3Sum

The problem

Given a list of integers nums, return every triple of values that adds up to zero. The three values must come from three different positions in the list. Each triple appears once in the answer: triples that hold the same three values count as one, whatever positions they came from. The triples may be in any order, and so may the values inside a triple. If there are none, return an empty list.

What to write

function solve(nums: number[]): number[][]

Input
nums = [-1,0,1,2,-1,-4]

Output
[[-1,-1,2],[-1,0,1]]

Input
nums = [0,0,0,0]

Output
[[0,0,0]]

Constraints

0 ≤ nums.length ≤ 3000.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   With up to 3,000 numbers, trying every group of three is about 4.5 billion sums, which is far too many. A method that does about n × n work, 9 million steps here, is fine. Notice also that the order of the numbers in the list does not matter to the answer.

2. Hint 2: Ask a smaller question

   Suppose one number of the triple is already chosen, say -1. What must the other two add up to? Finding two numbers with a given sum is a problem you have met before.

3. Hint 3: Name the pattern

   Sort the list. Then each number in turn is the smallest of a triple, and the other two come from the numbers after it. That is a pair with a known sum in a sorted list, which is Two Sum II. The inner search is opposing two pointers. Read the lesson on opposing two pointers.

4. Hint 4: State the invariant

   For the current smallest number, every pair that completes a triple and is not yet recorded lies between the two pointers. Equal values sit side by side after sorting, so stepping past a value you have already used is what keeps a triple from appearing twice.

5. Hint 5: Sketch the pseudocode

   Sort. For each position i: skip it if its value equals the one before. left = i + 1, right = last position. While left < right: add the three numbers. Below zero: add 1 to left. Above zero: subtract 1 from right. Zero: record the triple, move both inward, then past values equal to the ones they left.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Sort, fix one value, and use two pointers to find matching pairs. Skip repeated values to avoid duplicate triples.

The slow way

Try every group of three positions, keep the groups that add up to zero, and then throw out the triples that repeat the same three values. It is correct, but 3,000 numbers make about 4.5 billion groups, and removing the repeats is extra work on top.

The insight

Fix one number, say -1, and the other two must add up to its opposite, 1. In a sorted list that is Two Sum II: one pass with two pointers. Sorting also puts equal values side by side, so stepping past a value you have already used is all it takes to never record a triple twice.

Step by step

1. Sort the numbers from smallest to largest. In sorted order a sum that is too small or too large tells you which pointer to move. Sorting also puts equal values next to each other, so a repeat can be spotted by looking at its neighbor.
2. Take each number in turn as the smallest of a triple. Every triple has a smallest value, so trying each number in that role misses none. The last two numbers have fewer than two numbers after them, so the loop stops before them.
3. Skip a number equal to the one before it. The earlier copy had this copy and everything after it to choose from, so it already found every triple this one could start. Running again would only record them a second time.
4. Search the numbers after it with a pointer at each end. Looking only at later numbers builds each triple in sorted order, so it is found from its smallest value and from nowhere else. The two pointers frame the pairs that are still possible.
5. Move the left pointer if the sum is below zero, the right if above. This is Two Sum II. Below zero, the left number is too small even with the largest partner that remains, so it is ruled out. Above zero, the right number is too large in the same way.
6. A sum of zero is a triple: record it and move both pointers inward. Both numbers are used. Keeping one of them would need a partner equal to the other to reach zero again, and that would be the same triple, so both pointers move.
7. Move each pointer past any values equal to the one it left. A value equal to the one a pointer left could only build the same triple again. Stepping past such values loses nothing and keeps the answer free of repeats.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Sort the numbers from smallest to largest
  nums.sort((a, b) => a - b);
  const out = [];
  // 2. Take each number in turn as the smallest of a triple
  for (let i = 0; i < nums.length - 2; i++) {
    // 3. Skip a number equal to the one before it
    if (i && nums[i] === nums[i - 1]) continue;
    // 4. Search the numbers after it with a pointer at each end
    let l = i + 1,
      r = nums.length - 1;
    while (l < r) {
      // 5. Move the left pointer if the sum is below zero, the right if above
      const sum = nums[i] + nums[l] + nums[r];
      if (sum < 0) l++;
      else if (sum > 0) r--;
      else {
        // 6. A sum of zero is a triple: record it and move both pointers inward
        out.push([nums[i], nums[l], nums[r]]);
        l++;
        r--;
        // 7. Move each pointer past any values equal to the one it left
        while (l < r && nums[l] === nums[l - 1]) l++;
        while (l < r && nums[r] === nums[r + 1]) r--;
      }
    }
  }
  return out;
}

function solve(nums: number[]): number[][] {
  // 1. Sort the numbers from smallest to largest
  nums.sort((a, b) => a - b);
  const out: number[][] = [];
  // 2. Take each number in turn as the smallest of a triple
  for (let i = 0; i < nums.length - 2; i++) {
    // 3. Skip a number equal to the one before it
    if (i && nums[i] === nums[i - 1]) continue;
    // 4. Search the numbers after it with a pointer at each end
    let l = i + 1,
      r = nums.length - 1;
    while (l < r) {
      // 5. Move the left pointer if the sum is below zero, the right if above
      const sum = nums[i] + nums[l] + nums[r];
      if (sum < 0) l++;
      else if (sum > 0) r--;
      else {
        // 6. A sum of zero is a triple: record it and move both pointers inward
        out.push([nums[i], nums[l], nums[r]]);
        l++;
        r--;
        // 7. Move each pointer past any values equal to the one it left
        while (l < r && nums[l] === nums[l - 1]) l++;
        while (l < r && nums[r] === nums[r + 1]) r--;
      }
    }
  }
  return out;
}

def solve(nums):
    # 1. Sort the numbers from smallest to largest
    nums.sort()
    out = []
    # 2. Take each number in turn as the smallest of a triple
    for i in range(len(nums) - 2):
        # 3. Skip a number equal to the one before it
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # 4. Search the numbers after it with a pointer at each end
        left, right = i + 1, len(nums) - 1
        while left < right:
            # 5. Move the left pointer if the sum is below zero, the right if above
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                # 6. A sum of zero is a triple: record it and move both pointers inward
                out.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                # 7. Move each pointer past any values equal to the one it left
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
    return out

Example 1, traced

Input
nums = [-1,0,1,2,-1,-4]

Output
[[-1,-1,2],[-1,0,1]]

Why it works

Take any triple that adds up to zero and call its values a, b and c from smallest to largest. The loop reaches the first copy of a, and the pointers then close in on b and c, because a pointer only steps past a number that cannot be part of a new triple. Skipping equal values removes repeats and nothing else.

Time and space

Time O(n²), extra space O(n + output). Sorting takes about n log n steps. Then each of the n numbers gets one two-pointer pass over the numbers after it, at most n steps each: O(n²) time. Apart from the answer, the only extra memory is what the sort uses, which is at most O(n).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• After recording a triple, move both pointers past values equal to the ones they left. Skipping repeats only for the smallest number is not enough: the list -2, 0, 0, 2, 2 would record -2, 0, 2 twice.
• When you skip a repeated smallest number, compare it with the one before, not the one after. Skipping the first -1 of example 1 loses the triple -1, -1, 2, which needs both copies.
• In JavaScript, give sort a compare function. A bare sort() orders numbers as text and puts -1 before -2, and the list 3, 2, -2, -1, 1, -1 then loses the triple -2, -1, 3.

Pattern

Opposing two pointers. Builds on Two Sum II Input Array Is Sorted.

Keep going