Return all triples [a, b, c] from the array, at distinct positions, with a + b + c = 0. The result must not contain duplicate triples.
Before you code
Checking every triple is O(n³). After sorting, fixing the first value reduces the rest to Two sum II on a sorted range: O(n²) in total.
Hints
- Sort. For each i, run two pointers on i + 1 to the end, looking for
-nums[i]. - Skip
nums[i]if it equalsnums[i - 1]. - After recording a triple, move both pointers past equal values.
- Stop early when
nums[i] > 0: no triple starting there can sum to zero.
Production & complexity notes
When solving 3Sum on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Two pointers to reinforce the underlying pattern.
What it practices
Extending two pointers and avoiding duplicates without a set, from Two pointers.