4 Sum Problem Optimal Solution using Two Pointers

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given an array of integers arr and an integer target, find all unique quadruplets (four numbers) in the array that sum up to the given target value.

  • A valid quadruplet is a set of four elements (a, b, c, d) such that a + b + c + d = target.
  • All quadruplets must be unique. That means no two quadruplets can contain the same set of four numbers, even in a different order.
  • The input array can contain duplicate numbers, but the result must contain only unique combinations.

If no such quadruplets exist, return an empty list.

Examples❯

Input Array Target Quadruplets Description
[1, 0, -1, 0, -2, 2] 0 [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] Three unique quadruplets sum to 0
[2, 2, 2, 2, 2] 8 [[2, 2, 2, 2]] Duplicates allowed in input, but result is unique
[1, 2, 3, 4] 50 [] No combination of four elements adds to 50
[0, 0, 0, 0] 0 [[0, 0, 0, 0]] All elements are zero and they form one valid result
[1, -2, -5, -4, -3, 3, 3, 5] -11 [[-5, -4, -3, 1]] Only one valid quadruplet with negative target
[1, 2, 3] 6 [] Less than 4 elements; no quadruplet is possible
[] 0 [] Empty input array returns an empty list

Solution❯

Understanding the Problem

The "4 Sum" problem asks us to find all unique quadruplets (groups of four numbers) in a given array that add up to a specific target sum. The array can include positive numbers, negative numbers, and duplicates. For example, if the input is nums = [1, 0, -1, 0, -2, 2] and target = 0, we need to find all unique sets of four numbers whose sum equals 0.

Example

Let’s take nums = [1, 0, -1, 0, -2, 2] and target = 0.

After sorting the array, we get: [-2, -1, 0, 0, 1, 2]

We want to find combinations like [-2, -1, 1, 2] because -2 + -1 + 1 + 2 = 0.

Step-by-Step Approach

Instead of using brute force to try every combination of 4 numbers (which is very slow), we use a structured and efficient method:

Step 1: Sort the Array

Sorting helps us to:

  • Quickly skip duplicate values
  • Use the two-pointer technique for finding pairs

Step 2: Use Nested Loops to Fix First Two Numbers

We use two nested for loops to pick the first and second numbers of the quadruplet.

Step 3: Two-Pointer Technique for Remaining Two Numbers

Once the first two numbers are fixed, we use two pointers — left and right — to scan for the remaining two numbers that complete the quadruplet.

Step 4: Skip Duplicates

After each valid combination, we move the left and right pointers to skip over any duplicate values to avoid repeating the same quadruplets in the result.

Incorporating Edge Cases

Case 1: Empty Array or Less Than 4 Elements

If the array is empty or has fewer than 4 elements, we can’t form a quadruplet. Return an empty list: []

Case 2: All Elements Are the Same

Example: [2, 2, 2, 2, 2] with target = 8 → Only one valid quadruplet: [2, 2, 2, 2]. Skip remaining duplicates.

Case 3: No Valid Combination

If no group of 4 numbers adds up to the target, return an empty list.

Case 4: Negative and Positive Mix

The presence of both negative and positive numbers means valid quadruplets can be scattered across the array — sorting helps align them for scanning.

Why This Solution Works

By sorting and using nested loops with two pointers:

  • We reduce time complexity to O(n³) — much faster than checking every O(n⁴) combination.
  • We ensure that no duplicate sets are added to the result.
  • We handle all edge cases with clear, logical checks.

Finally

This method is efficient, beginner-friendly, and scalable. It teaches good habits like sorting early, avoiding duplicate work, and breaking problems down step-by-step.

Algorithm Steps❯

  1. Given an array arr of size n and a target value target.
  2. Sort the array in ascending order.
  3. Fix the first element with index i (0 to n-4).
  4. Fix the second element with index j (i+1 to n-3).
  5. Use two pointers left = j+1 and right = n-1 to find two other numbers.
  6. If the sum of the four elements equals target, store the quadruplet.
  7. Move pointers intelligently while skipping duplicates to find all unique quadruplets.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
TS
#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

void fourSum(int* arr, int n, int target) {
    qsort(arr, n, sizeof(int), compare);

    for (int i = 0; i < n - 3; i++) {
        if (i > 0 && arr[i] == arr[i-1]) continue;
        for (int j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && arr[j] == arr[j-1]) continue;
            int left = j + 1, right = n - 1;
            while (left < right) {
                int total = arr[i] + arr[j] + arr[left] + arr[right];
                if (total == target) {
                    printf("%d %d %d %d\n", arr[i], arr[j], arr[left], arr[right]);
                    left++;
                    right--;
                    while (left < right && arr[left] == arr[left-1]) left++;
                    while (left < right && arr[right] == arr[right+1]) right--;
                } else if (total < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
}

int main() {
    int arr[] = {1, 0, -1, 0, -2, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 0;
    fourSum(arr, n, target);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n^3)Even in the best case, we use two nested loops and a two-pointer approach, leading to cubic time complexity when scanning all possible quadruplets.
Average CaseO(n^3)For each pair of the first two elements (i and j), we use a two-pointer scan through the remaining array. This results in O(n³) combinations on average.
Worst CaseO(n^3)The algorithm always uses two nested loops plus a two-pointer traversal, so the worst-case complexity remains cubic.

Space Complexity❯

O(1) (excluding output)

Explanation: Only a few pointers and loop variables are used for the computation. However, the space needed to store the resulting quadruplets depends on the number of valid combinations found.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...