3Sum
On this page
Problem statement
Given an array of integers, return every distinct triple of values that adds up to zero. The three values must come from three different positions, and the same triple of values must not appear twice in the answer. The order of triples, and of values inside a triple, doesn't matter.
3Sum is the standard test of turning a k-sum problem into a smaller one: fix one number, then solve a sorted Two Sum on the rest. Most of the difficulty is in skipping duplicates cleanly. Original problem: LeetCode 15.
Example
![From [−1, 0, 1, 2, −1, −4] there are exactly two distinct zero-sum triples; the same values in another order count once.](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/000-c3ff910e.png)
Input: [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Input: [0, 0, 0, 0]
Output: [[0, 0, 0]] # one triple, not four
Constraints (assumed)
- 3 ≤ n ≤ 3,000.
- −10⁵ ≤ nums[i] ≤ 10⁵.
What this question tests
- Reducing 3Sum to repeated Two Sum on a sorted array.
- Using sorting both to drive two pointers and to make duplicates adjacent.
- Careful duplicate handling without a hash set of tuples.
Questions to ask first
- Distinct triples by value or by index? (Here: by value;
[-1, 0, 1]once, even if −1 appears twice.) - Can I modify the input? Sorting in place saves memory. (Here: yes.)
- Target always zero? The same method works for any target; ask in case it's a follow-up.
- How large is n? O(n²) is fine for a few thousand; the output itself can be O(n²).
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.