Skip to main content

18. 4Sum

mediumAsked at Netflix

Given an array of n integers and a target, return all unique quadruples (a, b, c, d) summing to target. Netflix asks this to see whether you generalize the k-sum pattern recursively and handle duplicate skipping cleanly enough to avoid an O(n^4) blow-up.

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

Source citations

Public interview reports confirming this problem appears in Netflix loops.

  • Glassdoor (2026-Q1)— Netflix mid-level loop reports cite 4Sum as a follow-up after 3Sum on the same screen.
  • Blind (2025-10)— Netflix SWE reports describe a k-sum generalization variant of this problem.

Problem

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that 0 <= a, b, c, d < n, a, b, c, d are distinct, and nums[a] + nums[b] + nums[c] + nums[d] == target. You may return the answer in any order.

Constraints

  • 1 <= nums.length <= 200
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9

Examples

Example 1

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

Example 2

Input
nums = [2,2,2,2,2], target = 8
Output
[[2,2,2,2]]

Approaches

1. Brute-force quadruple loop

Try every (a, b, c, d) and dedupe with a Set on sorted tuples.

Time
O(n^4)
Space
O(n^4) in the worst case
function fourSumBrute(nums, target) {
  nums.sort((a, b) => a - b);
  const seen = new Set();
  const out = [];
  for (let a = 0; a < nums.length; a++)
    for (let b = a + 1; b < nums.length; b++)
      for (let c = b + 1; c < nums.length; c++)
        for (let d = c + 1; d < nums.length; d++) {
          if (nums[a] + nums[b] + nums[c] + nums[d] === target) {
            const key = `${nums[a]},${nums[b]},${nums[c]},${nums[d]}`;
            if (!seen.has(key)) { seen.add(key); out.push([nums[a], nums[b], nums[c], nums[d]]); }
          }
        }
  return out;
}

Tradeoff: Conceptually clear but O(n^4) puts it well past acceptable at n = 200 (1.6B operations). Mention it to motivate the reduction.

2. Sort + two outer loops + two-pointer (optimal)

Sort. Two outer loops fix the first two elements; an inner two-pointer finds the remaining pair summing to target - nums[i] - nums[j]. Skip duplicates at every level.

Time
O(n^3)
Space
O(1) extra (O(log n) for sort recursion)
function fourSum(nums, target) {
  nums.sort((a, b) => a - b);
  const out = [];
  const n = nums.length;
  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      let l = j + 1, r = n - 1;
      while (l < r) {
        const s = nums[i] + nums[j] + nums[l] + nums[r];
        if (s === target) {
          out.push([nums[i], nums[j], nums[l], nums[r]]);
          while (l < r && nums[l] === nums[l + 1]) l++;
          while (l < r && nums[r] === nums[r - 1]) r--;
          l++; r--;
        } else if (s < target) l++;
        else r--;
      }
    }
  }
  return out;
}

Tradeoff: O(n^3) at O(1) extra space (modulo sort). The dedup skips at every level are critical — without them the output contains repeats and the test fails silently. Watch for integer overflow on the sum (JS handles it via Number, but in Java/C++ you'd use a long).

Netflix-specific tips

Netflix likes the explicit four-level dedup walkthrough. Talk through each 'continue if duplicate' line as you write it — they're testing whether you can articulate why each is needed. The interviewer may also ask 'how would you generalize to kSum?' — be ready to sketch the recursive kSum(arr, target, k) that reduces to twoSum when k === 2.

Common mistakes

  • Forgetting the outer dedup skip (`if (i > 0 && nums[i] === nums[i-1]) continue;`) — produces duplicate quadruples.
  • Skipping the inner duplicate skip after finding a match — produces duplicates within the same (i, j) pair.
  • Using a Set of stringified tuples for dedup instead of skips — works but is much slower and signals you didn't see the cleaner solution.

Follow-up questions

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

  • Generalize to k-Sum (recursive reduction to twoSum at the base case).
  • What if target is at the edge of the integer range? (Watch for overflow in non-JS languages.)
  • 4Sum II — given four arrays, count tuples summing to 0 (hash-map approach, O(n^2)).

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 is the recursive kSum often preferred over hand-coding 4Sum?

It generalizes — kSum reduces to (k-1)Sum on a smaller subarray, bottoming out at twoSum with two pointers. Same O(n^(k-1)) complexity but one function handles 3Sum, 4Sum, 5Sum without copy-paste.

Can you do better than O(n^3)?

With hash maps you can do O(n^2 * log(n^2)) for the 'count tuples' variant (4Sum II) but for the 'return all unique' variant O(n^3) is the standard bound.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →