Skip to main content

15. 3Sum

mediumAsked at Citadel

3Sum tests whether you can compose a known primitive (Two Sum) into a harder problem and handle duplicate suppression correctly. Citadel often uses it as the natural escalation after Two Sum, specifically probing your O(n²) two-pointer approach and whether you can articulate why sorting is the enabling step.

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

Source citations

Public interview reports confirming this problem appears in Citadel loops.

  • Glassdoor (2026-Q1)— Citadel SWE on-site candidates report 3Sum as a common follow-up to Two Sum in the same coding round.
  • Blind (2025-10)— Citadel threads identify the Two Sum → 3Sum escalation as a deliberate pattern in their SWE interview structure.

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 distinct triplets sum to zero.

Example 2

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

Explanation: No triplet sums to zero.

Example 3

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

Explanation: One triplet — all zeros.

Approaches

1. Sort + two pointers

Sort the array. For each index i, run a two-pointer search on the subarray [i+1, n-1]. Skip duplicates at both the outer and inner levels.

Time
O(n²)
Space
O(1) excluding output
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 outer duplicates
    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++; // skip inner dups
        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 (sort is in-place). This is the canonical solution. The sort is the enabling step — without it, duplicate suppression requires a Set and costs O(n) space per iteration.

Citadel-specific tips

Lead with: 'I'll sort first — O(n log n) — then reduce 3Sum to n instances of Two Sum II, each O(n) with two pointers, for O(n²) overall.' State this trade before touching code. Citadel interviewers specifically care about the duplicate-skipping logic — walk through the nums = [-2,-2,0,2,2] case to show you handle repeated values at all three positions. Also: can you solve it in O(n) time? No — sorting is a lower bound here; 3Sum is Θ(n²) under the decision-tree model.

Common mistakes

  • Skipping outer duplicates with if (nums[i] === nums[i+1]) instead of nums[i] === nums[i-1] — this skips the last occurrence rather than subsequent ones.
  • Not advancing lo and hi after recording a triplet — leads to an infinite loop on [0,0,0].
  • Using a Set-based deduplication instead of sorted skip — O(n) extra space and harder to reason about correctness.
  • Starting i at 1 and checking nums[i-1] without guarding i > 0 — index underflow on the first iteration.

Follow-up questions

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

  • 3Sum Closest (LC 16) — find the triplet with sum closest to target.
  • 4Sum (LC 18) — generalize to k-sum; each additional dimension adds one O(n) loop.
  • What is the minimum possible time complexity for 3Sum? (Answer: Θ(n²) — proven under comparison model.)

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 instead of using a hash map?

Sorting enables O(n) two-pointer scan per outer element and makes duplicate suppression trivial. A hash map approach requires an extra Set per iteration, costs O(n) space, and is harder to deduplicate correctly.

Why check nums[i] === nums[i-1] rather than nums[i] === nums[i+1]?

We want to skip repeated outer values after we've already processed them. Checking against the previous (not next) element ensures we process the first occurrence and skip all subsequent ones.

Can this be extended to k-Sum?

Yes — fix one element and recurse into (k-1)-Sum. k-Sum runs in O(n^(k-1)) time. For k ≥ 4, sort first, then apply nested two-pointer loops.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →