Solution: 3Sum

Statement

Given an integer array, nums, find and return all unique triplets [nums[i], nums[j], nums[k]], such that i $\neq$ j, i $\neq$ k, and j $\neq$ k and nums[i] + nums[j] + nums[k] $== 0$.

Note: The order of the triplets in the output does not matter.

Constraints:

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

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

Solution

The essence of the solution lies in first sorting the array, which makes it easier to find positive numbers that balance out negative ones to sum to zero, and also helps in skipping duplicates. Then, for each number in the array, we search for two other numbers to the right that, together with it, sum to zero. This is done using two pointers—low and high—starting just after the fixed number and at the end of the array, respectively. We calculate the sum of each triplet as nums[i] + nums[low] + nums[high]. If the total is less than zero, we move the low pointer forward to increase the sum; if it’s greater than zero, we move the high pointer backward to decrease the sum. When the sum is exactly zero, we add the triplet to the result and move both pointers inward, skipping duplicates to ensure all triplets are unique.

Using the intuition above, we implement the algorithm as follows:

1. Sort the input array nums in ascending order to make it easier to find triplets and skip duplicates.

2. Create an empty array, result, to store the unique triplets.

3. Store the length of nums in a variable n.

4. Iterate over the array from index i = 0 to n - 2 (as we are looking for triplets).

   1. Break the loop if the current number nums[i] is greater than 0. As the array is sorted, all remaining numbers will be positive, and any triplet including nums[i] will have a sum greater than zero.

   2. If i == 0 or nums[i] is not equal to nums[i - 1], this ensures that the current number is either the first element or not a duplicate of the previous element.

      1. Initialize two pointers: low = i + 1 and high = n - 1.

      2. Run a loop as long as low is less than high.

         1. Calculate the sum: nums[i] + nums[low] + nums[high].

         2. If the sum is less than 0, move the low pointer forward to increase the sum.

         3. If the sum is greater than 0, move the high pointer backward to decrease the sum.

         4. Otherwise, add [nums[i], nums[low], nums[high]] to the result, as this triplet sums to 0.

         5. Move low and high to the next distinct values to avoid duplicate triplets. This is done by incrementing low while nums[low] == nums[low - 1], and decrementing high while nums[high] == nums[high + 1].

5. After iterating through the whole array, return the result that contains all unique triplets that sum to zero.

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