LeetCode 15 · Two Pointers · Sorting

3Sum

MediumFind every unique triplet that sums to zero — sort, then two-pointer.
Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c = 0. The solution set must not contain duplicate triplets.

Walkthrough

try:
Find every unique triplet that sums to 0. Sort, then fix an anchor and sweep two pointers.
sorted nums
-4
·
-1
·
-1
·
0
·
1
·
2
·
—
triplets found
(none yet)
anchor ileftrightskipped dup
1
function threeSum(nums) {
2
  nums.sort((a, b) => a - b);
◄
3
  const res = [];
4
  for (let i = 0; i < nums.length - 2; i++) {
5
    if (i > 0 && nums[i] === nums[i-1]) continue;
6
    let left = i + 1, right = nums.length - 1;
7
    while (left < right) {
8
      const sum = nums[i] + nums[left] + nums[right];
9
      if (sum < 0) left++;
10
      else if (sum > 0) right--;
11
      else {
12
        res.push([nums[i], nums[left], nums[right]]);
13
        left++; right--;
14
        while (left<right && nums[left]===nums[left-1]) left++;
15
        while (left<right && nums[right]===nums[right+1]) right--;
16
      }
17
    }
18
  }
19
  return res;
20
}
nums = [-4, -1, -1, 0, 1, 2]
step 0 / 26
line 2
Sort the array
Sorting lets us sweep two pointers instead of a nested search. Sorted: [-4, -1, -1, 0, 1, 2].

Intuition

Sorting unlocks the two-pointer trick and makes duplicate-skipping easy, at a cost of only O(n log n).

Fix one number as an anchor (nums[i]); the problem reduces to “find two numbers in the rest that sum to −nums[i]” — the classic sorted two-pointer scan.

With left just after the anchor and right at the end: if the sum is too small move left up (bigger), if too big move right down (smaller), if exactly zero record it.

Skip duplicate values for the anchor and after finding a triplet, so each combination is reported once. Overall O(n²).

The algorithm

  1. 01Sort nums.
  2. 02For each anchor i (skipping repeats), set left = i + 1, right = n − 1.
  3. 03While left < right, compare nums[i] + nums[left] + nums[right] to 0 and move the appropriate pointer.
  4. 04On a zero sum, record the triplet, move both pointers, and skip any duplicate values.
  5. 05Return all collected triplets.

Reference implementation

1
function threeSum(nums) {
2
  nums.sort((a, b) => a - b);
3
  const res = [];
4
  for (let i = 0; i < nums.length - 2; i++) {
5
    if (i > 0 && nums[i] === nums[i - 1]) continue;   // skip duplicate anchor
6
    let left = i + 1, right = nums.length - 1;
7
    while (left < right) {
8
      const sum = nums[i] + nums[left] + nums[right];
9
      if (sum < 0) left++;
10
      else if (sum > 0) right--;
11
      else {
12
        res.push([nums[i], nums[left], nums[right]]);
13
        left++; right--;
14
        while (left < right && nums[left] === nums[left - 1]) left++;
15
        while (left < right && nums[right] === nums[right + 1]) right--;
16
      }
17
    }
18
  }
19
  return res;
20
}

Complexity

Time
O(n²) — an O(n) two-pointer scan for each of n anchors.
Space
O(1) beyond the output (ignoring the sort).