Triplets, and Everything Above Them

Two Sum on a sorted array is O(n). Three Sum looks like a different problem, and it is not: fix the first element, and what is left is Two Sum on the rest of the array with a smaller target. One loop wrapped around the pass from two pages ago takes the obvious O(n³) down to O(n²).

That is the whole idea of this page, and it keeps going. Four Sum fixes two elements and runs the same pair pass, giving O(n³) instead of O(n⁴). k-Sum is k-2 nested loops with the converging pair at the bottom. What changes between the variants is not the structure but the single line at the comparison - and that line is where the interesting problems live.

3 Sum

Find every distinct triplet summing to zero. Sort first, then for each index i, run a converging pair over everything to its right looking for -a[i].

Sorting does two jobs here. It makes the pair pass valid, and it puts duplicates next to each other so they can be skipped, which is what stops the same triplet being reported three times over.

There are two separate duplicate skips, and both are needed. The one on the outer loop stops the same value of a[i] starting the same search twice. The two inside the pair loop, after a hit, stop the same pair being re-reported. Miss either and the output fills with repeats; the usual patch is to dedupe the results afterwards, which works and is slower and hides the fact that the sort already solved it.

A useful early exit falls out of the sort as well. Once a[i] is greater than zero, every value to its right is too, so no triplet from there on can sum to zero, and the loop can stop rather than continue.

function threeSum(nums) {
  const a = [...nums].sort((x, y) => x - y);
  const out = [];

  for (let i = 0; i < a.length - 2; i++) {
    if (a[i] > 0) break;                       // everything to the right is bigger
    if (i > 0 && a[i] === a[i - 1]) continue;  // same i value, same search

    let lo = i + 1, hi = a.length - 1;
    while (lo < hi) {
      const sum = a[i] + a[lo] + a[hi];
      if (sum === 0) {
        out.push([a[i], a[lo], a[hi]]);
        lo++; hi--;
        while (lo < hi && a[lo] === a[lo - 1]) lo++;
        while (lo < hi && a[hi] === a[hi + 1]) hi--;
      } else if (sum < 0) {
        lo++;
      } else {
        hi--;
      }
    }
  }
  return out;
}

Counting triplets under a target

How many triplets sum to less than a target? Enumerating them and counting is O(n²) work per fixed i in the worst case, which puts the whole thing back at O(n³). The counting version avoids that with the observation this problem is really about.

Suppose a[i] + a[lo] + a[hi] comes out under the target. Every value between lo and hi is at most a[hi], so swapping a[hi] for any of them keeps the sum under the target too. That is hi - lo triplets, all valid, counted in one step without looking at any of them. Then lo moves up.

If the sum is not under the target, a[hi] is too big for the current lo and for every lo after it, so hi comes down. Same two-branch structure, but one branch now credits a whole block.

// Number of triplets i < j < k with a[i] + a[j] + a[k] < target.
function countTripletsUnder(nums, target) {
  const a = [...nums].sort((x, y) => x - y);
  let count = 0;

  for (let i = 0; i < a.length - 2; i++) {
    let lo = i + 1, hi = a.length - 1;
    while (lo < hi) {
      if (a[i] + a[lo] + a[hi] < target) {
        // Every partner from lo+1 up to hi also works: one step, hi - lo triplets.
        count += hi - lo;
        lo++;
      } else {
        hi--;
      }
    }
  }
  return count;
}

The closest triplet

Now the target does not have to be hit, only approached: find the triplet whose sum is nearest to it. The pass is unchanged, and only the comparison changes - instead of testing for equality, keep the best distance seen so far and move the pointer that pushes the sum in the right direction.

There is one shortcut worth taking. A distance of zero cannot be beaten, so an exact hit can return immediately rather than finishing the scan.

This variant is the clearest illustration of why the technique is more than a trick for exact matches. A hash map answers "does this exact sum exist" and is useless here; the ordered scan answers "how close can we get", because the sort gives every step a direction to move in.

function closestTriplet(nums, target) {
  const a = [...nums].sort((x, y) => x - y);
  let best = Infinity;

  for (let i = 0; i < a.length - 2; i++) {
    let lo = i + 1, hi = a.length - 1;
    while (lo < hi) {
      const sum = a[i] + a[lo] + a[hi];
      if (Math.abs(sum - target) < Math.abs(best - target)) best = sum;

      if (sum === target) return sum;   // nothing beats a distance of zero
      if (sum < target) lo++;
      else hi--;
    }
  }
  return best;
}

4 Sum, and the general pattern

Two fixed indices instead of one, then the same pair. The duplicate skipping now has to happen on both outer loops, with the second one guarded by j > i + 1 rather than j > 0, because the first j of each new i is allowed to repeat a value that a previous i already used.

Watch the frame counter: even on six values the run is noticeably longer than 3 Sum on the same array, which is the O(n³) showing up. There is real pruning available - if the smallest four values from i already overshoot the target, no later j can help - and it is worth adding when n gets large, but it does not change the exponent.

function fourSum(nums, target) {
  const a = [...nums].sort((x, y) => x - y);
  const out = [];
  const n = a.length;

  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && a[i] === a[i - 1]) continue;
    for (let j = i + 1; j < n - 2; j++) {
      // j > i + 1, not j > 0: the first j of a new i may repeat a value.
      if (j > i + 1 && a[j] === a[j - 1]) continue;

      let lo = j + 1, hi = n - 1;
      while (lo < hi) {
        const sum = a[i] + a[j] + a[lo] + a[hi];
        if (sum === target) {
          out.push([a[i], a[j], a[lo], a[hi]]);
          lo++; hi--;
          while (lo < hi && a[lo] === a[lo - 1]) lo++;
          while (lo < hi && a[hi] === a[hi + 1]) hi--;
        } else if (sum < target) {
          lo++;
        } else {
          hi--;
        }
      }
    }
  }
  return out;
}

What each variant costs

The pattern has a floor worth knowing. k-Sum by this method is O(n^(k-1)), and for 4 Sum there is a hash-based approach that reaches O(n²) by storing every pair sum, at the cost of O(n²) memory and considerably more care around duplicates. Below that, no method is known to do better, and the problem is one of the standard hard cases in fine-grained complexity.

Check yourself

Next: two sequences, one pass each, where the pointers live in different arrays.