4Sum: Every Distinct Quadruplet With Two Pointers

You're given an integer array nums and a target. I'd like you to return every distinct quadruplet [a, b, c, d] whose sum is target, where the four values come from four different positions in the array. Each one should be written smallest first and you list them in ascending order as well (by the first value, and then the second if that's a tie, and so on). If two quadruplets have the same four values they only count once.

Examples

Input	Output	Why
`nums = [1, 0, -1, 0, -2, 2], target = 0`	`[-2,-1,1,2] [-2,0,0,2] [-1,0,0,1]`	The two 0's can both go in the same quadruplet because they sit at different positions.
`nums = [2, 2, 2, 2, 2], target = 8`	`[2,2,2,2]`	There are five ways to choose four of the 2's but they're all the same quadruplet.
`nums = [1, 2, 3], target = 6`	`(none)`	You can't make a quadruplet out of three values.

Constraints

1 ≤ n ≤ 200
−10⁶ ≤ nums[i] ≤ 10⁶
−4 × 10⁶ ≤ target ≤ 4 × 10⁶

Hints

Hint 1

If you've done 3-sum with a sort and two pointers you've done most of this. What would you need to add on the outside to get to four values?

Hint 2

Sort it and fix two values with two nested loops over i < j, and then the last two come from a pair scan on everything to the right of j.

Hint 3

You'll get duplicates from three places: the same value fixed twice at i, the same value fixed twice at j, and the pointers landing on repeats after a hit. Skip all three the same way you did in 3-sum.

Where people lose marks

Skipping a repeated j even when j = i + 1, which I've seen quite a lot. You'll lose quadruplets like [2, 2, 2, 2] where the second value happens to be the same as the first one.
Moving lo and hi on by one step each after a hit, so that if the next value's the same you find the same quadruplet again and it shows up twice in the output.
Overflow in a language with fixed-width ints once the values get near 10⁹. They're capped at 10⁶ here so a 32-bit int's fine, but I'd probably still mention it in an interview.

Dry run on `[1,0,-1,0,-2,2],0`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 5

Step 1 / 5

nums
-20-1102031425
target0
I'd sort it first, which gives [-2, -1, 0, 0, 1, 2], and then for each i and j there's a pair scan on the rest looking for target − a[i] − a[j].
Step 2 / 5

nums
-20i-11j020314lo25hi
need3found1
With -2 and -1 fixed you need 3 from what's to the right, and 1 + 2 is exactly 3, so that's [-2, -1, 1, 2].
Step 3 / 5

nums
-20i-1102j03lo1425hi
need2found2
Now it's -2 and 0 that are fixed. You'd want 2 and the pointers find 0 and 2, which gives [-2, 0, 0, 2].
Step 4 / 5

nums
-20-11i02j03lo14hi25
need1found3
0 + 1 = 1 is what's needed here, so [-1, 0, 0, 1] goes in as well.
Step 5 / 5

nums
-20-1102031425
found3
That's every i and j tried. There are 3 distinct quadruplets and none of them came out twice, because of the skips.

How to think about it

If you try every four values it's O(n⁴), which is probably too slow even at 200. After a sort you can fix the first value at i and the second at j > i, and what you've got left is the question from the pair scan, where you're looking for two values in nums[j+1..n−1] that add up to target − nums[i] − nums[j]. That's O(n) for each of the O(n²) choices of i and j, so you end up at O(n³) in all.

The duplicates are where people lose marks, just like in 3-sum, and there are three places they come from now. When I move i on I skip any value that's the same as the one before, and I do the same for j, but only once it's past i + 1 because the first j for each i is always a fresh choice. After a hit I move lo past every copy of its value and hi past every copy of its value before I look again.

Because the array's sorted and every one of the loops goes left to right, I think you'll find the quadruplets come out in exactly the order the problem asks for, so there's no need for a sort at the end.

Complexity. Time O(n³) · Space O(1) extra (the output aside)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def four_sum(nums, target):
    a = sorted(nums)
    n = len(a)
    out = []
    for i in range(n - 3):
        if i > 0 and a[i] == a[i - 1]:
            continue                            # this first value was fixed already
        for j in range(i + 1, n - 2):
            if j > i + 1 and a[j] == a[j - 1]:
                continue                        # this second value was fixed already
            need = target - a[i] - a[j]
            lo, hi = j + 1, n - 1
            while lo < hi:
                s = a[lo] + a[hi]
                if s == need:
                    out.append([a[i], a[j], a[lo], a[hi]])
                    lv, hv = a[lo], a[hi]
                    while lo < hi and a[lo] == lv:
                        lo += 1
                    while lo < hi and a[hi] == hv:
                        hi -= 1
                elif s < need:
                    lo += 1
                else:
                    hi -= 1
    return out

#include <vector>
#include <algorithm>

std::vector<std::vector<int>> solve(std::vector<int> a, int target) {
    std::sort(a.begin(), a.end());
    int n = (int)a.size();
    std::vector<std::vector<int>> out;
    for (int i = 0; i + 3 < n; ++i) {
        if (i > 0 && a[i] == a[i - 1]) continue;                // this first value was fixed already
        for (int j = i + 1; j + 2 < n; ++j) {
            if (j > i + 1 && a[j] == a[j - 1]) continue;        // this second value was fixed already
            long long need = (long long)target - a[i] - a[j];
            int lo = j + 1, hi = n - 1;
            while (lo < hi) {
                long long s = (long long)a[lo] + a[hi];
                if (s == need) {
                    out.push_back({a[i], a[j], a[lo], a[hi]});
                    int lv = a[lo], hv = a[hi];
                    while (lo < hi && a[lo] == lv) ++lo;
                    while (lo < hi && a[hi] == hv) --hi;
                } else if (s < need) ++lo;
                else --hi;
            }
        }
    }
    return out;
}

import java.util.*;

class Solution {
    public int[][] fourSum(int[] nums, int target) {
        int[] a = nums.clone();
        Arrays.sort(a);
        int n = a.length;
        List<int[]> out = new ArrayList<>();
        for (int i = 0; i + 3 < n; i++) {
            if (i > 0 && a[i] == a[i - 1]) continue;            // this first value was fixed already
            for (int j = i + 1; j + 2 < n; j++) {
                if (j > i + 1 && a[j] == a[j - 1]) continue;    // this second value was fixed already
                long need = (long) target - a[i] - a[j];
                int lo = j + 1, hi = n - 1;
                while (lo < hi) {
                    long s = (long) a[lo] + a[hi];
                    if (s == need) {
                        out.add(new int[]{a[i], a[j], a[lo], a[hi]});
                        int lv = a[lo], hv = a[hi];
                        while (lo < hi && a[lo] == lv) lo++;
                        while (lo < hi && a[hi] == hv) hi--;
                    } else if (s < need) lo++;
                    else hi--;
                }
            }
        }
        return out.toArray(new int[0][]);
    }
}

function fourSum(nums, target) {
  const a = nums.slice().sort((x, y) => x - y), n = a.length, out = [];
  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && a[i] === a[i - 1]) continue;                 // this first value was fixed already
    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && a[j] === a[j - 1]) continue;           // this second value was fixed already
      const need = target - a[i] - a[j];
      let lo = j + 1, hi = n - 1;
      while (lo < hi) {
        const s = a[lo] + a[hi];
        if (s === need) {
          out.push([a[i], a[j], a[lo], a[hi]]);
          const lv = a[lo], hv = a[hi];
          while (lo < hi && a[lo] === lv) lo++;
          while (lo < hi && a[hi] === hv) hi--;
        } else if (s < need) lo++;
        else hi--;
      }
    }
  }
  return out;
}

fn solve(nums: &[i64], target: i64) -> Vec<Vec<i64>> {
    let mut a = nums.to_vec();
    a.sort();
    let n = a.len();
    let mut out = Vec::new();
    if n < 4 { return out; }
    for i in 0..n - 3 {
        if i > 0 && a[i] == a[i - 1] { continue; }              // this first value was fixed already
        for j in i + 1..n - 2 {
            if j > i + 1 && a[j] == a[j - 1] { continue; }      // this second value was fixed already
            let need = target - a[i] - a[j];
            let (mut lo, mut hi) = (j + 1, n - 1);
            while lo < hi {
                let s = a[lo] + a[hi];
                if s == need {
                    out.push(vec![a[i], a[j], a[lo], a[hi]]);
                    let (lv, hv) = (a[lo], a[hi]);
                    while lo < hi && a[lo] == lv { lo += 1; }
                    while lo < hi && a[hi] == hv { hi -= 1; }
                } else if s < need { lo += 1; } else { hi -= 1; }
            }
        }
    }
    out
}

import Data.List (sort, group)

-- Lists instead of indices: each level walks the distinct values left to right, so no quadruplet repeats.
solve :: [Int] -> Int -> [[Int]]
solve nums target = go1 (sort nums)
  where
    go1 (x : rest) = [x : q | q <- go2 (target - x) rest] ++ go1 (dropWhile (== x) rest)
    go1 []         = []
    go2 t (y : rest) = [[y, c, d] | (c, d) <- pairs (t - y) rest] ++ go2 t (dropWhile (== y) rest)
    go2 _ []         = []
    -- the distinct pairs in a sorted list that sum to t, smallest first
    pairs t xs = scan xs (reverse xs) (length xs)
      where
        scan (l : ls) (h : hs) k
          | k < 2      = []
          | l + h == t = (l, h) : scanSkip l h ls hs (k - 2)
          | l + h <  t = scan ls (h : hs) (k - 1)
          | otherwise  = scan (l : ls) hs (k - 1)
        scan _ _ _ = []
        scanSkip l h ls hs k =
          let (dl, ls') = span (== l) ls
              (dh, hs') = span (== h) hs
          in scan ls' hs' (k - length dl - length dh)

Variants to try

For k values you'd fix k − 2 of them in nested loops and do one pair scan at the bottom, which is O(n^(k−1)). It's neatest written as a recursion that drops k by one each time.
If you only need to count quadruplets from four separate arrays, a hash map of every a + b and a lookup for every −(c + d) gets it down to O(n²).

Next problems

Medium20 min

All distinct quadruplets with a given sum

Examples

Constraints

Hints

Where people lose marks

Dry run on `[1,0,-1,0,-2,2],0`

How to think about it

The solution, in six languages

Variants to try

Next problems

All distinct triplets summing to zero

The triple sum closest to a target

Count the triplets with a sum below a target

Keep going

All distinct triplets summing to zero

The triple sum closest to a target

Count the triplets with a sum below a target

The pattern behind it

All distinct quadruplets with a given sum

Examples

Constraints

Hints

Where people lose marks

Dry run on [1,0,-1,0,-2,2],0

How to think about it

The solution, in six languages

Variants to try

Next problems

All distinct triplets summing to zero

The triple sum closest to a target

Count the triplets with a sum below a target

Keep going

All distinct triplets summing to zero

The triple sum closest to a target

Count the triplets with a sum below a target

The pattern behind it

Dry run on `[1,0,-1,0,-2,2],0`