15. Three Sum
mediumAsked at RobinhoodGiven an array of integers, find all unique triplets that sum to zero. Robinhood asks this as the universal follow-up to Two Sum — they want to see the sort + fix-one + two-pointer pattern executed cleanly with duplicate handling.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Robinhood loops.
- Glassdoor (2026-Q1)— Robinhood SWE phone-screen reports list Three Sum as the universal follow-up after Two Sum.
- Blind (2025-11)— Robinhood new-grad onsite trip reports cite Three Sum and Four Sum as recurring.
Problem
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.
Constraints
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
Examples
Example 1
nums = [-1,0,1,2,-1,-4][[-1,-1,2],[-1,0,1]]Explanation: Two unique triplets sum to 0.
Example 2
nums = [0,1,1][]Example 3
nums = [0,0,0][[0,0,0]]Approaches
1. Brute-force triple loop
Try every (i, j, k) triple. Use a set to deduplicate.
- Time
- O(n^3)
- Space
- O(unique triplets)
function threeSumBrute(nums) {
const seen = new Set();
const result = [];
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 triple = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
const key = triple.join(',');
if (!seen.has(key)) {
seen.add(key);
result.push(triple);
}
}
}
}
}
return result;
}Tradeoff: Cubic. Mention it as the brute-force baseline, then pivot to sort + two-pointer.
2. Sort + fix-one + two-pointer (optimal)
Sort the array. Fix the leftmost element with a loop. Use two-pointer (left, right) over the rest to find pairs summing to -nums[i].
- Time
- O(n^2)
- Space
- O(1) extra (output excluded)
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
if (nums[i] > 0) break; // smallest > 0 means no zero-sum possible
let left = i + 1, right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}Tradeoff: O(n^2) — n iterations of fixed-i, each running an O(n) two-pointer scan. Duplicate-skipping at three levels (i, left, right) keeps the output deduplicated without a Set.
Robinhood-specific tips
Robinhood interviewers reliably probe three things on Three Sum: (1) duplicate skipping at all three levels — i, left, and right; (2) the early break when nums[i] > 0; (3) why sort is required (the two-pointer move-inward proof needs sorted input). Articulate all three out loud. Skipping the dedupe at any level is the #1 bug.
Common mistakes
- Forgetting to dedupe at any of the three levels — gives duplicate triplets.
- Using a Set to dedupe at the end — works but wastes memory; sort+skip is cleaner.
- Forgetting that the result is an array of triplets, not a count.
- Off-by-one on the i loop bound (must be < n - 2 to leave room for left and right).
Follow-up questions
An interviewer at Robinhood may pivot to one of these next:
- Three Sum Closest (LC 16) — return the closest sum to a target.
- Three Sum Smaller (LC 259) — count triplets summing strictly less than target.
- Four Sum (LC 18) — generalizes; fix two and two-pointer.
- K Sum — generalize to arbitrary k.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does sort enable two-pointer?
After sorting, if nums[left] + nums[right] is too small, the only way to grow it is left++. If too large, right--. This rules out one of the two pointers per step — O(n) for each fixed i.
Why the nums[i] > 0 early break?
Once the smallest of the three is positive, the sum is positive — no triplet sums to zero. Bail early to save work on long positive tails.
Free learning resources
Curated free links for this problem.