Pair and triplet sums
In one line
Sort the array, fix one element, and find the rest with two pointers: two sum becomes O(n), three sum O(n^2), and duplicates are skipped by comparing neighbours.
What it is
The k-sum family asks for pairs, triplets or quadruplets that add up to a target, or come closest to it. Two sum on an unsorted array with indices is a hash map problem; once the array is sorted (or when only the values matter), two pointers solve it in O(n) with O(1) extra space.
Three sum fixes each element in turn as the 'anchor' and runs two sum on the elements to its right, giving O(n^2). Four sum adds another loop for O(n^3). Sorting also makes duplicates adjacent, so unique combinations are produced by skipping equal neighbours.
Why interviewers ask
3Sum is one of the most frequently asked interview questions. It tests whether you can reduce a problem to a smaller one you already know, choose between hashing and sorting, and handle duplicates without a set of tuples. Getting the duplicate skipping exactly right is where most candidates slip.
How it works
- 1Sort the array: O(n log n). Equal values become neighbours and sums become predictable as pointers move.
- 2For i from 0 to n - 3: skip i if nums[i] == nums[i - 1], so each anchor value is used once. If nums[i] > 0 (target 0), stop: every remaining value is positive.
- 3Set lo = i + 1, hi = n - 1 and compute s = nums[i] + nums[lo] + nums[hi].
- 4If s < target, lo += 1. If s > target, hi -= 1. If equal, record the triplet, move both pointers, and keep moving lo while it repeats the previous value.
- 5Each anchor costs O(n) for the inner two-pointer pass, so the total is O(n^2), which dominates the sort.
- 6Closest sum variant: keep the triplet with the smallest abs(s - target) and move pointers by the same rule; generalised k-sum recurses down to two sum for O(n^(k-1)).
Worked example · 3Sum to 0 on [-1, 0, 1, 2, -1, -4]
- Sorted: [-4, -1, -1, 0, 1, 2] (indexes 0 to 5).
- i = 0 (anchor -4): lo = 1, hi = 5. Sums: -4 - 1 + 2 = -3, too small, lo = 2; -3 again, lo = 3; -4 + 0 + 2 = -2, lo = 4; -4 + 1 + 2 = -1, lo = 5. lo meets hi: nothing found.
- i = 1 (anchor -1): lo = 2, hi = 5. -1 - 1 + 2 = 0: record [-1, -1, 2]. Move to lo = 3, hi = 4.
- -1 + 0 + 1 = 0: record [-1, 0, 1]. Move to lo = 4, hi = 3: stop.
- i = 2 (anchor -1): same value as the previous anchor, skip, otherwise we would record the same triplets again.
- i = 3 (anchor 0): lo = 4, hi = 5. 0 + 1 + 2 = 3, too big, hi = 4. Stop.
- Result: [[-1, -1, 2], [-1, 0, 1]], each exactly once.
Picture it
Picking three dishes for a meal that must total exactly 30 euros from a menu sorted by price. You pick a first dish, then look for the other two by starting with the cheapest and the most expensive of the rest: if the total is too high, swap the expensive one for a cheaper one; too low, swap the cheap one for a pricier one. Then try the next first dish.
Reference code
def three_sum(nums):
nums.sort()
res = []
n = len(nums)
for i in range(n - 2):
if nums[i] > 0:
break # smallest value positive: no zero sum
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicate anchors
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 # skip duplicate second values
return res
After sorting, each anchor value is used once (duplicate anchors skipped) and the inner loop moves lo or hi based on the sum. After recording a triplet, both pointers move and lo skips repeated values, so each unique triplet is reported once. Time O(n^2); extra space O(1) besides the output and the sort (Python's sort can use up to O(n)).
Key patterns
Two sum, sorted
When: Pair with a target sum where values (or sorted indices) are enough
How: lo and hi from both ends; move by comparing the sum to the target.
Two sum, unsorted with indices
When: Original positions are needed and the array is unsorted
How: Hash map of value -> index; O(n) time, O(n) space. Sorting would lose positions.
Anchor + two sum (3Sum)
When: Triplets with a target sum, closest sum, or count below a target
How: Sort, fix i, two pointers on i + 1..n - 1; skip duplicate anchors and duplicate lo values.
Count pairs below a target
When: Number of pairs (or triplets) with sum < target
How: If nums[lo] + nums[hi] < target, all pairs (lo, lo+1..hi) qualify: add hi - lo and move lo; else move hi.
k-sum recursion
When: 4Sum and beyond
How: Fix one element and recurse to (k - 1)-sum until two sum; O(n^(k-1)). Watch integer overflow in languages with fixed-width ints.
Real-world use
Payment reconciliation
Accounting and reconciliation tools match a bank deposit against combinations of open invoices that sum to the deposited amount; for pairs and triples, sorting the invoice amounts and using two pointers is a practical way to search.
Gift cards and bundle offers
Retail features that suggest 'two or three items that use up your gift card balance' search price-sorted catalogs for combinations closest to the balance, which is the 3Sum closest problem.
Chemistry and mass spectrometry
Matching an observed mass to combinations of known fragment masses is a k-sum search over sorted mass tables, with a tolerance instead of an exact target.
Computational geometry
3Sum is a standard reference problem in complexity theory: problems like 'do any three points lie on a line' are shown to be at least as hard as 3Sum, and are usually solved in about O(n^2) time.
In a project
A food-delivery app wants a 'meal deal finder' that suggests a main, side and drink combination closest to a user's budget, from a restaurant with about 300 items.
- Split items by category and sort sides and drinks by price.
- For each main (the anchor), set the remaining budget to budget - main price and run two pointers over sides (cheapest first) and drinks (most expensive first).
- Move the drink pointer down when the total is over budget and the side pointer up when it is under, tracking the combination with the smallest difference.
- Stop early on an exact match, and filter unavailable items before sorting so the pointers only see valid items.
Impact: Instead of checking every main-side-drink combination (millions for large menus), each request runs in roughly mains * (sides + drinks) steps, so suggestions return in milliseconds and can be shown for every restaurant on the page.
Trade-offs
Use it when
- You need unique value combinations, not original indices
- O(1) extra space matters
- You want closest-sum or count-below-target variants, which hashing does not handle well
Avoid it when
- Two sum needing original indices on unsorted data: use a hash map
- The input must not be reordered and copying is too costly
- k is large: O(n^(k-1)) grows fast, so consider meet-in-the-middle or dynamic programming (subset sum)
Cost: Two sum sorted: O(n). 3Sum: O(n log n) sort + O(n^2) = O(n^2) time, O(1) extra space besides output. 4Sum: O(n^3).
Common mistakes
- Using a set of tuples to remove duplicate triplets instead of skipping neighbours; it works but wastes memory and suggests you missed the sorted structure.
- Skipping duplicates with nums[i] == nums[i + 1] instead of nums[i] == nums[i - 1], which wrongly skips valid triplets like [-1, -1, 2].
- Forgetting to move the pointers after recording a match, causing an infinite loop.
- Sorting for the classic indices-based two sum, which loses the original indices.
- Stating 3Sum as O(n log n) because of the sort; the nested two-pointer pass makes it O(n^2).
Interview questions
Quick revision
- Sort first: duplicates become neighbours, sums become monotonic.
- 3Sum = for each anchor, two sum on the right part. O(n^2).
- Skip duplicate anchors: i > 0 and nums[i] == nums[i - 1].
- After a match: lo += 1, hi -= 1, then skip repeated lo values.
- Early stop for target 0: nums[i] > 0 means no more triplets.
- Unsorted two sum with indices: hash map, not sorting.
- Count below target: add hi - lo, then lo += 1.
- k-sum is O(n^(k-1)).
Check yourself
1. What is the time complexity of the sort + two pointers 3Sum?
2. In 3Sum, which check correctly skips a duplicate anchor?
3. Sorted array [1, 2, 3, 4, 6], target 6. Which pair do two pointers return?
4. When is a hash map better than two pointers for two sum?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.