Skip to main content

15. 3Sum

mediumAsked at DRW

DRW asks 3Sum to test whether candidates can combine sorting with two-pointer sweeps and suppress duplicates without extra memory. In trading contexts this pattern appears in three-asset arbitrage detection: find all triplets of prices summing to zero profit after costs.

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

Source citations

Public interview reports confirming this problem appears in DRW loops.

  • Glassdoor (2026-Q1)— DRW SWE onsite candidates report 3Sum as a frequent medium-difficulty coding question, often paired with Two Sum as the prior warm-up.
  • Blind (2025-11)— DRW interview threads cite 3Sum as a test of duplicate-suppression discipline — interviewers mark down candidates who reach for a Set without explaining the O(n²) two-pointer approach first.

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: Sort first, then for each i use two pointers on the remainder.

Example 2

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

Explanation: No triplet sums to 0.

Example 3

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

Explanation: Single valid triplet.

Approaches

1. Sort + two pointers

Sort the array. For each index i, run a two-pointer sweep over the remaining suffix. Skip duplicates at each level to avoid duplicate triplets.

Time
O(n²)
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; // skip duplicate i
    if (nums[i] > 0) break; // sorted: no triplet can sum to 0
    let lo = i + 1, hi = nums.length - 1;
    while (lo < hi) {
      const sum = nums[i] + nums[lo] + nums[hi];
      if (sum === 0) {
        result.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 (sum < 0) {
        lo++;
      } else {
        hi--;
      }
    }
  }
  return result;
}

Tradeoff: O(n²) time, O(1) extra space. This is the canonical answer. The duplicate-skipping logic at each of the three levels is what separates a correct solution from one that passes only some test cases.

DRW-specific tips

DRW interviewers want to see the three-level duplicate suppression before they see any code: '(1) skip duplicate i values, (2) skip duplicate lo values after a hit, (3) skip duplicate hi values after a hit.' Missing any one level produces wrong output on arrays with repeated elements. They will also ask: 'What is the expected number of valid triplets in a length-n array of uniformly random integers in [−k, k]?' — frame it as a birthday-problem variant.

Common mistakes

  • Forgetting to skip duplicate i values — produces repeated triplets like [[-1,-1,2],[-1,-1,2]].
  • Not skipping duplicate lo and hi values after finding a match — same problem inside the inner loop.
  • Sorting with the default JS comparator (lexicographic) — always pass (a,b) => a - b for numeric sort.
  • Using a Set of triplet strings for deduplication instead of the in-place skip — correct but hides the O(n²) elegance DRW expects.

Follow-up questions

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

  • 3Sum Closest (LC 16) — find the triplet sum closest to a target value.
  • 4Sum (LC 18) — generalize to four numbers; O(n³) with the same sort + nested two-pointer pattern.
  • How would you detect three-leg arbitrage across currency pairs where the product of exchange rates equals 1?

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 the two-pointer sweep, which collapses the inner O(n²) search into O(n). It also makes duplicate suppression trivial — identical values are adjacent.

Can you break early in the outer loop?

Yes: if nums[i] > 0 after sorting, no triplet starting at i can sum to 0 (all remaining values are also positive). This cuts work in practice for arrays with many positives.

What is the time complexity lower bound?

O(n²) in the worst case — you may need to enumerate O(n²) output triplets. You cannot do better than O(n²) for the general case.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →