Jump to section
Three Sum asks for every unique triplet in an array that adds up to zero. The standard solution sorts the array, fixes one number at a time, and finds pairs for it with two pointers moving inward, skipping duplicates as it goes. It runs in O(n²) time and O(1) extra space beyond the sort and the output.
The Three Sum Problem
You are given an array of integers. Return every distinct triplet of values [a, b, c], taken from three different positions, where a + b + c = 0. The result must not contain the same triplet twice, even if the input has repeated values. The order of the triplets usually does not matter.
Example 1
Input: [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Why: both triplets sum to zero. [0, 1, -1] would also sum to zero, but it is the same set of values as [-1, 0, 1], so it is not listed again.
Example 2
Input: [0, 0, 0, 0]
Output: [[0, 0, 0]]
Why: there are four ways to pick three zeros, but they are all the same triplet of values.
Assumptions to confirm
- Return values or indexes? (Values, in the classic version.)
- Is the target always zero? (Often yes; the same method works for any target.)
- May I sort or modify the input? (Sorting is the key step, so ask, or sort a copy.)
Start With the Brute Force
The direct approach tries every combination of three positions with three nested loops, and uses a set of sorted triplets to drop duplicates. It is O(n³) time, which is too slow for inputs of a few thousand elements.
A better middle step reuses Two Sum: fix one number, then look for a pair that adds up to its negative with a hash set. That is O(n²), but de-duplicating the results is awkward. Sorting first gives the same O(n²) with much simpler duplicate handling, which is why it is the expected answer.
Ready to put this into practice?
Practice this with MockIF →Still applying for jobs? Let Auto Apply do it
The Optimal Approach: Sort, Then Two Pointers
Sort the array
Sorted order lets two pointers decide which way to move, and puts duplicates next to each other so they are easy to skip.
Fix the first number at index i
Skip i if it equals the previous value, so each first number is used once. If nums[i] is positive, stop: three numbers that are all at least nums[i] cannot sum to zero.
Move two pointers inward
Start lo just after i and hi at the end. If the sum is too small, move lo right; if too large, move hi left.
Record a match and skip repeats
When the sum is zero, save the triplet, move both pointers, then keep moving lo while it points at the same value as before.
Repeat for every i
Each fixed number costs O(n) for the pointer scan, so the whole loop is O(n²).
Three Sum in Python and TypeScript
Both versions sort a copy, so the caller’s array is left unchanged. In TypeScript, pass a comparator to sort: the default sort compares numbers as strings.
Python
def three_sum(nums: list[int]) -> list[list[int]]:
nums = sorted(nums)
result: list[list[int]] = []
for i in range(len(nums) - 2):
if nums[i] > 0:
break # the smallest number is positive, so no sum can reach 0
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicate first numbers
lo, hi = i + 1, len(nums) - 1
while lo < hi:
total = nums[i] + nums[lo] + nums[hi]
if total < 0:
lo += 1
elif total > 0:
hi -= 1
else:
result.append([nums[i], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
return resultTypeScript
function threeSum(input: number[]): number[][] {
const nums = [...input].sort((a, b) => a - b);
const result: number[][] = [];
for (let i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) break; // the smallest number is positive, so no sum can reach 0
if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicate first numbers
let lo = i + 1;
let hi = nums.length - 1;
while (lo < hi) {
const total = nums[i] + nums[lo] + nums[hi];
if (total < 0) lo++;
else if (total > 0) hi--;
else {
result.push([nums[i], nums[lo], nums[hi]]);
lo++;
hi--;
while (lo < hi && nums[lo] === nums[lo - 1]) lo++;
}
}
}
return result;
}Ready to put this into practice?
Practice this with MockIF →Still applying for jobs? Let Auto Apply do it
Time and Space Complexity
| Approach | Time | Space | When to use it |
|---|---|---|---|
| Three nested loops | O(n³) | O(n) for the de-duplication set | Tiny inputs only |
| Fix one, hash set for the pair | O(n²) | O(n) | When the input must not be reordered |
| Sort + two pointers | O(n²) | O(1) beyond the sort and output | The expected interview answer |
How to Talk Through It in an Interview
- Clarify: "Values, not indexes? No duplicate triplets? Can I sort?"
- Brute force: "Three nested loops find every triplet in O(n cubed), with a set to remove duplicates."
- Optimise: "If I fix one number, the rest is Two Sum for its negative. On a sorted array that is a two-pointer scan, so the total is O(n squared), and sorting puts duplicates side by side so I can skip them."
- Code: explain each skip: duplicate first numbers, and duplicate second numbers after a match. These are where most bugs live.
- Test: [-1, 0, 1, 2, -1, -4], all zeros, a case with no answer such as [0, 1, 1], and one with several matches for the same first number.
Ready to put this into practice?
Practice this with MockIF →Still applying for jobs? Let Auto Apply do it
Edge Cases and Common Follow-Ups
Duplicate triplets
The most common bug. Skip a repeated first number before the scan and a repeated second number after each match.
Fewer than three elements
The loop simply does not run and the result is empty.
Any target instead of zero
Compare the sum with the target instead of zero. The early stop for positive numbers only applies when the target is zero.
Three Sum Closest
Same scan, but track the sum with the smallest distance to the target instead of exact matches.
Four Sum
Add one more outer loop: fix two numbers, then two pointers, for O(n³).
Practise Three Sum in a Mock Coding Round
Reading a solution is not the same as producing one with someone listening. The gap shows up as long silences, a jump straight to code without a brute force, or a bug you only spot after the interviewer asks you to test. The fix is to rehearse problems like Three Sum out loud, under time pressure, while explaining each decision.
MockIF runs mock coding interviews with a voice AI interviewer in a real in-browser editor, in Python and TypeScript. It runs your code against tests, asks you to explain your approach, adds follow-up questions the way a real interviewer would, and then scores your answer and gives specific feedback. Each session costs 2 credits. It is free to start with 5 credits, then monthly or 3-monthly plans, or one-off credit packs (see pricing).
Frequently Asked Questions
What is the time complexity of Three Sum?
How do you avoid duplicate triplets in Three Sum?
Can Three Sum be solved faster than O(n²)?
How is Three Sum related to Two Sum?
Why does the TypeScript version pass a comparator to sort?
Stop Preparing in Your Head. Start Practicing Out Loud.
Drop your resume, add a job description, and get a mock interview like the real thing.
Start Free Mock Interview →Still applying for jobs? Let Auto Apply do it for you.