Leetcode # 15. 3Sum provides an unsorted list of integers and asks that you find all unique triplets from that list that add to a target number, in this case zero (0). A brute force approach would be to use three nested for loops, reaching a runtime complexity of O(n^3) in order to find all triplets. However, building on two earlier Leetcode "sum" problems, 1. Two Sum and 167. Two Sum II - Input Array Is Sorted (TwoSum Sorted for the rest of this blog) it is possible to implement an O(n^2) approach.

Hints

There are two big hints to this problem, as mentioned on Leetcode, that I've paraphrased below:

1. Can we "fix" one number x and then traverse the rest of the array to find all combos y and z so that x + y + z = 0? This makes the problem much more similar to TwoSum.
2. Can we modify the input array so that search is faster?

The answer is yes! If we sort our array in ascending order we can fix one number for each round and then implement a take on TwoSum Sorted to find all remaining members of each triplet for that number.

Runtime

In this case we will target a runtime complexity of O(n^2), which makes the addition of sorting at the beginning "free". More specifically, our target runtime is now O(n^2) + O(nlogn), but in Big O notation the smaller added chunks of runtime will fall away, leaving us with O(n^2).

Now with sorting out of the way, we can approach this problem similarly to the sorted TwoSum problem and use two pointers.

Outer Loop

The gist

If we "fix" one number x, we can then scan the array once for each x using the two pointer approach from TwoSum Sorted to find all possible y and z combos such that x + y + z = 0. See note (a) below for progressing through the outer loop.

Inner Loop:

For each x, we will use a low and high pointer to look for potential options for y and z respectively. We will set our low pointer to x + 1 and our high pointer to the last element of the array (nums.length - 1).

Now we are simply implementing the two pointer approach from TwoSum Sorted. There are two ways to conceptualize what our new TwoSum Sorted approach is seeking:
Option 1) find the numbers y and z such that x + y + z = 0
Option 2) find the numbers y and z such that y + z = x * -1.
I prefer Option 1 so that is shown in the code below.

The Gist

At each step of TwoSum Sorted ask:

• Does the sum of x + y + z equal 0? If yes, we've found a valid answer so add this triplet to the result. Then iterate both low (increase with low++) and high (decrease with high--). See note (b) below.

• Alternately, if this sum does not equal 0, we need to figure out which pointer to move:

  • If the sum is less than the target (0), then we know our current combination of numbers is too low. Therefore, we need to increase the numbers involved. Increase the bottom pointer with low++ (see note (b) below).
  • If the sum is greater than the target, the opposite is true and we need to decrease the values involved. Decrease the high pointer with high-- (see note c below).

We will follow this process until we've traversed our current section of the array (x + 1 to end) and save all valid triplets in a results array. Then progress to the next element in the outer loop and repeat, continuing until we've reached the end of the array or gone above 0 (see note (d) below).

Notes

a) In our outer `for` loop, skip any duplicate numbers.
b) Like in (a), when we find a valid triplet and we increase `low`, skip any duplicate numbers.
c) We will check all `high` values every time. As we are validating uniqueness on `x` and `y`, we should include duplicates for `z`. This ensures that we find all valid triplet combos while skipping duplicates.
d) In our outer loop, stop once we've gone above `0`. As our array is ordered, if `x` is 1, that means any potential `y` or `z` will be at least `1`. It is not possible for `1 + 1 + 1` (or any larger combination of numbers) to equal `0` so we know we are done at that point.

Code:

var threeSum = function (nums) {
    const results = [];

    nums.sort((a, b) => a - b);

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] <= 0) {
            if (i === 0 || nums[i] !== nums[i - 1]) {
                twoSumII(nums, i, results);
            }
        }
    }

    return results;
};

const twoSumII = (nums, i, results) => {
    let lo = i + 1;
    let hi = nums.length - 1;

    while (lo < hi) {
        const sum = nums[i] + nums[lo] + nums[hi];

        if (sum > 0) {
            hi--;
        } else if (sum < 0) {
            lo++;

            while (nums[lo] === nums[lo - 1]) {
                lo++;
            }
        } else {
            results.push([nums[i], nums[lo], nums[hi]]);

            lo++;
            while (nums[lo] === nums[lo - 1]) {
                lo++;
            }

            hi--;
        }
    }
}