Skip to main content

15. 3Sum

mediumAsked at DoorDash

Given an integer array, return all unique triplets that sum to zero. DoorDash uses 3Sum as the canonical 'sort + two-pointer' problem — they want clean dedupe logic and the O(n^2) bound.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports list 3Sum as a recurring 2-pointer + sort question.
  • Blind (2025-12)— DoorDash new-grad reports note the dedupe step as the actual interview signal.

Problem

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and 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]]

Example 2

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

Example 3

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

Approaches

1. Sort + two-pointer with dedupe (optimal)

Sort. For each i, use two pointers l, r to find pairs that sum to -nums[i]. Skip duplicates at i and after each successful triplet.

Time
O(n^2)
Space
O(1) extra (sort in place)
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;
    let l = i + 1, r = nums.length - 1;
    while (l < r) {
      const sum = nums[i] + nums[l] + nums[r];
      if (sum < 0) l++;
      else if (sum > 0) r--;
      else {
        result.push([nums[i], nums[l], nums[r]]);
        while (l < r && nums[l] === nums[l + 1]) l++;
        while (l < r && nums[r] === nums[r - 1]) r--;
        l++; r--;
      }
    }
  }
  return result;
}

Tradeoff: DoorDash's preferred answer. Two-pointer per fixed i gives O(n^2). Dedupe at three places: outer (i), inner l, inner r. Missing any of these returns duplicates.

2. Hash set with explicit dedupe

For each pair (i, j), check if -(nums[i] + nums[j]) is in the array. Sort each triplet to canonicalize, then dedupe.

Time
O(n^2)
Space
O(n^2) for dedupe set
function threeSumHash(nums) {
  const result = new Set();
  const sorted = [...nums].sort((a, b) => a - b);
  for (let i = 0; i < sorted.length; i++) {
    const seen = new Set();
    for (let j = i + 1; j < sorted.length; j++) {
      const need = -(sorted[i] + sorted[j]);
      if (seen.has(need)) {
        result.add(`${sorted[i]}_${need}_${sorted[j]}`);
      }
      seen.add(sorted[j]);
    }
  }
  return [...result].map((s) => s.split('_').map(Number));
}

Tradeoff: Same complexity but uses O(n^2) space for the dedupe set. Two-pointer is cleaner and uses O(1) extra.

DoorDash-specific tips

DoorDash interviewers grade on the DEDUPE LOGIC. State 'I'll skip duplicates at i, then after each found triplet I'll skip duplicates at both pointers' BEFORE coding. The three skip points are the actual interview signal.

Common mistakes

  • Forgetting the outer-loop dedupe (nums[i] same as nums[i-1] returns the same triplet).
  • Forgetting the inner-loop dedupe after a triplet is found.
  • Returning the values without sorting first — different orderings count as duplicates.

Follow-up questions

An interviewer at DoorDash may pivot to one of these next:

  • Two Sum II (LC 167) — the warm-up two-pointer.
  • 4Sum (LC 18) — extend with one more outer loop.
  • 3Sum Closest (LC 16) — minimize |sum - target|.

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 sort first?

Sorting enables both the two-pointer convergence (sum < 0 -> l++, sum > 0 -> r--) and the dedupe by comparing adjacent values.

Can I break early?

Yes — if nums[i] > 0, sorted means all subsequent values are too. No way to sum to 0 with two non-negatives + a positive. Break.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →