Find Four Elements that Sum to a Target

Title: Find Four Elements that Sum to a Target

In this guide, you’ll learn how to solve the classic 4Sum problem: given an array of integers and a target value, find every unique combination of four elements whose sum equals the target. This is a direct extension of the two-sum and three-sum problems, and it shows up often in interviews that test whether you can generalize a two-pointer technique.

We’ll walk through a sorting-and-two-pointers approach that runs in O(n^3) time, trace it step by step on a small array, and cover the duplicate-handling details that trip up most candidates.

Understanding the Problem

Given an integer array numbers and an integer target, you need to return all unique quadruplets [a, b, c, d] from numbers such that a + b + c + d equals target. The same index cannot be used twice inside one quadruplet, but the same value can appear more than once if the array contains duplicates.

The order of values inside a quadruplet and the order of quadruplets in the result do not matter, as long as no duplicate combination appears twice in the output.

A brute-force solution checks every combination of four indices, which costs O(n^4) and becomes impractical quickly. Sorting the array first lets you fix two numbers and scan the rest with two pointers, cutting the work down to O(n^3).

Approach

1. Handle the trivial case: if numbers.length is less than 4, return an empty result immediately.
2. Sort numbers in ascending order so duplicates sit next to each other and two-pointer scanning becomes valid.
3. Iterate i from 0 to n - 4, skipping it whenever numbers[i] == numbers[i - 1] to avoid repeating the first element of a quadruplet.
4. For each i, iterate j from i + 1 to n - 3, skipping it whenever numbers[j] == numbers[j - 1] (and j is not immediately after i) to avoid repeating the second element.
5. Set left = j + 1 and right = n - 1, then move the two pointers toward each other based on how numbers[i] + numbers[j] + numbers[left] + numbers[right] compares to target.
6. When the sum equals target, record the quadruplet, then advance left and right past any duplicate values before continuing.
7. When the sum is less than target, increment left; when it is greater, decrement right.
8. Repeat until left and right meet, then move on to the next j, and eventually the next i.

Java Program

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSum {

    public static List<List<Integer>> findQuadruplets(int[] numbers, int target) {
        List<List<Integer>> result = new ArrayList<>();
        int n = numbers.length;
        if (n < 4) {
            return result;
        }

        Arrays.sort(numbers);

        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && numbers[i] == numbers[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && numbers[j] == numbers[j - 1]) {
                    continue;
                }
                int left = j + 1;
                int right = n - 1;
                while (left < right) {
                    long sum = (long) numbers[i] + numbers[j] + numbers[left] + numbers[right];
                    if (sum == target) {
                        result.add(Arrays.asList(numbers[i], numbers[j], numbers[left], numbers[right]));
                        while (left < right && numbers[left] == numbers[left + 1]) {
                            left++;
                        }
                        while (left < right && numbers[right] == numbers[right - 1]) {
                            right--;
                        }
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] numbers = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> quadruplets = findQuadruplets(numbers, target);
        System.out.println(quadruplets);
    }
}

Explanation of the Program

• findQuadruplets first checks for arrays shorter than four elements and returns an empty list rather than risk an out-of-bounds pointer.
• Arrays.sort(numbers) puts the array in ascending order so duplicate values become adjacent and the two-pointer scan is valid.
• The outer loop variable i and the inner loop variable j fix the first two elements of each candidate quadruplet.
• The duplicate-skip checks on numbers[i] and numbers[j] prevent the same leading pair from being processed more than once.
• left and right scan inward from just after j to the end of the array, and the sum is cast to long before comparison to avoid integer overflow.
• When a match is found, both pointers skip past any following duplicates before the search continues, which keeps the result free of repeated quadruplets.

Step-by-Step Trace

Consider the sorted array [-3, -1, 0, 2, 4, 5] with target = 2, where i = 0 (numbers[i] = -3) and j = 1 (numbers[j] = -1) are already fixed. The table below traces the inner while loop as left and right scan the remaining sub-array [0, 2, 4, 5]:

At the end of each iteration, the window between left and right has shrunk by at least one position, so every pair of positions in the sorted sub-array is tested at most once before the loop ends.

Examples

Example 1: Multiple Quadruplets with Negative Numbers

This is the input most people associate with the 4Sum problem. Negative and positive values combine in more than one way to reach the target.

int[] numbers = {1, 0, -1, 0, -2, 2};
int target = 0;
// findQuadruplets(numbers, target) returns:
// [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Example 2: No Quadruplet Reaches the Target

When every possible combination falls short of the target, the method should return an empty list rather than null or throw an exception.

int[] numbers = {1, 2, 3, 4};
int target = 100;
// findQuadruplets(numbers, target) returns:
// []

Example 3: Repeated Values Still Produce One Quadruplet

When the same value appears five times, only one quadruplet should be reported even though several index combinations would otherwise sum to the target.

int[] numbers = {2, 2, 2, 2, 2};
int target = 8;
// findQuadruplets(numbers, target) returns:
// [[2, 2, 2, 2]]

Common Mistakes to Avoid

The two-pointer approach depends on several details that are easy to get wrong under interview pressure.

• Forgetting to sort first – the duplicate-skip checks and the left/right pointer narrowing both assume ascending order; without Arrays.sort(numbers), valid quadruplets get missed or duplicated. Always sort before the nested loops begin.
• Comparing against the wrong neighbor when skipping duplicates – checking numbers[i] == numbers[i + 1] instead of numbers[i] == numbers[i - 1] skips the first occurrence of a value entirely. Compare each index to the one before it.
• Letting the four-way sum overflow – adding four int values near Integer.MAX_VALUE silently wraps around and produces a false match or a missed one. Cast the running sum to long before comparing it to target.
• Advancing only one pointer after a match – moving just left or just right after recording a quadruplet re-adds the same combination on the next iteration. Advance both pointers past duplicates and then one step further.

Edge Cases to Test

Walking through these cases out loud is exactly what an interviewer wants to see before you start coding.

• Array with fewer than four elements
• Empty array
• All elements identical
• Multiple quadruplets sharing the same values
• Target unreachable by any combination
• Negative numbers mixed with positive numbers
• Sum of four values near Integer.MAX_VALUE or Integer.MIN_VALUE
• Null array reference

Additional Considerations

The sorting step costs O(n log n), and the nested i, j loops combined with the inner two-pointer scan cost O(n^3), so the overall time complexity is O(n^3). This is a significant improvement over the O(n^4) brute-force search over every combination of four indices.

Space complexity is O(1) beyond the output list if you ignore the space used by Arrays.sort, though the result itself can hold up to O(n^2) quadruplets in the worst case where many duplicate values exist.

Arrays.sort(numbers) mutates the input array in place. If the caller needs to preserve the original order, sort a clone with numbers.clone() instead of sorting the parameter directly.

The Integer.MIN_VALUE / Integer.MAX_VALUE edge case matters specifically because four large values summed as plain int can overflow before the comparison runs, which is why the program casts the running sum to long.

Interview Follow-up Questions

Once you have the base solution working, expect the interviewer to push on these variations.

• What if you must return the quadruplets without changing the original array’s order? – sort a cloned copy of the array instead of sorting numbers in place, and look up original positions separately if indices are needed.
• What if you need k numbers summing to a target instead of exactly four? – generalize the recursion: reduce a kSum problem to a (k – 1)Sum problem on a smaller sub-array, bottoming out at the two-pointer two-sum case.
• What if you need to answer many different target queries against the same array? – sort once upfront, then consider precomputing all pairwise sums into a hash map keyed by sum so each query can look up complementary pairs in roughly O(n^2) instead of re-deriving them.
• What if the numbers arrive as a continuous stream too large to fit in memory? – two-pointer scanning needs random access to a sorted structure, so true streaming 4Sum is impractical at scale; the realistic answer is to discuss why, and to propose maintaining a bounded sorted window or external sort as a partial mitigation.

Conclusion

The 4Sum problem rewards the same pattern you’d use for two-sum and three-sum: sort first, then shrink the search space with pointers instead of brute-forcing every combination. The trickiest part is not the arithmetic, it’s handling duplicates correctly at every level of nesting.

Try adapting findQuadruplets to return the quadruplets’ original indices, or to generalize it into a kSum method, to confirm you understand why each duplicate-skip check is positioned where it is. You can learn more about array-based problems like this one in our Arrays category.