4Sum

TWO POINTERS · MEDIUM

Builds on Day 4: Two-Pointer Pattern

The optimal solution below fixes two indices with nested loops and then runs the exact converging left/right scan taught in that lesson on whatever’s left of the sorted array — read it first if two pointers closing in from opposite ends still feels unfamiliar.

The problem

Given an array of integers nums and a target integer, find every unique quadruplet [a, b, c, d] — four values from the array, using four distinct indices — whose sum equals target. “Unique” means each combination of values appears exactly once in the result, even if the same values could be picked from the array in more than one way (repeated values are common, and the array can contain duplicates). The order of the returned quadruplets doesn’t matter, and neither does the order of the four values within a quadruplet. Example: nums = [1, 0, -1, 0, -2, 2], target = 0 → [[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]]. Note that 0 appears twice in nums, and both copies get legitimately used across two different quadruplets above — but no quadruplet is ever repeated in the output.

Solution 1: Brute force — check every 4-index combination, dedupe with a Set

The most literal reading of the problem: try every possible way to pick 4 distinct indices a < b < c < d out of the array, and check whether their values sum to target. Four nested loops does exactly that. The catch is uniqueness — the same quadruplet of values can turn up from more than one combination of indices when the array has duplicates (that’s exactly what happens with the two 0s in the example above, and it happens far more aggressively when the array has heavier repeats). So every time a combination sums to target, sort its four values, stringify them into a key, and check a Set of keys already seen — only keep the combination if that key is new. This is correct, but it’s genuinely wasteful in two ways: it inspects every single 4-index combination regardless of how obviously wrong most of them are, and it does real extra work (sorting + stringifying + a Set lookup) on every match just to clean up duplicates it could have avoided creating in the first place.

nums = [1, 1, -1, -1, 0, 0], target = 0— checking all 15combinations

Press Play or Step to begin.

combinations checked: —

Step 0

▶ Play — O(n⁴)⏭ Step↺ Reset

The code

function fourSumBrute(nums, target) {
  const n = nums.length;
  const seen = new Set();
  const result = [];

  for (let a = 0; a < n; a++) {
    for (let b = a + 1; b < n; b++) {
      for (let c = b + 1; c < n; c++) {
        for (let d = c + 1; d < n; d++) {
          if (nums[a] + nums[b] + nums[c] + nums[d] === target) {
            const quad = [nums[a], nums[b], nums[c], nums[d]].sort((x, y) => x - y);
            const key = quad.join(',');
            if (!seen.has(key)) {
              seen.add(key);
              result.push(quad);
            }
          }
        }
      }
    }
  }

  return result;
}

Line by line:

• Four nested loops, each starting one index past the previous one (b = a + 1, c = b + 1, d = c + 1) — this is exactly how “choose 4 distinct indices, order doesn’t matter” is generated without ever picking the same set of indices twice.
• nums[a] + nums[b] + nums[c] + nums[d] === target is the only real check — every combination gets summed and compared, with zero shortcuts.
• On a match, [...].sort((x, y) => x - y) normalizes the four values into a canonical order (see the trick question in Interview Corner for exactly why the comparator here isn’t optional), then .join(',') turns that into a single string key like "-1,0,0,1".
• seen.has(key) is the entire uniqueness mechanism — if this exact sorted combination of values was already recorded, it’s silently dropped; otherwise it’s added to both seen and result.
• Nothing about the loop structure changes based on what’s been found — every one of the n(n-1)(n-2)(n-3)/24 combinations gets fully evaluated, match or not.

Complexity

Time	Space	Approach
O(n⁴)	O(n)	Four nested loops over every index combination, deduped with a Set

Solution 2: Optimal — sort once, fix two, two-pointer the rest

Sort nums first. Sorting turns the problem’s hardest part — avoiding duplicate quadruplets — into something that can be handled by simply skipping over repeated values, because in a sorted array every occurrence of the same value sits right next to its duplicates. Use two nested loops to fix the first two members of the quadruplet, i and j. At each level, if the current index’s value is the same as the value right before it at that same nesting level, skip it — trying it again would only ever regenerate a quadruplet already produced by the previous, identical value. For the remaining two members, run a standard two-pointer scan: left starts right after j, right starts at the end of the array, and they converge inward based on whether the running sum of all four values is above or below target. When a match is found, apply the same duplicate-skipping idea to left and right before continuing, so the exact same quadruplet never gets recorded twice.

Be honest about what this buys you. This is a real asymptotic improvement — O(n³) beats O(n⁴) — but it’s a modest one, not a dramatic one. The two outer loops fixing i and j are still O(n²) on their own; the two-pointer scan only shrinks the innermost pair of loops from O(n²) down to O(n). One power of n disappears, not three. The bigger practical win isn’t even the asymptotic complexity — it’s that duplicate quadruplets are never generated in the first place, instead of being generated and then cleaned up with the wasteful sort-stringify-Set-lookup dance from Solution 1.

Sorted: [-1, -1, 0, 0, 1, 1], target = 0— fewer comparisons with two-pointer

Press Play or Step to begin.

Step 0

▶ Play — O(n³)⏭ Step↺ Reset

The code

function fourSumOptimal(nums, target) {
  const n = nums.length;
  const sorted = nums.slice().sort((a, b) => a - b);
  const result = [];

  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && sorted[i] === sorted[i - 1]) continue;

    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && sorted[j] === sorted[j - 1]) continue;

      let left = j + 1;
      let right = n - 1;

      while (left < right) {
        const sum = sorted[i] + sorted[j] + sorted[left] + sorted[right];
        if (sum === target) {
          result.push([sorted[i], sorted[j], sorted[left], sorted[right]]);
          left++;
          right--;
          while (left < right && sorted[left] === sorted[left - 1]) left++;
          while (left < right && sorted[right] === sorted[right + 1]) right--;
        } else if (sum < target) {
          left++;
        } else {
          right--;
        }
      }
    }
  }

  return result;
}

Line by line:

• sorted = nums.slice().sort((a, b) => a - b) — sorts a copy, numerically (see the trick question below for why the comparator is non-negotiable here). Everything after this line depends on sorted actually being in ascending order.
• i runs up to n - 3 and j up to n - 2 — each needs to leave room for at least two more elements (left and right) after it.
• if (i > 0 && sorted[i] === sorted[i - 1]) continue; — the classic duplicate-skip. This only fires when i isn’t the first index AND its value repeats the immediately preceding one; trying the same starting value twice at the same nesting level would only rebuild quadruplets already fully explored the first time.
• The identical pattern guards j, with one important difference: j > i + 1, not j > 0. j is compared against the slot directly before it in the CURRENT inner loop, not against i — comparing against i would wrongly skip a legitimately different value.
• left = j + 1, right = n - 1 — the two-pointer scan always starts on the untouched remainder of the array, strictly after j.
• On a match, both pointers move inward, and then two more while loops skip past any repeated values at the NEW left and right positions — this is what stops the exact same quadruplet from being recorded a second time when, say, three or four copies of the same value sit next to each other.
• sum < target moves left rightward (toward larger values); sum > target moves right leftward (toward smaller values) — the same convergence rule from the two-pointer lesson, just with two of the four terms already pinned by the outer loops.

Complexity

Time	Space	Approach
O(n³)	O(n) or O(log n)	Sort once, fix i/j with dup-skipping, two-pointer scan the remainder

Space here depends on the sort — this solution builds a sorted copy of nums explicitly (O(n)); if sorting in place were acceptable, only the sort algorithm’s own internal stack space would count (commonly O(log n) for a typical comparison sort), on top of O(1) for the pointers themselves. Either way, the output array itself isn’t counted as extra space, by the usual convention.

Complexity comparison

Solution	Time	Space
Brute force (four nested loops + Set dedupe)	O(n⁴)	O(n)
Optimal (sort + two-pointer)	O(n³)	O(n) for the sorted copy

This is a genuine asymptotic improvement — O(n³) really is better than O(n⁴) — but it’s worth being honest that it’s a modest one, not a dramatic one: the two outer loops fixing i and j stay at O(n²) regardless, and the two-pointer scan only removes one power of n from what used to be two nested loops for c and d. O(n³) is still not “fast” in any absolute sense for large inputs — it’s a real win over the brute force, not a transformation into something lightweight. The more meaningful practical difference is that duplicate quadruplets are never generated at all in the optimal solution, instead of being generated and then cleaned up after the fact with a Set.

Interview corner

Why does sorting the array first make the duplicate-skipping trick possible, when the brute force couldn’t use anything like it?

• In a sorted array, every occurrence of the same value is adjacent to its other occurrences — there’s no way for two copies of the same value to be sorted but not next to each other.
• That means “have I already tried this exact value at this exact nesting level?” collapses into a single comparison: check the value immediately before the current index. If it’s equal, the current index is guaranteed to be a repeat of something already fully explored.
• The brute force iterates over the ORIGINAL array order, where equal values can be scattered anywhere — there’s no adjacent-comparison shortcut available, which is exactly why it has to fall back to a Set keyed by the full sorted-and-stringified quadruplet instead.

In the inner loop, why is the duplicate check j > i + 1 && sorted[j] === sorted[j - 1] and not j > 0 && sorted[j] === sorted[j - 1]?

• j always starts at i + 1 for a fresh i — that very first j in each new outer iteration must always be allowed to run, even if sorted[j] === sorted[j - 1] happens to be true (which it very well could be, since sorted[j - 1] might just be sorted[i] itself, an entirely different nesting level).
• Using j > 0 would incorrectly compare against a value chosen by a DIFFERENT, outer-loop index, and could wrongly skip a legitimately different value.
• j > i + 1 restricts the comparison to only fire when j has already advanced at least once past its own starting point within the CURRENT i, which is the only time “compare to the previous j” is even a meaningful statement.

After a match, why does the code skip duplicates at left and right AFTER moving the pointers inward, rather than before?

• The dup-skip’s job is to prevent re-recording the SAME quadruplet — but the quadruplet just found used the values at the OLD left and right, so those exact positions have already correctly contributed one result.
• left++; right--; happens first specifically so the values being checked for repeats are the NEXT candidates, not the ones that were just recorded.
• Checking for duplicates before advancing would compare each position to itself (trivially always “equal”) and never actually move past a genuine run of repeated values — the loop would find the same quadruplet, advance nothing, and either loop forever or (with the left < right guard) simply never make progress on real duplicate runs.

↳ Common follow-up: “What if the array had 5 copies of the same value in a row, all part of the answer?” The two while loops handle it correctly — each one keeps advancing past every matching neighbor, not just one, so a long run of duplicates collapses to exactly one surviving position rather than needing one dup-check per pair.

Trick question — what does this log?

const nums = [10, 2, -1, -10, 5];
console.log(nums.slice().sort());
console.log(nums.slice().sort((a, b) => a - b));

• Answer: the first line logs [-1, -10, 10, 2, 5] — visibly NOT sorted by numeric value. The second logs [-10, -1, 2, 5, 10] — the actually correct numeric order.
• Array.prototype.sort() with no comparator converts every element to a STRING and sorts lexicographically (dictionary order) by default — not numerically. String comparison puts "10" before "2" because the character '1' sorts before '2', completely ignoring that 10 > 2 as numbers. It gets worse with negative signs, since '-' is just another character being compared position by position, not a sign the comparison understands.
• This is exactly why fourSumOptimal above sorts with .sort((a, b) => a - b) and never bare .sort() — the entire duplicate-skip and two-pointer convergence logic silently assumes true numeric ascending order. With the default sort, values like -10 would land in the wrong position relative to -1, and the “check the immediately preceding value” duplicate trick would compare against the wrong neighbor entirely.

⚠ Trap: this bites hardest exactly on arrays with negative numbers or multi-digit values — the kind 4Sum test cases are full of — while small single-digit positive-only arrays can accidentally “look right” with a bare .sort() and hide the bug until a nastier input exposes it.

Quiz

Quiz: 1. Why does sorting the array first make the duplicate-skipping trick (comparing each index to the one before it) work correctly?

Sorting puts every occurrence of a value directly next to its duplicates, so comparing to the immediately preceding index is enough to catch a repeat

Sorting places every occurrence of a value directly next to its other occurrences, so checking “does this equal the value right before it” is enough to detect a repeat at that nesting level. The original array order gives no such adjacency, which is exactly why the brute force needs a Set instead.

Quiz: 2. Why is the inner loop’s duplicate check written as j > i + 1 && sorted[j] === sorted[j-1] instead of j > 0 && sorted[j] === sorted[j-1]?

j > 0 would wrongly compare the first j of a new i against a value chosen by the outer loop, and could skip valid quadruplets

j always starts fresh at i + 1 for a new i, and that first j must be allowed to run even if it happens to equal sorted[j-1] (which could just be sorted[i], a different nesting level entirely). Comparing against j > 0 instead would wrongly skip valid quadruplets by comparing against a value chosen by the outer loop.

Quiz: 3. After finding a match, why does the code advance left and right BEFORE checking them for duplicates, rather than after?

Advancing first means the duplicate check compares the next candidates, not the positions that were just recorded — checking first would compare a position to itself and never progress

left++ and right-- happen first so the duplicate check compares the NEXT candidate positions, not the ones that were just recorded as part of the match. Checking before advancing would compare each position to itself and never make progress past a real run of duplicates.

Quiz: 4. How should the O(n³) vs O(n⁴) improvement be honestly described?

A real but modest asymptotic improvement — one power of n drops, not a dramatic speedup, and O(n³) still isn’t “fast” in absolute terms

O(n³) is a real improvement over O(n⁴), but a modest one — the two outer loops fixing i and j stay at O(n²), and the two-pointer scan only removes one power of n from what used to be two more nested loops. It’s not a dramatic speedup, and O(n³) is still not “fast” in any absolute sense on large input.

Quiz: 5. Why must fourSumOptimal sort with .sort((a, b) => a - b) instead of a bare .sort()?

Bare .sort() converts elements to strings and sorts lexicographically, which is wrong for numbers — the algorithm’s logic depends on true ascending numeric order

Array.prototype.sort() with no arguments converts elements to strings and sorts lexicographically, which is wrong for numbers (e.g. '10' sorts before '2', and negative signs are compared as characters, not as a sign). fourSumOptimal’s entire duplicate-skip and two-pointer logic depends on true ascending numeric order, so it must use .sort((a, b) => a - b).