Canonical Deep-Dive: 3Sum

Problem: 3Sum (https://leetcode.com/problems/3sum/) The lesson: sort to unlock the directional rule, fix one index, two-pointer the rest, and handle duplicates deliberately at every level.

This is a guided walk-through, not an answer key. It explains how to think about the approach and what it costs, and shows the skeleton in words and high-level pseudocode. It stops short of an assembled, paste-runnable function on purpose. You write the actual Python yourself, in your own work repo. The tutor will not confirm your code; LeetCode’s judge will.

Restated: given an integer array nums, return all distinct triples [a, b, c] such that a + b + c == 0. The result must not contain duplicate triples. Order within a triple and order of the triples do not matter to the judge.

Why the brute force is not enough

The most direct idea is to try every triple of indices.

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:
                record (nums[i], nums[j], nums[k])
  • Time: O(n^3). Three nested loops over the array.
  • Space: O(1) extra (ignoring the output and a set you would need to de-duplicate).

This is your baseline, and you should be able to write it without thinking. But it has two problems: it is cubic, and de-duplicating the triples it finds is awkward (you would normalize each triple by sorting it and drop it into a set). Both problems are solved by the same single move: sort the array first.

The insight: sort, then reduce to a two-pointer scan

Once nums is sorted, two things become true at once.

First, the three-number search collapses by one dimension. Fix the first element with an index i. Now you need two more numbers, drawn from the part of the array to the right of i, that sum to -nums[i]. That is exactly the two-pointer scan you will practice all week: on a sorted range, put one pointer just after i and one at the far end, and walk them toward each other under the directional rule. So 3Sum is “for each fixed first element, solve a Two Sum II on the sorted remainder.” The outer fix is O(n), the inner scan is O(n), and the product is O(n^2): one order better than brute force.

Second, duplicates line up. Equal values are now adjacent, so producing only distinct triples becomes a matter of advancing past runs of equal values at the right moments, with no set needed.

The directional rule on the remainder

This is the Two Sum II move (you will also solve it as a standalone problem this week). With the first element fixed at i, set target = -nums[i], put lo = i + 1 and hi = n - 1, and loop while lo < hi:

s = nums[lo] + nums[hi]
if s < target:   lo += 1     # sum too small: only a larger left value can help
elif s > target: hi -= 1     # sum too large: only a smaller right value can help
else:            record the triple, then advance past duplicates (see below)

Why this is safe: the remainder is sorted, so when nums[lo] + nums[hi] is too small, every pair using nums[lo] with a value at or left of hi is also too small (those values are all <= nums[hi]), so they are all ruled out and lo can move right without skipping a solution. The mirror argument moves hi left when the sum is too large. Each step discards a whole batch of pairs, which is why the inner scan is linear, not quadratic.

Skipping duplicates at three levels

This is the part people get wrong, so be deliberate. There are exactly three places a duplicate can sneak in, and each needs its own skip.

  1. The fixed index i. Before you use nums[i] as the anchor, check whether it equals the previous anchor: if i > 0 and nums[i] == nums[i - 1], skip this i entirely. The previous identical anchor already found every triple that starts from this value, so re-running it would only reproduce them.
  2. The left pointer lo, after recording a triple. Once you record a triple and step lo forward (and hi back), advance lo past every copy of the value you just used: while lo < hi and nums[lo] == nums[lo - 1]: lo += 1. Without this, a repeated left value re-emits the same triple.
  3. The right pointer hi, after recording a triple. Symmetrically, advance hi past every copy of its value: while lo < hi and nums[hi] == nums[hi + 1]: hi -= 1.

Level 1 keeps the anchor distinct; levels 2 and 3 keep the pair distinct for a given anchor. Together they guarantee distinct triples without ever building a set of seen results.

One optional early exit: because the array is sorted, once nums[i] > 0 the smallest possible triple sum from i onward is already positive, so no remaining anchor can reach zero and you can stop the outer loop. This does not change the asymptotic cost; it just saves obvious work.

The skeleton, in one place

Pulling the pieces together as high-level pseudocode (you write the Python):

sort nums
for i in range(n):
    if nums[i] > 0: break                      # optional early exit
    if i > 0 and nums[i] == nums[i - 1]: continue   # skip duplicate anchor
    lo, hi = i + 1, n - 1
    while lo < hi:
        s = nums[i] + nums[lo] + nums[hi]
        if s < 0:        lo += 1
        elif s > 0:      hi -= 1
        else:
            record (nums[i], nums[lo], nums[hi])
            lo += 1; hi -= 1
            skip lo past duplicates of its previous value
            skip hi past duplicates of its previous value

This is the shape, not a finished solution: you still decide how to store and return the triples, get the loop bounds exactly right, and prove to yourself that the three skips cover every duplicate case.

The key insight, in one sentence

Sorting turns a triple search into “fix one number, two-pointer the sorted remainder for its complement,” which drops the cost from O(n^3) to O(n^2), and because equal values are now adjacent, distinctness is enforced by advancing past duplicate runs at three points rather than by a set.

Exact complexity

  • Time: O(n^2). The sort is O(n log n), which is dominated by the main work: n choices of the fixed index, each running an O(n) two-pointer scan over the remainder, for O(n^2) total. The duplicate-skips do not add an extra factor; across one inner scan, lo and hi each move at most n times total.
  • Space: O(1) extra, excluding the output list and the space the sort uses. The two-pointer scan holds only a constant number of indices; no hash set, no auxiliary array. (Python’s sort is not in-place-free, but the standard accounting for this problem counts only the extra space your algorithm adds beyond input, output, and the sort.)

Your work this week

  1. Implement 3Sum yourself, in your own work repo (for example three-sum.py). Sort, loop the fixed index with the anchor skip, run the two-pointer scan on the remainder, and handle the left and right duplicate skips. Build it from the skeleton above; do not copy a solution.
  2. Test the duplicate handling deliberately. Run the provided examples ([-1, 0, 1, 2, -1, -4] gives [[-1, -1, 2], [-1, 0, 1]]; [0, 1, 1] gives []; [0, 0, 0] gives [[0, 0, 0]]), then add your own all-duplicate input like [0, 0, 0, 0] and confirm you emit [0, 0, 0] exactly once. Then submit to LeetCode’s judge.
  3. Commit with a five-question debrief in the message. In answer 3, state the exact complexity above (O(n^2) time, O(1) extra space excluding output and sort) and explain why the sort is not the dominating term.

When you can explain, from memory and with no AI open, why sorting licenses the two-pointer scan, why each pointer move cannot skip a valid pair, and what each of the three duplicate-skips prevents, you own this problem. That explanation is exactly what an interviewer will ask for, and the sort-then-two-pointer template is one you will reuse across this week and beyond.