Solution: 3Sum

Statement

Given an integer array nums, find and return all unique triplets [nums[i], nums[j], nums[k]], where the indexes satisfy i$\neq$j, i$\neq$k, and j$\neq$k, and the sum of the elements nums[i] + nums[j] + nums[k] == 0.

Constraints:

• $3 \leq$ nums.length $\leq 500$

• $-10^3 \leq$ nums[i] $\leq 10^3$

Solution

We will use the two pointers pattern to solve the problem. This method requires sorting the input array, so our first step is sorting the array.

Sorting the array facilitates the two-pointers technique and makes it easy to handle duplicate values. As duplicate values are next to each other in a sorted array, we can skip over them to ensure the result contains unique triplets.

Once the array is sorted, we iterate over it. For each iteration, we select a “pivot” element nums[i] and focus on the elements to the right of it. The goal is to find all pairs of numbers that sum to -nums[i]. Adding this pair to the pivot ensures the total sum equals zero.

The two pointers approach involves positioning one pointer just after the pivot (low) and the other at the array’s end (high). By computing the sum of these pointers and the pivot, adjustments are made: incrementing `low` if the sum is too small or decrementing high if it’s too large. When the sum equals zero, the triplet is added to the result, and both pointers are adjusted, skipping duplicates. This strategy focuses on efficient exploration, guiding the sum toward zero.

Now, let’s look at the steps of the solution:

• Sort the input array, nums, in ascending order.

• Create an empty list, result, to store the unique triplets.

• Use a for loop to iterate over the array, treating each element nums[i] as the pivot.

• Start the iteration at index 0 until the third-to-last element (because at least three elements are needed for a triplet).

  • Initialize two pointers:

    • low starts at i + 1 (the element after the pivot).

    • high starts at the last element of the array.

  • While low is less than high, compute the sum of the pivot, nums[low], and nums[high]:

    • If the sum is less than zero, increment low to increase the sum.

    • If the sum is greater than zero, decrement high to decrease the sum.

    • If the sum equals zero:

      • Add the triplet [nums[i], nums[low], nums[high]] to the result.

      • Move both pointers to their next positions (low++ and high--).

      • Skip duplicates at the new low and high positions to ensure unique triplets.

  • If nums[i] is the same as nums[i - 1] (for i > 0), skip the current iteration.

  • If nums[i] > 0, break the loop.

• Once the loop completes, return the result list containing all unique triplets.

Let’s look at the following illustration to get a better understanding of the solution: