Topics › Arrays › Hard

4 Sum

Medium TUF ID 28 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an integer array nums and an integer target. Return every distinct quadruplet of values [a, b, c, d], taken from four different positions, such that a + b + c + d == target. Two quadruplets are the same if they hold the same multiset of values, so each one should appear once. Report each quadruplet in non-decreasing order; the order of the quadruplets does not matter.

Constraints: 0 ≤ n ≤ 200, values and target fit in a 32-bit signed integer.

Example 1

nums = [1, 0, -1, 0, -2, 2], target = 0
answer = [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Each listed quadruplet sums to zero; the two zeros come from different indices, so [-2, 0, 0, 2] is valid.

Example 2

nums = [2, 2, 2, 2, 2], target = 8
answer = [[2, 2, 2, 2]]

There are five ways to pick four indices, but they all give the same values.

Approach 1: Brute force

Intuition. Enumerate every choice of four indices i < j < k < l, test the sum, and push sorted quadruplets into a Set so repeats vanish. This is the definition of the problem written as code.

Algorithm.

1. Four nested loops over i < j < k < l.
2. If the four values sum to target, sort them and add the list to a set.
3. Return the set (sorted for comparison in tests).

static List<List<Integer>> bruteForce(int[] nums, int target) {
    int n = nums.length;
    Set<List<Integer>> set = new HashSet<>();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                for (int l = k + 1; l < n; l++) {
                    if ((long) nums[i] + nums[j] + nums[k] + nums[l] == target) {
                        int[] q = {nums[i], nums[j], nums[k], nums[l]};
                        Arrays.sort(q);
                        set.add(List.of(q[0], q[1], q[2], q[3]));
                    }
                }
            }
        }
    }
    return sorted(set);
}

Complexity. Time O(n^4): about n^4 / 24 quadruples. Space O(k) for k distinct answers.

The (long) cast is essential here. Four values of 10^9 sum to 4 × 10^9, which int wraps to -294967296; a test in the Java file uses exactly that target and expects no quadruplet.

For n = 200, n^4 / 24 ≈ 6.7 × 10^7 is actually tolerable, but the approach falls apart the moment constraints grow, and interviewers expect better.

Approach 2: Better, hash the fourth value

Intuition. With three values fixed, the fourth is determined: target - a - b - c. Fix i and j with two loops, then walk k to the right while maintaining a hash set of the values strictly between j and k. For each k, look up the needed fourth value in that set. This is 3 Sum’s hashing trick with one more outer loop, and it finds every index quadruple exactly once because the fourth index always lies strictly between j and k.

Algorithm.

1. For each i, each j > i: create an empty set seen.
2. For each k > j: need = target - nums[i] - nums[j] - nums[k].
   • If need is in seen, sort {nums[i], nums[j], nums[k], need} and add to the result set.
   • Add nums[k] to seen.
3. Return the result set.

static List<List<Integer>> better(int[] nums, int target) {
    int n = nums.length;
    Set<List<Integer>> set = new HashSet<>();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            Set<Long> seen = new HashSet<>();            // values nums[j+1 .. k-1]
            for (int k = j + 1; k < n; k++) {
                long need = (long) target - nums[i] - nums[j] - nums[k];
                if (seen.contains(need)) {
                    int[] q = {nums[i], nums[j], nums[k], (int) need};
                    Arrays.sort(q);
                    set.add(List.of(q[0], q[1], q[2], q[3]));
                }
                seen.add((long) nums[k]);
            }
        }
    }
    return sorted(set);
}

Complexity. Time O(n^3): three nested loops with constant-time hash operations. Space O(n) for seen (it is rebuilt for every (i, j)), plus the output set.

The set stores Long so that need, which can fall outside the int range, is looked up directly without a range check; a need outside the range simply is not found.

Approach 3: Optimal, sort plus two pointers

Intuition. Sort the array. Fix the two smallest members of the quadruplet, a[i] and a[j], with two loops. The remaining two values must lie in a[j+1 .. n-1] and sum to target - a[i] - a[j], which is the classic sorted two-pointer search: too small, move lo right; too big, move hi left.

Sorting also kills duplicates without a set: skip i when a[i] == a[i-1], skip j when a[j] == a[j-1] within the same i (j > i + 1), and after every hit move lo and hi past equal values. The results come out in lexicographic order.

Algorithm.

1. Sort a copy a of the array.
2. For i from 0 to n - 4, skipping repeated values:
3. For j from i + 1 to n - 3, skipping repeated values (but never skipping j == i + 1):
   • lo = j + 1, hi = n - 1.
   • While lo < hi: compute sum. If sum < target, lo++; if sum > target, hi--; else record [a[i], a[j], a[lo], a[hi]], move both pointers inward and skip duplicates.
4. Return the list.

static List<List<Integer>> optimal(int[] nums, int target) {
    int[] a = nums.clone();
    Arrays.sort(a);
    int n = a.length;
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < n - 3; i++) {
        if (i > 0 && a[i] == a[i - 1]) continue;          // same first value already handled
        for (int j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && a[j] == a[j - 1]) continue;  // same second value already handled for this i
            int lo = j + 1, hi = n - 1;
            while (lo < hi) {
                long sum = (long) a[i] + a[j] + a[lo] + a[hi];
                if (sum < target) lo++;
                else if (sum > target) hi--;
                else {
                    res.add(List.of(a[i], a[j], a[lo], a[hi]));
                    lo++;
                    hi--;
                    while (lo < hi && a[lo] == a[lo - 1]) lo++;   // skip equal third values
                    while (lo < hi && a[hi] == a[hi + 1]) hi--;   // skip equal fourth values
                }
            }
        }
    }
    return res;
}

Dry run on nums = [1, 0, -1, 0, -2, 2], target = 0, sorted to a = [-2, -1, 0, 0, 1, 2]:

Result: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]].

Complexity. Time O(n^3): O(n log n) to sort, then O(n^2) pairs (i, j) each followed by an O(n) sweep. Space O(1) extra beyond the sorted copy and the output.

Same order as approach 2, so why prefer it? No boxing, no hashing, no per-pair set allocation, and the de-duplication is built into the traversal. In practice it is several times faster and uses almost no memory.

The j skip condition j > i + 1 deserves attention. If a[i] == a[i+1], the pair (i, i+1) is legitimate (two equal values at different indices, as in [2, 2, 2, 2]). Only when a value repeats as the second member for the same i has it been fully explored before.

Edge cases and pitfalls

• Fewer than four elements. Return an empty list; i < n - 3 guarantees the loops do not run.
• All equal values. [2, 2, 2, 2, 2] with target 8 must give exactly one quadruplet. Breaking the j > i + 1 rule would give zero; dropping the skips altogether would give several.
• Overflow. int addition of four values can wrap exactly onto the target. All sums are long. The Java tests include four copies of 10^9 with target -294967296.
• Negative targets. Nothing changes; [1, -2, -5, -4, -3, 3, 3, 5] with target -11 gives [[-5, -4, -3, 1]].
• Early-exit tricks. For 3 Sum with target zero we could break when a[i] > 0. Here the target is arbitrary, so that shortcut does not apply unless you compare against target and account for the sign of the remaining values; it is simplest to leave it out.

Related problems

• Two Sum is the innermost two-pointer or hash step.
• 3 Sum is the same pattern with one fewer fixed element.