3Sum
Return all unique triplets [a, b, c] from nums that sum to 0. The solution set must not contain duplicate triplets.
Intuition
Sorting unlocks two tricks: it lets a left/right pointer pair converge by sum, and it groups duplicates together so we can skip them. Fix one number, then two-pointer the rest of the array for a pair completing zero.
When a problem asks for k numbers hitting a target and order doesn't matter, sorting is almost always step one — it makes duplicates adjacent (so they're skippable) and makes the sum respond monotonically to moving a pointer. The general recipe: fix k - 2 indices with loops, then two-pointer the innermost pair. That turns 3Sum into O(n²) and 4Sum into O(n³).
Approach
Brute force, and the two problems it has
The obvious approach is three nested loops testing every triplet for a zero sum — O(n³). It has two pains: it's slow, and it produces the same triplet in many orders ([-1,0,1], [0,1,-1], …), so you'd need a set to dedupe. Both pains have the same root cause: the array has no order, so we can neither search efficiently nor recognize duplicates. That points at the fix — impose order by sorting.
Sorting unlocks a directional two-pointer search
Once the array is sorted, fix one number as an anchor at index i, and reduce the problem to “find a pair in the suffix that sums to −nums[i].” In a sorted array you can do that with two pointers, l just after the anchor and r at the end: compute the three-sum and let its sign steer you. Too small? The only way to grow it is to move l right to a larger value. Too big? Move r left to a smaller value. Exactly zero? Record it. This works because sorting guarantees moving l right never decreases the sum and moving r left never increases it — the search is monotonic, so each anchor costs only O(n).
Killing duplicates, and one early exit
Sorting also clusters equal values, which makes deduping cheap. Skip an anchor if it equals the previous anchor (nums[i] == nums[i−1]), since it would regenerate the same triplets. After recording a hit, advance l and r past any values equal to the ones just used, so each distinct pair is emitted once. Finally, because the array is sorted, the moment nums[i] > 0 the anchor and everything after it are positive and can't sum to zero — so we break. Total: O(n log n) sort plus O(n²) scanning.
Solution & live demo
Common pitfalls
Using a set to dedupe instead of skipping
res = set() ... res.add((nums[i], nums[l], nums[r]))
if i > 0 and nums[i] == nums[i - 1]:
continue
...
while l < r and nums[l] == nums[l - 1]:
l += 1It gives the right answer but does the work anyway — you still generate every duplicate triple and pay hashing on top. Worse, it hides the real insight: after sorting, equal values sit next to each other, so a duplicate is recognisable in O(1) and can be stepped over before any work happens.
Skipping duplicates without the l < r guard
while nums[l] == nums[l - 1]:
l += 1while l < r and nums[l] == nums[l - 1]:
l += 1On a run like [0, 0, 0, 0] the pointer walks straight past r and off the end of the array. The bound has to be re-checked on every step of the skip, not just before it.
Moving only one pointer after recording a hit
res.append([nums[i], nums[l], nums[r]]) l += 1
res.append([nums[i], nums[l], nums[r]]) l += 1 r -= 1
With nums[l] advanced and nums[r] fixed, the sum can only rise above the target, so the next iteration immediately pulls r back — it terminates, but it wastes a pass. Since the current pair is used up, both ends should move together.
Edge cases
Anchor- and pointer-level skips ensure [0,0,0] is emitted exactly once.
The pointers exhaust every anchor without a hit and the result stays empty.
The nums[i] > 0 early break and pointer logic quickly conclude no triplet is possible.