3Sum
Pin one value. Let order guide the others.
The challenge, in plain language +
Given a list of integers, find every distinct group of three values whose sum is zero. A group must use three different input positions, but equal values are allowed when enough copies exist. Return each triple in ascending order and return the triples in lexicographic order, without duplicates. Leave the original list unchanged.
How do you turn the three-value search into a reusable two-pointer search?
This lesson uses 2D: exact positions, widths and comparisons are easier to read in one plane.
Why this approach works
For a fixed anchor, every not-yet-eliminated pair lies between left and right. If the current sum is negative, every remaining pair using this left value with a right index no larger than the current right is also negative. If the sum is positive, every remaining pair using this right value with a left index no smaller than the current left is also positive. Equal-value skips remove only repeated value triples.
Each anchor performs a linear inward scan; across O(n) anchors this is O(n²). Sorting is O(n log n). The pointers themselves need O(1) space, but these solutions sort a copy, so their auxiliary space is O(n). Python's sort and common JavaScript sort implementations may also use linear temporary storage. Returned results use O(k) space, with k up to O(n²); never label these complete implementations O(1) space.
Common failure: Sorting JavaScript numbers without a numeric comparator. Default sorting compares strings and breaks the ordered-sum reasoning.
A fresh solve is the test.
Loading your saved attempts…