LeetCode 15 · Two Pointers

3Sum, explained with a picture

Three lockers that cancel out.

MediumTwo Pointers
▶ Watch it step by step

The problem

Find every group of three numbers in the list that adds up to 0. Don’t list the same group twice.

Input:  [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

Picture it

First we sort the lockers by number. Then we pin one locker (the first of the three) and send two friends inward from the remaining ends, exactly like Two Sum II, looking for two lockers that cancel the pinned one. To avoid repeated answers, we skip over lockers with the same number as the one we just used.

How to recognise it

  • You need groups of three values with a fixed sum (here 0), and you must list every such group.
  • Fixing one value turns the rest into a pair-sum problem, which you already know how to solve.
  • The output must have no duplicate groups, and the input has repeated values. Sorting puts equal values side by side, which makes duplicates easy to skip.
  • The answer is values, not positions, so sorting the list loses nothing.
  • n is up to 3,000, so O(n²) is fine but O(n³) is not.

Start with brute force

Try every triple of positions, and collect the sorted triples that sum to 0 in a set so each group is kept once.

def three_sum_brute(nums):
    n = len(nums)
    found = set()
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    found.add(tuple(sorted((nums[i], nums[j], nums[k]))))
    return [list(t) for t in found]

There are about n³/6 triples, so time is O(n³). With n = 3,000 that is about 4.5 × 10^9 triples, far too slow. Space is O(t) for the t groups found.

From brute force to the idea

  1. Sort once. Sorted order lets you use two pointers for the pair, and puts duplicates next to each other.
  2. Fix the first number. For each position i, you need two later numbers that sum to −a[i]. That is Two Sum II on the part of the list after i.
  3. Two pointers for the pair. Start l just after i and r at the end. If the total is below 0, move l right; if above, move r left. Each pass over the rest of the list is O(n).
  4. Skip repeated first numbers. If a[i] equals a[i - 1], every group starting with it has already been found, so continue.
  5. Skip repeated second numbers. After recording a group, move l past every copy of a[l], then step both pointers. A new l with a bigger value needs a smaller partner, so the old r value cannot repeat the same group.

This is the key idea: sort, fix one number, find the other two with two pointers, and skip equal neighbours to avoid repeats.

The key idea

Sort, fix one number, then solve Two Sum II on the rest with two pointers. Skip equal neighbours to avoid duplicates. O(n²).

Python solution

def three_sum(nums):
    a = sorted(nums)
    res = []
    for i in range(len(a) - 2):
        if i and a[i] == a[i - 1]:
            continue
        l, r = i + 1, len(a) - 1
        while l < r:
            s = a[i] + a[l] + a[r]
            if s < 0:
                l += 1
            elif s > 0:
                r -= 1
            else:
                res.append([a[i], a[l], a[r]])
                while l < r and a[l] == a[l+1]:
                    l += 1
                l, r = l + 1, r - 1
    return res

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n³): every triple is checkedO(t): a set of the groups found
Sort + two pointers (shown code)O(n²): n fixed numbers, each with an O(n) pointer pass; the O(n log n) sort is smallerO(n): the sorted copy (sorted makes a new list), plus the output

Edge cases

  • All zeros ([0, 0, 0, 0]): returns [[0, 0, 0]] once.
  • No group ([0, 1, 1]): returns [].
  • Fewer than three numbers: returns []; range(len(a) - 2) is empty. LeetCode guarantees at least 3.
  • Two groups with the same first number ([-2, 0, 1, 1, 2]): returns [[-2, 0, 2], [-2, 1, 1]]. The pointers keep going after the first find.
  • Input order is kept: the code sorts a copy, so the caller's list is unchanged.
  • Output order: groups come out sorted by first number, then second. LeetCode accepts any order.

Common mistakes

  • Dropping the a[i] == a[i - 1] skip. Then [-1, -1, 0, 1] returns [-1, 0, 1] twice.
  • Writing the skip as a[i] == a[i + 1], which skips the first copy instead of the later ones and misses groups such as [-1, -1, 2].
  • Stopping the pointer loop after the first group, which misses [-2, 1, 1] above.
  • Removing duplicates with a set of tuples at the end. That fixes the output but hides a slow or wrong loop.
Your turn: the closest sum

Given at least three numbers and a target, return the sum of three numbers that is closest to the target. For [-1, 2, 1, -4] and target 1 the answer is 2 (−1 + 2 + 1). Describe your approach, then write it if you like.

Compare with our answer

Keep the same frame: sort, fix i, two pointers. At every step, compare the current sum with the best so far. Move the pointers exactly as before, using the target in place of 0. If you hit the target exactly, nothing can be closer. Duplicates no longer matter, because you return one number, not a list of groups.

def three_sum_closest(nums, target):
    a = sorted(nums)
    best = a[0] + a[1] + a[2]
    for i in range(len(a) - 2):
        l, r = i + 1, len(a) - 1
        while l < r:
            s = a[i] + a[l] + a[r]
            if abs(s - target) < abs(best - target):
                best = s
            if s < target:
                l += 1
            elif s > target:
                r -= 1
            else:
                return s
    return best

Time O(n²), space O(n) for the sorted copy.

A strong answer mentions: tracking the best by absolute difference, the same pointer moves, and returning early on an exact match.

Check what stuck

1. You must list every group of four values that sums to a target, without repeats. Which approach fits best?

2. Why is the shown code O(n²) and not O(n² log n)?

3. A learner deletes the if i and a[i] == a[i - 1]: continue lines. Which input now returns a repeated group?

Score 60% or more and the lesson is marked complete.