3 Sum
WHAT IT SAYS
Find all unique triplets in an array that sum to zero, with no duplicate triplets in the output.
WHAT IT'S REALLY ASKING
"Fix one number and the rest of the problem collapses to: find two numbers summing to a known target. Now sort, and put a finger on each end of what is left. Their sum is simultaneously the biggest sum the left finger can ever make and the smallest the right finger can ever make — so whichever way it is wrong, it tells you exactly which finger is out of a job."
Three nested loops, then de-duplicate
O(n^3) time, O(number of triplets) spaceTry every triple of indices i < j < k, keep the ones summing to zero, sort each surviving triplet and throw it into a set so the duplicates collapse.
WHERE THE WORK IS WASTED — The innermost loop is a linear search for a value that is already known: once you have fixed a and b, the third number MUST be -(a + b). You are scanning an array to look for something you could have computed. And the de-duplication set is worse — it exists only because your loops generate the same answer over and over from different index orders, so you are manufacturing duplicates on purpose and then paying memory to filter them out.
Hash the third value
O(n^2) time, O(n) spaceFix i and j with two loops, then check whether -(a[i] + a[j]) exists in a hash set of the remaining elements. The third element is now found in O(1) instead of searched for.
WHERE THE WORK IS WASTED — Time is nearly optimal, but uniqueness is now a nightmare: the same triplet still surfaces from many (i, j) pairs, so you are back to sorting each triplet and hashing it just to detect that you have seen it before. The duplicates are a GLOBAL problem — you have to remember every answer you ever produced to recognise a repeat.
Sorted, the outer pair is the extreme pair.
Sort the array. Now fix a[i] and hunt inside the window [l, r] for a pair summing to target = -a[i]. Look at what a[l] + a[r] means in a sorted window. a[r] is the largest value left, so a[l] + a[r] is the BIGGEST sum that a[l] can possibly form with any partner still in the window. Symmetrically, a[l] is the smallest value left, so that same total is the SMALLEST sum a[r] can form with anyone. That double reading is the whole engine. If the sum comes out too small, then a[l] just played its strongest possible card and still fell short — no remaining partner can rescue it, so a[l] is dead for this target and you move l forward forever. If the sum comes out too big, then a[r] just played its weakest card and still overshot, so a[r] is dead and r retreats. Either way, a single comparison does not merely reject a pair — it retires an entire ELEMENT. There are only n elements to retire, so the window closes in linear time. Sorting pays a second dividend that people forget to notice. Duplicate values become adjacent, which turns uniqueness from a global bookkeeping problem into a local one: 'is this the same as the previous element?' is a comparison, not a set lookup. The de-duplication data structure disappears entirely.
Sort, fix, squeeze
O(n^2) time, O(1) extra space beyond the sort and the outputSort. For each i, skip it if a[i] equals a[i-1] (that first number's triplets have already been enumerated). Set l = i+1, r = n-1, target = -a[i], and squeeze: too small, l++; too big, r--; exact, record the triplet, then move BOTH pointers past their runs of equal values so the same triplet cannot be emitted twice.
Fix One, Squeeze the Rest
YOU'LL SEE IT AGAIN WHEN
- A target constraint pins down the last unknown exactly, so the search is really one dimension smaller than it looks.
- The answer is a set of value-combinations rather than index-combinations, which means you are free to reorder the input.
- The objective is monotone in each element, so from a sorted window a failed comparison can retire an endpoint instead of merely rejecting a pair.