4 Sum

Problem Statement

Given an integer array nums and an integer target, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

a, b, c, and d are distinct indices.
The sum of the four numbers equals target.

nums[a] + nums[b] + nums[c] + nums[d] == target

The solution set must not contain duplicate quadruplets.

Example 1

Input

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

target = 0

Output

[ [-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Explanation

Let's verify each quadruplet:

[-2, -1, 1, 2]

-2 + (-1) + 1 + 2 = 0

✅ Sum equals target.

[-2, 0, 0, 2]

-2 + 0 + 0 + 2 = 0

✅ Sum equals target.

[-1, 0, 0, 1]

-1 + 0 + 0 + 1 = 0

✅ Sum equals target.

Since all quadruplets are unique and their sum equals the target, they are included in the answer.

Constraints

1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

Prequisite:

2SUM - Two Sum Problem Explained: Brute Force and Optimal Hash Map Solution | SyntaxFlow

Extreme Brute Force Approach

Intuition

The most straightforward way to solve the 4 Sum problem is to try every possible group of four numbers and check whether their sum equals the target.

Since we need four distinct elements:

a + b + c + d = target

we can use four nested loops to generate all possible quadruplets.

For each quadruplet:

Calculate its sum.
If the sum equals the target, add it to the answer.
To avoid duplicates, sort the quadruplet before storing it and use a set.

Although this approach works, it becomes very slow for large arrays because it checks every possible combination of four elements.

Algorithm

Create a set to store unique quadruplets.
Use four nested loops to select four different indices.
Calculate the sum of the four elements.
If the sum equals the target:
- Store the quadruplet in a temporary array.
- Sort the quadruplet.
- Insert it into the set.

5. Convert the set into a vector and return the result.

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {

        int n = nums.size();

        set<vector<int>> st;

        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++) {

                        long long sum =
                            (long long)nums[i] +
                            nums[j] +
                            nums[k] +
                            nums[l];

                        if(sum == target) {

                            vector<int> temp = {
                                nums[i],
                                nums[j],
                                nums[k],
                                nums[l]
                            };

                            sort(temp.begin(), temp.end());

                            st.insert(temp);
                        }
                    }
                }
            }
        }

        return vector<vector<int>>(st.begin(), st.end());
    }
};

this code is not recommended in interviews

Complexity Analysis

Time Complexity

O(n⁴)

Reason:

Four nested loops are used.
Each loop can run up to n times.

n × n × n × n= O(n⁴)

Space Complexity

O(k)

where k is the number of unique quadruplets stored in the set.

Why Is This Inefficient?

Suppose:

n = 200

Then the number of combinations checked is approximately:

200⁴= 1,600,000,000

More than 1.6 billion checks!

This is far too slow.

Better Approach (Using Hash Set)

Intuition

In the brute-force approach, we used four nested loops to select all possible quadruplets.

Can we do better?

Let's fix the first two numbers and find the remaining two numbers more efficiently.

Suppose:

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

target = 0

Assume we have already fixed:

1 and 0

Current sum:

1 + 0 = 1

To reach the target:

remaining = target - 1 = -1

Now we need two numbers whose sum equals:

-1

Instead of using two more loops, we can use a Hash Set to solve this 2 Sum problem efficiently.

Key Observation

After fixing two numbers:

nums[i] and nums[j]

we need:

nums[k] + nums[l]=target - nums[i] - nums[j]

While traversing the remaining array, store previously seen elements in a Hash Set.

For every element:

current = nums[k]

calculate:

required = target
         - nums[i]
         - nums[j]
         - current

If required already exists in the Hash Set, we found a valid quadruplet.

Algorithm

Create a set to store unique quadruplets.
Fix the first element using loop i.
Fix the second element using loop j.
Create an empty Hash Set.
Traverse the remaining elements using k.
Compute the required fourth element.
If the required element exists in the Hash Set:
- Create a quadruplet.
- Sort it.
- Insert it into the set.

8. Otherwise insert the current element into the Hash Set.

9. Convert the set into a vector and return.

Dry Run

C++ Code

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {

        int n = nums.size();

        set<vector<int>> st;

        for(int i = 0; i < n; i++) {

            for(int j = i + 1; j < n; j++) {

                unordered_set<long long> hashSet;

                for(int k = j + 1; k < n; k++) {

                    long long required =
                        (long long)target
                        - nums[i]
                        - nums[j]
                        - nums[k];

                    if(hashSet.find(required) != hashSet.end()) {

                        vector<int> temp = {
                            nums[i],
                            nums[j],
                            nums[k],
                            (int)required
                        };

                        sort(temp.begin(), temp.end());

                        st.insert(temp);
                    }

                    hashSet.insert(nums[k]);
                }
            }
        }

        return vector<vector<int>>(st.begin(), st.end());
    }
};

Complexity Analysis

Time Complexity

O(n³)

Reason:

First loop → O(n)

Second loop → O(n)

Third loop → O(n)

Total:

O(n × n × n)=O(n³)

Space Complexity

O(n)

For the Hash Set used during traversal.

Why Is This Better?

Compared to brute force:

O(n⁴)

we removed one loop by using a Hash Set lookup:

O(1)

This improves the complexity to:

O(n³)

However, we still use extra space and a set to remove duplicates.

The optimal approach sorts the array and uses the Two Pointer technique, achieving the same O(n³) time but with O(1) extra space (excluding the output)

Optimal Approach (Sorting + Two Pointers)

Intuition

In the Better Approach, we fixed two numbers and used a Hash Set to find the remaining two numbers.

Can we avoid the extra space used by the Hash Set?

Yes.

If we sort the array, we can use the Two Pointer technique to find the remaining two numbers efficiently.

Key Observation

We need:

a + b + c + d = target

After fixing the first two numbers:

a = nums[i]
b = nums[j]

we need:

c + d = target - a - b

Now this becomes a 2 Sum problem in a sorted array, which can be solved using two pointers.

Why Sort?

Suppose the array is:

[1,0,-1,0,-2,2]

After sorting:

[-2,-1,0,0,1,2]

Now if the current sum is:

Too Small

sum < target

Move:

left++

to increase the sum.

Too Large

sum > target

move

right--

to decrease the sum

Equal

sum==target

Store the quadruplet and continue searching

Algorithm


Step 1

Sort the array.

sort(nums.begin(), nums.end());
Step 2

Fix the first number.

for(int i = 0; i < n; i++)

Skip duplicates.

Step 3

Fix the second number.

for(int j = i + 1; j < n; j++)

Skip duplicates.

Step 4

Use Two Pointers.

left = j + 1
right = n - 1
Step 5

Calculate:

sum =
nums[i] +
nums[j] +
nums[left] +
nums[right]
Step 6

If:

sum == target

Store answer and skip duplicates.

Step 7

If:

sum < target

Move:

left++
Step 8

If:

sum > target

Move:

right--

Dry run

C++ code:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {

        int n = nums.size();

        // Stores all valid quadruplets
        vector<vector<int>> ans;

        // Sort the array for Two Pointer technique
        sort(nums.begin(), nums.end());

        // Fix the first element
        for(int i = 0; i < n; i++) {

            // Skip duplicate first elements
            if(i > 0 && nums[i] == nums[i - 1])
                continue;

            // Fix the second element
            for(int j = i + 1; j < n; j++) {

                // Skip duplicate second elements
                if(j > i + 1 && nums[j] == nums[j - 1])
                    continue;

                // Two pointers for remaining two numbers
                int left = j + 1;
                int right = n - 1;

                while(left < right) {

                    // Calculate sum of four numbers
                    // Use long long to avoid integer overflow
                    long long sum =
                        (long long)nums[i]
                        + nums[j]
                        + nums[left]
                        + nums[right];

                    // Found a valid quadruplet
                    if(sum == target) {

                        ans.push_back({
                            nums[i],
                            nums[j],
                            nums[left],
                            nums[right]
                        });

                        // Move both pointers
                        left++;
                        right--;

                        // Skip duplicate third elements
                        while(left < right &&
                              nums[left] == nums[left - 1])
                            left++;

                        // Skip duplicate fourth elements
                        while(left < right &&
                              nums[right] == nums[right + 1])
                            right--;
                    }

                    // Sum is smaller than target
                    // Need a larger value
                    else if(sum < target) {
                        left++;
                    }

                    // Sum is greater than target
                    // Need a smaller value
                    else {
                        right--;
                    }
                }
            }
        }

        return ans;
    }
};

Complexity Analysis

Time Complexity

Sorting:

O(n log n)

Two loops:

O(n²)

Two Pointer traversal:

O(n)

Total:

O(n³)
Space Complexity
O(1)

Ignoring the output array.

problem link :

4Sum - LeetCode

Video link:

4 Sum | Brute - Better - Optimal with Codes - YouTube

4 Sum LeetCode Solution with Intuition, Dry Run, and C++ Code

4 Sum

Problem Statement

Example 1

Prequisite:

Extreme Brute Force Approach

Intuition

Algorithm

Complexity Analysis

Better Approach (Using Hash Set)

Intuition

Key Observation

Algorithm

Complexity Analysis

Optimal Approach (Sorting + Two Pointers)

Intuition

Key Observation

Equal

Algorithm

Complexity Analysis

Chakradhar

4 Sum

Problem Statement

Example 1

Prequisite:

Extreme Brute Force Approach

Intuition

Algorithm

Complexity Analysis

Better Approach (Using Hash Set)

Intuition

Key Observation

Algorithm

Complexity Analysis

Optimal Approach (Sorting + Two Pointers)

Intuition

Key Observation

Equal

Algorithm

Complexity Analysis