Find four elements that sum to a given value

The problem, simply

You get an array of numbers and a target. Find every group of four numbers, taken from four different positions, that adds up to the target.

Two groups with the same four values count as one, even if they use different positions. Return each group with its numbers in order from small to big. Extra room for the answer itself does not count.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every group of four positions. Sort each matching group and drop it into a set, so copies disappear.

import java.util.*;

class Solution {
    public List<List<Integer>> fourSum(int[] arr, int target) {
        Set<List<Integer>> groups = new TreeSet<>((x, y) -> {
            for (int k = 0; k < 4; k++) {
                int c = Integer.compare(x.get(k), y.get(k));
                if (c != 0) return c;
            }
            return 0;
        });
        int n = arr.length;
        for (int a = 0; a < n; a++)
            for (int b = a + 1; b < n; b++)
                for (int c = b + 1; c < n; c++)
                    for (int d = c + 1; d < n; d++) {
                        long sum = (long) arr[a] + arr[b] + arr[c] + arr[d];
                        if (sum == target) {
                            List<Integer> g = new ArrayList<>(List.of(arr[a], arr[b], arr[c], arr[d]));
                            Collections.sort(g);   // same values, same order
                            groups.add(g);         // the set drops copies
                        }
                    }
        return new ArrayList<>(groups);
    }
}

How long it takes: about n^4 / 24 groups, O(n^4). Extra room: O(1) besides the answer set.

Way 2: the clever way

Sort the array. Fix the first two numbers with two loops, then find the last two with two fingers that move toward each other, like two sum on a sorted list.

1. Sort the array.
2. Loop i over the first number. Skip it if it equals the number before it.
3. Loop j over the second number, after i. Skip it if it equals the number before it (but not the one right after i).
4. Put l = j + 1 and r = n - 1. Add the four numbers.
5. Equal to the target: save the group, then move l and r past any copies of their numbers.
6. Too small: move l right. Too big: move r left.

import java.util.*;

class Solution {
    public List<List<Integer>> fourSum(int[] arr, int target) {
        List<List<Integer>> out = new ArrayList<>();
        int n = arr.length;
        Arrays.sort(arr);
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && arr[i] == arr[i - 1]) continue;          // same first number
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && arr[j] == arr[j - 1]) continue;  // same second number
                int l = j + 1, r = n - 1;
                while (l < r) {
                    long sum = (long) arr[i] + arr[j] + arr[l] + arr[r];
                    if (sum == target) {
                        out.add(List.of(arr[i], arr[j], arr[l], arr[r]));
                        while (l < r && arr[l] == arr[l + 1]) l++;   // skip copies
                        while (l < r && arr[r] == arr[r - 1]) r--;
                        l++;
                        r--;
                    } else if (sum < target) {
                        l++;                                       // need more
                    } else {
                        r--;                                       // need less
                    }
                }
            }
        }
        return out;
    }
}

How long it takes: sorting is O(n log n). Two loops times one finger walk is O(n^3). Extra room: O(1) besides the answer.

Watch out for

• Checking copies of j with j > 0 instead of j > i + 1. For [0, 0, 0, 0] and target 0, the first j equals arr[i] and gets skipped, so the only group [0, 0, 0, 0] is lost.
• After a match, moving only one finger. With sorted values, if l stays, the only partner that works is a copy of arr[r], which gives the same group again.
• Forgetting to sort each group in Way 1. Then [0, -1, 1, 0] and [-1, 0, 0, 1] look different to the set.

What interviewers ask next

• Can you beat O(n^3)? Store every pair sum in a hash map, then look up target - (pair sum) for each pair. That is O(n^2) on average for "does any group exist", but listing all distinct groups can still cost more, and keeping the four positions different is fiddly.
• Generalize to k-sum. Write kSum(start, k, target): for k == 2 use two fingers, otherwise loop the first number and call kSum(i + 1, k - 1, target - arr[i]). Time O(n^(k-1)).
• Speed it up in practice: break out of the i loop when the four smallest numbers from i already pass the target, and skip i when the biggest numbers cannot reach it.
• Count groups instead of listing them, with repeats allowed? Then pair sums in a hash map with counts work well.

Remember this

Grown-up words: the fingers are two pointers, the four numbers are a quadruplet, skipping equal neighbours is deduplication, and the recursive version is the general k-sum reduction.