Skip to main content

35. 3Sum

mediumAsked at Workday

Find all unique triplets in an array that sum to zero. Workday uses this as a sort + two-pointer composition test — same shape as 'find three pay-grade adjustments that net to zero'.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2026-Q1)— Workday SDE2 onsite.
  • Blind (2025)— Workday compensation team interview.

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. Triple loop with set dedup

Try every (i, j, k); dedup by sorting each triplet.

Time
O(n^3)
Space
O(unique triplets)
// triple loop, push sorted triplet into a set keyed by JSON

Tradeoff: Cubic. Won't pass n=3000.

2. Sort + fix one + two-pointer

Sort. For each i, run two pointers on the rest to find sum = -nums[i]. Skip duplicates carefully.

Time
O(n^2)
Space
O(1) extra)
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 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^2). The skip-duplicate steps after a match are the part candidates get wrong.

Workday-specific tips

Workday grades for duplicate handling. There are THREE places: skipping duplicates at the outer i, skipping at lo after a match, and skipping at hi after a match. Walk all three out loud — missing one gives duplicate triplets.

Common mistakes

  • Skipping i duplicates but forgetting lo/hi after a match.
  • Skipping at lo BEFORE finding a match — drops valid triplets like [0,0,0].
  • Not sorting first — two-pointer trick requires sorted input.

Follow-up questions

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

  • 3Sum Closest (LC 16) — find triplet closest to target.
  • 4Sum (LC 18) — extend by one more loop.
  • 3Sum with Multiplicity (LC 923).

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 three duplicate-skip places?

Sorted duplicates can sit adjacent at any of the three positions. Skipping only at i would still emit [x, y, y] -> [x, y2, y3] for repeated y. All three skips are needed.

Why sort?

Sorting enables the two-pointer pattern (sum too small -> move lo right; too big -> move hi left). Without sort, you'd need an extra hash map and the duplicate handling gets messier.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →