Skip to main content

15. Three Sum

mediumAsked at Robinhood

Given 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 Alex Chen, 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

Input
nums = [-1,0,1,2,-1,-4]
Output
[[-1,-1,2],[-1,0,1]]

Explanation: Two unique triplets sum to 0.

Example 2

Input
nums = [0,1,1]
Output
[]

Example 3

Input
nums = [0,0,0]
Output
[[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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Three Sum and other Robinhood interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →