3Sum (LeetCode 15)
You have an integer array nums. Find every triplet of three distinct positions i, j, k whose values nums[i] + nums[j] + nums[k] sum to zero, and return those triplets of values.
The output must not contain the same triplet of values more than once.
Worked Examples
nums = [-1,0,1,2,-1,-4][[-1,-1,2],[-1,0,1]]nums = [0,1,1][]nums = [0,0,0][[0,0,0]]⚖️Formal Constraints & Bounds
3 <= nums.length <= 3000-105 <= nums[i] <= 105
Core Insight
Backward comparison nums[i] == nums[i-1] prevents skipping legitimate duplicate values within the first valid triplet, while eliminating duplicate triplet evaluations.
Real-World Scenario & Production Applications
Financial portfolio 3-asset arbitrage balancing, chemical compound balance equations, and zero-sum game equilibrium finding.
Subproblems & Recurrence Decomposition3 Phases
Sort nums in O(N log N) to create monotonic order. Loop anchor i from 0 to N-3, pruning if nums[i] > 0 and skipping duplicate anchors with i > 0 and nums[i] == nums[i - 1].
nums.sort()
for i in range(len(nums) - 2):
if nums[i] > 0: break
if i > 0 and nums[i] == nums[i - 1]: continueStep-by-Step Execution Trace Table
| Step | i (anchor) | left | right | sum | Action |
|---|---|---|---|---|---|
| 1 | 0 (-4) | 1 (-1) | 5 (2) | -3 | sum < 0 → left++ |
| 2 | 1 (-1) | 2 (-1) | 5 (2) | 0 | Match [-1,-1,2]! Skip dups → left++, right-- |
| 3 | 1 (-1) | 3 (0) | 4 (1) | 0 | Match [-1,0,1]! Skip dups → left++, right-- |
| 1 | nums.sort() |
| 2 | res = [] |
| 3 | for i in range(len(nums) - 2): |
| 4 | if nums[i] > 0: |
| 5 | break |
| 6 | if i > 0 and nums[i] == nums[i - 1]: |
| 7 | continue |
| 8 | left, right = i + 1, len(nums) - 1 |
| 9 | while left < right: |
| 10 | total = nums[i] + nums[left] + nums[right] |
| 11 | if total < 0: |
| 12 | left += 1 |
| 13 | elif total > 0: |
| 14 | right -= 1 |
| 15 | else: |
| 16 | res.append([nums[i], nums[left], nums[right]]) |
| 17 | left += 1 |
| 18 | right -= 1 |
| 19 | return res |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
3Sum wants every distinct-position triplet from nums whose three values add to zero. Checking every triplet directly costs time, and de-duplicating the results with a hash set burns a lot of memory. Sorting the array first in changes the shape of the problem: pin one element nums[i] as an anchor, and what's left is just Two Sum II over the sorted suffix nums[i+1..n-1].
🏟️ The Analogy: The Three-Person Committee
Imagine selecting a 3-person committee from a line of candidates arranged strictly by height. First, you appoint candidate . Then, you send two scouts to the remaining line—one starting at the shortest end and one at the tallest end—to find two candidates whose heights balance candidate 's weight. If the next candidate in line has the exact same height as candidate , appointing them would produce an identical committee, so you skip them immediately.
🔑 Why It Works
The secret to zero duplicate sets lies in two-tier duplicate suppression:
- Outer loop skips if
nums[i] == nums[i-1]. - Inner loop skips consecutive identical values after recording a match.
Duplicate triplets from anchor element: Forgetting
if i > 0 and nums[i] == nums[i - 1]: continuegenerates duplicate triplets for identical anchor values.Duplicate triplets from inner pointers: After recording a valid triplet
[nums[i], nums[left], nums[right]], you must advance both pointers past all identical elements (while left < right and nums[left] == nums[left + 1]: left += 1).Missing sort step: 3Sum relies strictly on two-pointer convergence. Forgetting
nums.sort()produces completely incorrect results in O(N^3) time.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Finding all unique triplets that sum to a target value.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: array is sorted, anchor i is unique, and inner pointers skip identical adjacent values after recording.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Checking forward duplicates: nums[i] == nums[i + 1] skips valid triplets with repeated elements like [-1, -1, 2].
Skipping inner duplicates before recording: always record the match first, then slide past duplicates.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I sort the array in
O(N log N). I iterate an anchor i from 0 to N-3, skipping duplicates where nums[i] == nums[i-1]. Inside, I run converging two pointers on [i+1..n-1]. When the sum is 0, I record the triplet and advance past identical values. Total time is O(N^2) andO(1)auxiliary space."
Complexity & Mathematical Proof
O(N^2)
Sorting takes O(N log N). The outer loop runs N times, and the inner converging two-pointer scan takes O(N) steps across the remaining suffix, giving O(N log N + N * N) = O(N^2) overall.
O(1) Auxiliary
Apart from the returned output list and O(log N) sorting call stack, only integer pointers (i, left, right) and sum accumulators are maintained in O(1) auxiliary space.
Derivation Progression
Orders elements monotonically to enable directional two-pointer decisions.
Each fixed anchor performs a linear inward scan of the remaining array.
Variable Definitions
Number of elements in nums
Memory Architecture & Bounds
O(log N) for in-place sort
O(1) 3 scalar registers
O(N^2) for unique triplets list
Boundary Best / Worst Cases
(or if earliest anchor > 0 breaks immediately).
.
full scan.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "three elements sum to zero", "solution set must not contain duplicate triplets". Dimensionality reduction () by fixing the first element and executing converging Two-Pointers on the sorted suffix.
. time budget ( operations, comfortably ms).
Early exit optimization: if nums[i] > 0, break immediately (three positive numbers can never sum to zero).
3Sum (LeetCode 15)
You have an integer array nums. Find every triplet of three distinct positions i, j, k whose values nums[i] + nums[j] + nums[k] sum to zero, and return those triplets of values.
The output must not contain the same triplet of values more than once.
Worked Examples
nums = [-1,0,1,2,-1,-4][[-1,-1,2],[-1,0,1]]nums = [0,1,1][]nums = [0,0,0][[0,0,0]]⚖️Formal Constraints & Bounds
3 <= nums.length <= 3000-105 <= nums[i] <= 105
Core Insight
Backward comparison nums[i] == nums[i-1] prevents skipping legitimate duplicate values within the first valid triplet, while eliminating duplicate triplet evaluations.
Real-World Scenario & Production Applications
Financial portfolio 3-asset arbitrage balancing, chemical compound balance equations, and zero-sum game equilibrium finding.
Subproblems & Recurrence Decomposition3 Phases
Sort nums in O(N log N) to create monotonic order. Loop anchor i from 0 to N-3, pruning if nums[i] > 0 and skipping duplicate anchors with i > 0 and nums[i] == nums[i - 1].
nums.sort()
for i in range(len(nums) - 2):
if nums[i] > 0: break
if i > 0 and nums[i] == nums[i - 1]: continueStep-by-Step Execution Trace Table
| Step | i (anchor) | left | right | sum | Action |
|---|---|---|---|---|---|
| 1 | 0 (-4) | 1 (-1) | 5 (2) | -3 | sum < 0 → left++ |
| 2 | 1 (-1) | 2 (-1) | 5 (2) | 0 | Match [-1,-1,2]! Skip dups → left++, right-- |
| 3 | 1 (-1) | 3 (0) | 4 (1) | 0 | Match [-1,0,1]! Skip dups → left++, right-- |
| 1 | nums.sort() |
| 2 | res = [] |
| 3 | for i in range(len(nums) - 2): |
| 4 | if nums[i] > 0: |
| 5 | break |
| 6 | if i > 0 and nums[i] == nums[i - 1]: |
| 7 | continue |
| 8 | left, right = i + 1, len(nums) - 1 |
| 9 | while left < right: |
| 10 | total = nums[i] + nums[left] + nums[right] |
| 11 | if total < 0: |
| 12 | left += 1 |
| 13 | elif total > 0: |
| 14 | right -= 1 |
| 15 | else: |
| 16 | res.append([nums[i], nums[left], nums[right]]) |
| 17 | left += 1 |
| 18 | right -= 1 |
| 19 | return res |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
3Sum wants every distinct-position triplet from nums whose three values add to zero. Checking every triplet directly costs time, and de-duplicating the results with a hash set burns a lot of memory. Sorting the array first in changes the shape of the problem: pin one element nums[i] as an anchor, and what's left is just Two Sum II over the sorted suffix nums[i+1..n-1].
🏟️ The Analogy: The Three-Person Committee
Imagine selecting a 3-person committee from a line of candidates arranged strictly by height. First, you appoint candidate . Then, you send two scouts to the remaining line—one starting at the shortest end and one at the tallest end—to find two candidates whose heights balance candidate 's weight. If the next candidate in line has the exact same height as candidate , appointing them would produce an identical committee, so you skip them immediately.
🔑 Why It Works
The secret to zero duplicate sets lies in two-tier duplicate suppression:
- Outer loop skips if
nums[i] == nums[i-1]. - Inner loop skips consecutive identical values after recording a match.
Duplicate triplets from anchor element: Forgetting
if i > 0 and nums[i] == nums[i - 1]: continuegenerates duplicate triplets for identical anchor values.Duplicate triplets from inner pointers: After recording a valid triplet
[nums[i], nums[left], nums[right]], you must advance both pointers past all identical elements (while left < right and nums[left] == nums[left + 1]: left += 1).Missing sort step: 3Sum relies strictly on two-pointer convergence. Forgetting
nums.sort()produces completely incorrect results in O(N^3) time.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Finding all unique triplets that sum to a target value.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: array is sorted, anchor i is unique, and inner pointers skip identical adjacent values after recording.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Checking forward duplicates: nums[i] == nums[i + 1] skips valid triplets with repeated elements like [-1, -1, 2].
Skipping inner duplicates before recording: always record the match first, then slide past duplicates.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I sort the array in
O(N log N). I iterate an anchor i from 0 to N-3, skipping duplicates where nums[i] == nums[i-1]. Inside, I run converging two pointers on [i+1..n-1]. When the sum is 0, I record the triplet and advance past identical values. Total time is O(N^2) andO(1)auxiliary space."
Complexity & Mathematical Proof
O(N^2)
Sorting takes O(N log N). The outer loop runs N times, and the inner converging two-pointer scan takes O(N) steps across the remaining suffix, giving O(N log N + N * N) = O(N^2) overall.
O(1) Auxiliary
Apart from the returned output list and O(log N) sorting call stack, only integer pointers (i, left, right) and sum accumulators are maintained in O(1) auxiliary space.
Derivation Progression
Orders elements monotonically to enable directional two-pointer decisions.
Each fixed anchor performs a linear inward scan of the remaining array.
Variable Definitions
Number of elements in nums
Memory Architecture & Bounds
O(log N) for in-place sort
O(1) 3 scalar registers
O(N^2) for unique triplets list
Boundary Best / Worst Cases
(or if earliest anchor > 0 breaks immediately).
.
full scan.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "three elements sum to zero", "solution set must not contain duplicate triplets". Dimensionality reduction () by fixing the first element and executing converging Two-Pointers on the sorted suffix.
. time budget ( operations, comfortably ms).
Early exit optimization: if nums[i] > 0, break immediately (three positive numbers can never sum to zero).