4.5.3 — 3Sum

LeetCode 15 · Medium · ★ Blind 75

The problem

Find every unique triple in the array that sums to zero. The array is unsorted and may contain repeats.

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

→ [[-1, -1, 2], [-1, 0, 1]]

Up to 3,000 numbers. Note [-1, 0, 1] appears only once even though there are two -1s that could form it. The uniqueness rule is where all the difficulty is, not the sum.

The pattern

Sort the array first. Sorting costs O(n \log n), which is free here because the solution is O(n^2) anyway, and it buys two things.

1. Two pointers become usable, so the inner search is O(n) instead of O(n^2).
2. Equal values sit next to each other, which makes duplicates cheap to skip.

Then: fix the first number, and run Two Sum II on everything after it, looking for a pair that sums to the negative of the fixed number.

A three-dimensional search became a loop around a one-dimensional one.

The solution

Python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []

        for i in range(len(nums) - 2):
            if nums[i] > 0:                                   # (1)
                break
            if i > 0 and nums[i] == nums[i - 1]:              # (2)
                continue

            l, r = i + 1, len(nums) - 1
            while l < r:
                total = nums[i] + nums[l] + nums[r]
                if total < 0:
                    l += 1
                elif total > 0:
                    r -= 1
                else:
                    result.append([nums[i], nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l - 1]:   # (3)
                        l += 1
                    while l < r and nums[r] == nums[r + 1]:
                        r -= 1

        return result

TypeScript

function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);                                 // numeric sort
  const result: number[][] = [];

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

    let l = i + 1, r = nums.length - 1;
    while (l < r) {
      const total = nums[i] + nums[l] + nums[r];
      if (total < 0) l++;
      else if (total > 0) r--;
      else {
        result.push([nums[i], nums[l], nums[r]]);
        l++;
        r--;
        while (l < r && nums[l] === nums[l - 1]) l++;          // (3)
        while (l < r && nums[r] === nums[r + 1]) r--;
      }
    }
  }
  return result;
}

(1) Stop when the fixed number goes positive. The array is sorted, so once nums[i] > 0 every remaining number is positive too, and three positives cannot sum to zero. Not required for correctness, but it is a free early exit and it shows you are reading the sorted order.

(2) Skip a repeated first element. If nums[i] equals nums[i-1], every triple starting here was already produced starting at i-1. The guard i > 0 protects the very first element, which has no predecessor.

(3) Skip repeated second and third elements, but only after a match. This is the line your Report 3 singled out, and the placement matters.

After recording a triple you advance both pointers, then skip forward past any values equal to the one you just used. That prevents [-1, -1, 2] being reported twice when there are two -1s in the middle of the array.

Put this skip inside the "found a match" branch, not in the main loop. Two reasons. First, it is only needed there — you only produce duplicates when you produce an answer. Second, the main loop runs on nearly every iteration while a match is rare, so a duplicate check sitting in the hot path is a branch the CPU has to evaluate constantly and predict wrongly. Nesting it in the rare branch keeps the common path straight.

Note the JavaScript sort. nums.sort() sorts as strings by default, so [10, 9] comes out as [10, 9]. You must pass (a, b) => a - b. Python's sort() is numeric already.

Trace

nums = [-1, 0, 1, 2, -1, -4] sorts to [-4, -1, -1, 0, 1, 2].

i	fixed	pointers walk	found
0	−4	needs a pair summing to 4; none	—
1	−1	l=2 (−1), r=5 (2) → sum 0	[-1, -1, 2]
		then l=3 (0), r=4 (1) → sum 0	[-1, 0, 1]
2	−1	equal to nums[1] → skipped by (2)	—
3	0	l=4 (1), r=5 (2) → sum 3, too big; r--; loop ends	—

Without guard (2), i = 2 would rediscover [-1, 0, 1] and the answer would contain it twice.

Complexity

O(n^2) time. The outer loop is n, and for each i the two pointers together cover the rest of the array once, which is O(n). Sorting adds O(n \log n), which is smaller and disappears.

O(1) extra space, not counting the output and whatever the sort uses internally. In Python, sort() is Timsort and uses up to O(n) temporary space, which is worth mentioning if the interviewer is strict.

The mutation problem

nums.sort() reorders the caller's array in place. On a coding judge that is fine. In real code, sorting an array somebody else handed you is a side effect they did not ask for, and if another part of the program is reading it, you have introduced a bug that is very hard to find.

Use sorted(nums) if the input belongs to someone else. It costs O(n) space and buys a function with no side effects.

Where this goes next

• 3Sum Closest — the same loops, but track the sum nearest to the target instead of exactly matching it. No duplicate handling needed at all, which shows how much of this problem was the uniqueness rule.
• 4Sum — one more outer loop, with the same skip guard at each level. O(n^3).
• 3Sum Smaller — count triples below a target. When nums[i] + nums[l] + nums[r] < target, then every position between l and r also works with l, so add r - l at once and move l. Counting a whole range in one step is the idea worth taking away.

The rule: to solve a k-sum, fix one element and reduce to a (k−1)-sum. The base case is two pointers.

What the interviewer will push on

"Why sort?" Two reasons, and say both: it enables two pointers, and it puts equal values next to each other so duplicates are cheap to skip.

"Where exactly do you skip duplicates, and why there?" Guard (2) for the fixed element, guard (3) inside the match branch for the pair. Duplicates only arise when an answer is produced.

"Could you use a hash set instead?" Yes — fix two elements and look up the third. That is also O(n^2) time but O(n) space, and deduplicating the results is messier because you end up sorting each triple to use it as a key. Two pointers is cleaner.

"Your sort mutates the input." Acknowledge it and offer sorted(nums).

One thing to volunteer: say that the uniqueness rule, not the arithmetic, is the hard part of this problem. That is the observation that separates people who have actually written it.

Next: 4.5.4 Container With Most Water — two pointers again, but now the discard rule comes from geometry rather than from sorting.