medium

3Sum

Find every unique triplet of numbers in an array that adds up to zero.

1. Define the problem

3Sum

Given an integer array nums, return all the triplets [numsi, numsj, numsk] such that i != j, i != k, and j != k, and numsi + numsj + numsk == 0. Notice that the solution set must not contain duplicate triplets . Sort the array first, fix one element in an outer loop, then run converging two pointers on the remainder — skipping over repeated values at every level keeps the output free of duplicate triplets.

Constraints

  • 3 ≤ nums.length ≤ 3000
  • -105 ≤ numsi ≤ 105

Example

Inputnums = [-1, 0, 1, 2, -1, -4]
Output[[-1, -1, 2], [-1, 0, 1]]

Explanation nums0 + nums1 + nums2 = -1 + 0 + 1 = 0, and nums1 + nums2 + nums4 = 0 + 1 + -1 = 0. The distinct triplets are [-1, 0, 1] and [-1, -1, 2]; the order of the output and of each triplet does not matter.

2. Know the words first

In plain terms

Triplet
A group of exactly three values picked from the array, like picking three friends out of a group.
3. Visualize the solution

Fix one element, converge two pointers on the rest

Fix one element, converge two pointers on the rest
Statusinit

Sort the array. Fix the outer anchor at index 1 (-1). left=2, right=5.

What happens in this step

anchor = index 1 (value -1)
left = 2 (value -1), right = 5 (value 2)

The anchor is fixed at -1; left and right sit just after it and at the array's end, ready to converge.
Step 1 of 3

Steps to visualize

  1. Sort the array so equal values sit next to each other and sums move monotonically.
  2. Fix the leftmost unfixed element as the outer anchor, skipping it if it repeats the previous anchor.
  3. Set left just after the anchor and right at the end of the array.
  4. If the three-way sum is 0, record the triplet, then skip past any duplicate values on both sides before moving both pointers inward.
  5. If the sum is negative, move left inward; if it is positive, move right inward.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Fix one element, converge two pointers on the rest
Statusinit

Sort the array. Fix the outer anchor at index 1 (-1). left=2, right=5.

What happens in this step

anchor = index 1 (value -1)
left = 2 (value -1), right = 5 (value 2)

The anchor is fixed at -1; left and right sit just after it and at the array's end, ready to converge.
Step 1 of 3
5. Solution

Solution

solution.tsTypeScript
function threeSum(nums) {
  const sorted = [...nums].sort((a, b) => a - b);
  const result = [];

  for (let i = 0; i < sorted.length - 2; i++) {
    if (i > 0 && sorted[i] === sorted[i - 1]) {
      continue;
    }
    if (sorted[i] > 0) {
      break;
    }

    let left = i + 1;
    let right = sorted.length - 1;

    while (left < right) {
      const sum = sorted[i] + sorted[left] + sorted[right];

      if (sum === 0) {
        result.push([sorted[i], sorted[left], sorted[right]]);
        while (left < right && sorted[left] === sorted[left + 1]) {
          left++;
        }
        while (left < right && sorted[right] === sorted[right - 1]) {
          right--;
        }
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }

  return result;
}
Time
O(n^2)
Space
O(n) (for the sort; excluding the output array)
6. Test cases

Test cases

InputExpectedCovers
nums = [-1, 0, 1, 2, -1, -4][[-1, -1, 2], [-1, 0, 1]]example from the docstring
nums = [0, 1, -1][[-1, 0, 1]]smallest valid input: exactly three elements
nums = [0, 0, 0, 0][[0, 0, 0]]all-zero array collapses to a single deduplicated triplet
nums = [-2, 0, 0, 2, 2][[-2, 0, 2]]duplicate values that would otherwise produce a repeat triplet
nums = [1, 2, -2, -1][]no combination of three values sums to zero
nums = [1, 2][]array shorter than three elements returns empty

Keep reading