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, anddare 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^9Prequisite:
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
ntimes.
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 = 0Assume we have already fixed:
1 and 0
Current sum:
1 + 0 = 1To reach the target:
remaining = target - 1 = -1
Now we need two numbers whose sum equals:
-1Instead 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]
- currentIf 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 = targetAfter fixing the first two numbers:
a = nums[i]
b = nums[j]we need:
c + d = target - a - bNow 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 < targetMove:
left++to increase the sum.
Too Large
sum > targetmove
right--to decrease the sum
Equal
sum==targetStore 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 :
Video link: