Three Sum
Given an array of integers nums, return all unique triplets [a, b, c] drawn from elements at distinct indices such that a + b + c == 0.
Implement the function:
```python def three_sum(nums): ```
The answer must be canonical and gradable: - Each triplet is sorted ascending: a <= b <= c. - The list of triplets is sorted in ascending (lexicographic) order. - No duplicate triplets appear (values, not indices, determine duplicates).
Return the list of triplets (a list of lists). If none exist, return an empty list.
Example
three_sum([-1, 0, 1, 2, -1, -4]) -> [[-1, -1, 2], [-1, 0, 1]]
Sorting the input gives [-4, -1, -1, 0, 1, 2]; the two zero-sum triplets are [-1, -1, 2] and [-1, 0, 1], listed in lexicographic order with duplicates removed.
Hints
- Fixing one element reduces the problem to finding two numbers that sum to a target -- this is the classic two-sum problem.
- Sort the array first. For a sorted array, two-sum can be solved in $O(n)$ using two pointers converging from both ends.
- The trickiest part is handling duplicates. Skip repeated values at the outer loop (
nums[i] == nums[i-1]) and at both inner pointers after finding a match.
Worked Solution
Approach. Sort the array, then for each index i run a two-pointer scan over the remaining suffix. Because the array is sorted, moving lo right increases the sum and moving hi left decreases it, so each fixed i is solved in O(n). Skip repeated values at i, lo, and hi to avoid duplicate triplets. Overall time is O(n^2).
Since the input is sorted first, triplets are naturally emitted in ascending lexicographic order and each triplet is already ascending, matching the required canonical form.
```python def three_sum(nums): nums = sorted(nums) n = len(nums) res = [] for i in range(n - 2): if i > 0 and nums[i] == nums[i - 1]: continue lo, hi = i + 1, n - 1 while lo < hi: s = nums[i] + nums[lo] + nums[hi] if s < 0: lo += 1 elif s > 0: hi -= 1 else: res.append([nums[i], nums[lo], nums[hi]]) lo += 1 hi -= 1 while lo < hi and nums[lo] == nums[lo - 1]: lo += 1 while lo < hi and nums[hi] == nums[hi + 1]: hi -= 1 return res ```
Intuition
Three-sum is one of the most common interview problems because it tests multiple skills at once: recognizing that a higher-order problem reduces to a simpler one (three-sum to two-sum), knowing that sorting unlocks efficient techniques (two pointers), and handling the fiddly implementation detail of deduplication.
The broader pattern -- fix one variable, solve the reduced problem efficiently -- appears constantly in algorithm design. Four-sum reduces to three-sum, which reduces to two-sum. In quantitative finance, a similar decomposition shows up when you optimize over multiple instruments: fix one position, optimize the rest, then sweep over the fixed variable. The two-pointer technique itself is a workhorse for any sorted-array problem where you are searching for pairs satisfying a constraint.