14. 3Sum
mediumAsked at Postman3Sum asks for every unique triplet in an integer array that sums to zero — the canonical sort-plus-two-pointer problem and one of the most-reported medium screens in the industry. Postman candidates describe it as a test of duplicate discipline: anyone can find triplets, but cleanly skipping repeats at all three positions without a Set crutch is what separates a pass from a 'mostly worked'.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Postman loops.
- LeetCode (2026)— Problem #15 '3Sum' — canonical statement, constraints, and medium difficulty rating; among the highest-frequency interview problems site-wide.
- Google Search Console (InterviewChamp) (2026-Q2)— Live search-demand data shows candidates searching this problem paired with Postman interview prep.
Problem
Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c = 0 and the indices are distinct. The result must not contain duplicate triplets, regardless of how many index combinations produce them.
Constraints
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5Output order does not matter, but each value-triplet may appear only once.
Examples
Example 1
nums = [-1,0,1,2,-1,-4][[-1,-1,2],[-1,0,1]]Explanation: Two distinct value-triplets sum to zero. Note [-1,0,1] appears via multiple index combinations but is listed once — that is the dedupe requirement in action.
Example 2
nums = [0,0,0][[0,0,0]]Explanation: All three zeros form the only triplet; duplicate-skipping must not discard the legitimate all-equal case.
Approaches
1. Triple loop
Enumerate every triple and use a Set of sorted-string keys to dedupe.
- Time
- O(n^3)
- Space
- O(n^2)
function threeSum(nums) {
const seen = new Set();
const out = [];
for (let i = 0; i < nums.length; i++)
for (let j = i + 1; j < nums.length; j++)
for (let k = j + 1; k < nums.length; k++)
if (nums[i] + nums[j] + nums[k] === 0) {
const key = [nums[i], nums[j], nums[k]].sort((a, b) => a - b).join(',');
if (!seen.has(key)) {
seen.add(key);
out.push(key.split(',').map(Number));
}
}
return out;
}Tradeoff: Cubic time with a Set holding up to O(n^2) keys — at n = 3000 that is ~4.5 billion triple checks, far past any time limit. State it only to frame the optimization, then move on within a sentence.
2. Sort + two-pointer
Sort the array; for each fixed i, walk lo and hi pointers inward, skipping duplicates on all three positions.
- Time
- O(n^2)
- Space
- O(1)
function threeSum(nums) {
nums.sort((a,b)=>a-b);
const out = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i-1]) continue;
let lo = i+1, hi = nums.length - 1;
while (lo < hi) {
const s = nums[i] + nums[lo] + nums[hi];
if (s === 0) {
out.push([nums[i], nums[lo], nums[hi]]);
while (lo < hi && nums[lo] === nums[lo+1]) lo++;
while (lo < hi && nums[hi] === nums[hi-1]) hi--;
lo++; hi--;
} else if (s < 0) lo++;
else hi--;
}
}
return out;
}Tradeoff: Quadratic time, constant extra space, and dedupe comes free from sorted order instead of a Set — that trade (one O(n log n) sort buys ordered scanning AND duplicate-skipping) is the exact sentence interviewers want to hear before you code.
Postman-specific tips
Postman candidates report the grading weight on the dedupe-skip pattern being verbalized, not just typed: 'after sorting, equal neighbors produce identical triplets, so I advance past repeats at i, lo, and hi.' If the conversation invites it, the domain analogy is natural for an API platform — deduplicating repeated header sets or query parameters before signing a request is the same skip-equal-neighbors shape. Expect the 'why sort first?' follow-up: sorting costs O(n log n) but unlocks both the two-pointer walk and free deduplication.
Common mistakes
- Skipping duplicates only at position i and forgetting lo/hi — output then contains repeated triplets and fails the judge.
- Skipping duplicates BEFORE checking the sum at lo/hi — you can jump past the only valid pairing; record the triplet first, then skip.
- Off-by-one in the i-loop bound (nums.length - 2) — lo and hi need at least two slots to the right of i.
- Reaching for a Set of stringified triplets in the optimal solution — it works, but it signals you did not see that sorted order makes deduplication free.
Follow-up questions
An interviewer at Postman may pivot to one of these next:
- 3Sum Closest (LC 16): same two-pointer walk, but track the minimum |sum - target| instead of exact zero.
- 4Sum (LC 18): one more outer loop plus the identical inner pattern — generalize to kSum recursively.
- Two Sum II on a sorted array (LC 167): the inner two-pointer subroutine in isolation — useful to name as the building block.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does sorting make deduplication free?
After sorting, any duplicate triplet must use equal values in equal positions, and equal values sit adjacent. Skipping equal neighbors at i, lo, and hi therefore eliminates every duplicate without hashing or post-processing.
Can 3Sum be solved faster than O(n^2)?
No materially better bound is known — 3Sum is the namesake of the '3SUM-hard' complexity class, and subquadratic algorithms are only slightly better in theory. O(n^2) with O(1) space is the accepted interview optimum.
Why not fix the two outer values and binary-search the third?
That works but costs O(n^2 log n) and still needs dedupe handling. The two-pointer inward walk does the search in O(n) per fixed i, which is strictly better and simpler to reason about.