3Sum
Given an integer array, return all unique triplets of elements whose sum is zero. The same triplet must not appear twice in the output, though the array may contain duplicates.
- 3 ≤ n ≤ 3000
- -10^5 ≤ nums[i] ≤ 10^5
- Sorting is allowed since only values matter, not indices
- After fixing one element it becomes a *sorted* two-sum
- Duplicates must be skipped — easy with sorted neighbors
When order gives you a way to decide which of two ends to move, you can replace an O(n^2) double loop by a single pass. Opposite-direction pointers exploit sortedness (move the side that must change); same-direction pointers maintain a "written so far" prefix for in-place compaction.
Sort the array. For each index i (skipping values equal to the previous), search for pairs summing to -nums[i] in the suffix using two pointers l = i + 1 and r = n - 1: move l right if the sum is too small and r left if too large. On a hit, record the triplet and advance both pointers past any duplicate values. The sort guarantees pointer moves discard only impossible pairs.
- A hash set per fixed element also gives O(n^2) but makes deduplication awkward. Brute force is O(n^3).