-
Notifications
You must be signed in to change notification settings - Fork 0
042 — 3Sum
LeetCode 15 · Medium. Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] (with distinct indices) such that they sum to zero. The solution set must not contain duplicate triplets.
Picture a tug-of-war rope laid along a number line, with markers at various sorted positions — positive markers pulling right, negative markers pulling left. You need to find exactly three markers whose combined pull cancels out perfectly to zero. Here's the trick: lock in one marker as an anchor. Once that marker is fixed, the question "which two other markers cancel it out?" is just "which two markers sum to -anchor?" — and that's a problem you already know how to solve: it's Two Sum II, the sorted two-pointer pair-matching problem, with target = -anchor instead of some given number. Do that once for every possible anchor position (skipping anchors you've already tried), and you've found every triplet — without ever comparing three markers by brute force all at once.
"Find all triplets (or all k-element combinations) that sum to a target" is the signal to reduce k-Sum down to (k-1)-Sum, recursively, until you hit the base case of Two Sum — which, once the array is sorted, collapses to Two Pointers. Sorting first buys you two things at once here: it's what makes the two-pointer collapse possible for the inner pair search, and it's what makes duplicate-skipping cheap, since sorting puts every group of equal values right next to each other.
Check every triplet of indices, and use a set to discard duplicate triplets.
func threeSumBruteForce(_ nums: [Int]) -> [[Int]] {
var uniqueTriplets = Set<[Int]>()
let n = nums.count
for i in 0..<n {
for j in (i + 1)..<n {
for k in (j + 1)..<n {
if nums[i] + nums[j] + nums[k] == 0 {
let triplet = [nums[i], nums[j], nums[k]].sorted()
uniqueTriplets.insert(triplet)
}
}
}
}
return Array(uniqueTriplets)
}Big-O: O(n³) time from the triple-nested loop over every possible triplet. O(n) extra space for the dedup set, beyond the output itself.
Sort the array. Walk an anchor index across it; for each anchor, run a Two-Pointer sweep across the remainder of the array looking for a pair that sums to -anchor, skipping duplicate anchors and duplicate pair values as you go.
func threeSum(_ nums: [Int]) -> [[Int]] {
let sorted = nums.sorted()
var result = [[Int]]()
let n = sorted.count
for i in 0..<n {
if sorted[i] > 0 { break } // sorted ascending: no anchor from here on can reach zero
if i > 0 && sorted[i] == sorted[i - 1] { continue } // skip duplicate anchors
var left = i + 1
var right = n - 1
let target = -sorted[i]
while left < right {
let sum = sorted[left] + sorted[right]
if sum == target {
result.append([sorted[i], sorted[left], sorted[right]])
left += 1
right -= 1
while left < right && sorted[left] == sorted[left - 1] {
left += 1 // skip duplicate low values
}
while left < right && sorted[right] == sorted[right + 1] {
right -= 1 // skip duplicate high values
}
} else if sum < target {
left += 1
} else {
right -= 1
}
}
}
return result
}Big-O: O(n log n) to sort, then O(n) anchors each running an O(n) two-pointer sweep, giving O(n²) overall (the sort is dominated by this term). O(n) space for the sorted copy, not counting the output.
The brute force treats 3Sum as "check every group of 3," which is inherently O(n³). But once you fix any one element as an anchor, the remaining question — "do two other elements cancel this one out?" — is exactly the sorted pair-sum problem from Two Sum II, solvable in O(n) with two pointers instead of an O(n²) nested loop. Running that O(n) sub-solve once per anchor turns the whole triple-nested search into O(n) × O(n) = O(n²). Sorting is what makes both halves of this work: it unlocks the two-pointer collapse for the inner search, and it makes "skip if equal to the previous value" enough to guarantee uniqueness, replacing the brute force's Set.
- Two Pointers — the converging-pointer sweep used for each anchor's inner search.
- Arrays & Strings — the array being sorted and scanned.
- Two Sum II — the exact sorted pair-sum sub-problem 3Sum is built on top of.
3Sum is a tug-of-war rope: anchor one marker, then two-pointer the rest to cancel it out to zero — and skip repeats so nobody pulls the same triplet twice.
The optimal solution breaks out of the outer loop entirely once sorted[i] > 0, rather than just continue-ing to the next anchor. Why is break provably correct here rather than merely a helpful shortcut, given the array is sorted ascending? What specifically would go wrong if you tried this same break on an unsorted array?
⬅️ Previous: Two Sum II - Input Array Is Sorted · Next: Container With Most Water ➡️