3Sum

A reliable 3Sum solution comes from turning a cubic search into a sequence of sorted two-sum scans—and proving why each pointer move is safe.

Start with the obligations

Given an integer array, return every unique triplet of values from three different indices whose sum is zero. The result must not repeat a value triplet, even when the input contains repeated values.

There are three obligations to keep visible while designing the algorithm:

1. Choose three different positions.
2. Make their values sum to zero.
3. Return each value composition once.

For example, [-1, 0, 1] and [1, -1, 0] describe the same triplet. Sorting gives every discovered triplet a canonical order, which makes both duplicate handling and reasoning much cleaner.

The optimized plan is short:

1. Sort the array.
2. Fix one value at index i.
3. Search the suffix for two values summing to -nums[i].
4. Move two pointers according to whether the current sum is too small or too large.
5. Skip repeated values at the fixed position and after each match.

The important idea is not merely that two pointers are fast. Sorting makes the remaining search monotonic, so one movement can eliminate a whole group of impossible pairs.

The brute-force baseline

The direct approach chooses indices in increasing order:

i < j < k

For each combination, calculate:

nums[i] + nums[j] + nums[k]

Save the triplet when the sum is zero. This checks every possible combination and takes O(n³) time.

A duplicate-free version can sort the input, store each matching triplet as a tuple, and use a set to remove repeated value compositions. That is a valid baseline because it establishes coverage: every combination is considered, and the three indices are distinct by construction.

But it spends work on pairs that sorted order could reject immediately. The optimized version keeps the same obligations while shrinking the candidate space. That is the real transition from brute force to two pointers.

Sort, fix, and reduce to 2Sum

Sort the values in ascending order. For a fixed index i, the remaining equation is:

nums[left] + nums[right] == -nums[i]

Initialize the pointers like this:

left = i + 1
right = n - 1

Because left starts after i and the loop runs only while left < right, the three selected indices are always different.

The outer loop stops at n - 3, because two positions must remain after the fixed value. In Python, range(n - 2) expresses that boundary.

There is also a safe early stop. Once nums[i] > 0, every later value is positive because the array is sorted. Any later triplet therefore has a positive sum, so it cannot equal zero.

if nums[i] > 0:
    break

This guard is an optimization, not the central proof. The central proof is the monotonic behavior of the sorted suffix.

Why the pointers move in one direction

For a fixed i, compute:

current_sum = nums[i] + nums[left] + nums[right]

The sorted values tell us which boundary can still improve the sum.

The sum is too small

If current_sum < 0, moving right left would choose an equal or smaller value and could only keep the sum the same or make it smaller. It cannot produce zero.

Move left right instead:

left += 1

The next left value is at least as large and is the only movement that can increase the sum.

The sum is too large

If current_sum > 0, moving left right would choose an equal or larger value and could only keep the sum the same or make it larger. It cannot produce zero.

Move right left:

right -= 1

The next right value is at most as large and is the only movement that can decrease the sum.

The sum is zero

Record the triplet, then move both pointers inward. The current pair has been consumed, and the same two positions cannot be reused.

The pointer rule is not a heuristic: a negative sum makes the left boundary the only useful boundary to advance, while a positive sum makes the right boundary the only useful boundary to retreat.

For one fixed i, each pointer moves inward and never reverses direction. The inner scan is therefore linear. Across all fixed positions, the algorithm takes O(n²) time after sorting.

Duplicate skipping has two separate jobs

Duplicate handling is easier when treated as a pair of invariants rather than as a cleanup step.

Skip repeated fixed values

At the start of the outer loop:

if i > 0 and nums[i] == nums[i - 1]:
    continue

The earlier occurrence already searched the relevant suffix for this value. Repeating the same fixed value would reproduce the same value triplets.

Do not skip every repeated value indiscriminately. Repeated values can be required inside a valid answer. Both [-1, -1, 2] and [0, 0, 0] are legitimate triplets because their values come from distinct indices.

Skip repeated pointer values after a match

After recording a match, advance both pointers first. Then skip equal neighbors:

left += 1
right -= 1

while left < right and nums[left] == nums[left - 1]:
    left += 1

while left < right and nums[right] == nums[right + 1]:
    right -= 1

The comparisons use the values just consumed. The bounds checks prevent the duplicate scan from leaving the active range.

For [-2, 0, 0, 2, 2], fixing -2 produces [-2, 0, 2]. The second zero and second two are different positions, but they do not produce a new value composition. Skipping them prevents a repeated output.

This distinction matters:

• pointer boundaries guarantee distinct indices;
• duplicate skipping guarantees unique value triplets.

They solve different problems.

Correctness through invariants

For a fixed i, maintain this invariant:

Before each inner-loop iteration, every discarded pair is unable to form a new valid pair for this fixed value, and every unexamined pair lies within the current pointer range.

The invariant survives each branch:

• If the sum is too small, every pair using the current left with a smaller right position is also too small. Advancing left discards only impossible pairs.
• If the sum is too large, every pair using the current right with a larger left position is also too large. Decreasing right discards only impossible pairs.
• If the sum is zero, the pair is valid and is recorded before both positions are consumed.

Now consider the outer loop. Any valid triplet can be written in sorted value order as a <= b <= c. The first occurrence of a is processed as the fixed value. Later equal occurrences are skipped, but they would search the same value-based combinations and add no new result.

The inner scan finds the pair for that fixed value because it never discards a pair that could still reach the target. Duplicate skipping does not remove the first necessary occurrence of a value; it removes only later equivalent representations after a valid composition has already been recorded.

Finally, left > i and left < right guarantee three different indices. Every loop iteration advances a pointer, so the scan terminates.

The proof is a state-management proof: name what remains possible, name what has been ruled out, and show that each transition preserves those claims.

Dry run: [-1, 0, 1, 2, -1, -4]

After sorting:

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

A few states expose the mechanism:

Fixed value	Left value	Right value	Sum	Action
-4	-1	2	-3	Too small; advance left
-4	0	2	-2	Too small; advance left
-4	1	2	-1	Too small; advance left
-1	-1	2	0	Record [-1, -1, 2]
-1	0	1	0	Record [-1, 0, 1]

When -4 is fixed, even the largest available pair cannot raise the sum to zero. The pointers discover this without enumerating every pair.

At the first -1, the pair [-1, 2] gives zero. After both pointers move, [0, 1] gives the second result. The next outer value is another -1, so that fixed position is skipped.

For [0, 0, 0, 0], the first zero uses two later positions to produce [0, 0, 0]. After the match, equal pointer values are skipped, and later outer zeros are skipped as well. The result contains one triplet, while the selected indices remain distinct.

Python implementation

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result: list[list[int]] = []
    n = len(nums)

    for i in range(n - 2):
        if nums[i] > 0:
            break

        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left = i + 1
        right = n - 1

        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]

            if current_sum < 0:
                left += 1
            elif current_sum > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])

                left += 1
                right -= 1

                while left < right and nums[left] == nums[left - 1]:
                    left += 1

                while left < right and nums[right] == nums[right + 1]:
                    right -= 1

    return result

The code follows the proof directly:

• i selects the first value;
• left and right bound the unexamined pair range;
• the sign of current_sum chooses the only useful pointer movement;
• a match advances both pointers before duplicate skipping.

nums.sort() mutates the input list. If the surrounding function must preserve the original list, use a sorted copy instead:

values = sorted(nums)

The algorithm is unchanged; only the input-storage decision differs.

Complexity and edge cases

Sorting costs O(n log n). For each fixed value, the two pointers move across the suffix in linear time, so the scans cost O(n²) overall. The total is:

O(n log n + n²) = O(n²)

Apart from the returned triplets, the algorithm uses O(1) auxiliary space when the sort is in place. The output itself is output-dependent and should be counted separately.

Check these boundaries:

• fewer than three values: return an empty list;
• all positive values: stop at the first positive fixed value;
• all negative values: the sums remain too small and no result is found;
• repeated zeros: return [0, 0, 0] once;
• repeated negative or positive values: skip duplicates at both levels;
• several matches for one fixed value: move both pointers, then continue scanning.

Common bugs are useful diagnostic signals. Reusing unrestricted indices violates the contract. Skipping repeated values before their first necessary use can remove [-1, -1, 2]. Moving the wrong pointer moves the sum away from zero. Skipping only the outer duplicate can still produce repeated results after multiple matches.

The transferable recognition rule

When you see a fixed-size sum problem with an exact target, ask:

1. Can sorting make the candidate values monotonic?
2. Can I fix one dimension and reduce the rest to a two-pointer search?
3. Which entire group of states becomes impossible after each comparison?

For 3Sum, the answers are yes, yes, and “the pairs on the wrong side of the current sum.”

Sort. Fix. Scan. Prove the discarded states. Handle duplicates as a separate invariant.

If you can explain why a negative sum advances left, why a positive sum retreats right, and why duplicate skipping begins only after preserving the first necessary occurrence, you understand the 3Sum solution. The code is then a translation of the reasoning rather than a spell memorized from one example.