DSA
4 Sum
Covers: Brute Force, Better, Optimal. Optimal — Time O(nlogn), Space O(t).
Practice Link
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < n a, b, c, and d are distinct. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order.
Prerequisite: Checkout 3 Sum Implementation
Brute Force#
Use four nested loops to check every combination of four indices. Insert sorted quadruplets into a set to eliminate duplicates. O(n⁴) time makes this infeasible for large inputs.
- Check all quads
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
set<vector<int>> st;
int n = nums.size();
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 = 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);
}
}
}
}
}
vector<vector<int>> ans(st.begin(), st.end());
return ans;
}
};
Time Complexity: O(n^4)
Space Complexity - O(2 x no. of the quadruplets),
Better Approach#
Fix the first two elements with two loops (i, j). For the third element k, look up the required fourth value (target - nums[i] - nums[j] - nums[k]) in a hash set built so far in the innermost loop. This reduces the four-loop O(n⁴) brute force to O(n³). The outer set<vector<int>> deduplicates results, adding an O(log m) factor per insertion.
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
set<vector<int>> st;
int n = nums.size();
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
set<long long> hashSet;
for(int k = j+1; k < n; k++){
long long sum = nums[i] + nums[j] + nums[k];
long long fourth = target - sum;
if(hashSet.find(fourth) != hashSet.end()){
vector<int> temp = {nums[i], nums[j], nums[k], fourth};
sort(temp.begin(), temp.end());
st.insert(temp);
}
hashSet.insert(nums[k]);
}
}
}
vector<vector<int>> ans(st.begin(), st.end());
return ans;
}
};
Time Complexity: O(n^3 x logm), n -> size of array, m -> number of elements in set.
Space Complexity - O(2 x no. of the quadruplets) + O(n)
Optimal Approach#
Sort the array. Fix the first two elements with loops i and j, skipping duplicates. Then use a two-pointer sweep (low = j+1, high = n-1) on the remaining subarray — the 4-Sum problem reduces to a 2-Sum on a sorted array. Move pointers based on the current sum vs. target; when a valid quad is found, skip duplicate values before advancing. Sorting costs O(n log n); the three-loop + two-pointer scan costs O(n³).
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> result;
for(int i=0;i<n-3;i++){
if(i>0 && nums[i]==nums[i-1])
continue;
for(int j=i+1; j<n-2;j++){
if(j>i+1 && nums[j]==nums[j-1])
continue;
int low = j+1, high = n-1;
while(low < high){
long long sum = (long long)nums[i];
sum += nums[j];
sum += nums[low];
sum += nums[high];
if(sum<target){
low++;
}else if(sum>target){
high--;
}else{
result.push_back({nums[i], nums[j], nums[low], nums[high]});
while(low < high && nums[low]==nums[low+1])
low++;
while(low < high && nums[high]==nums[high-1])
high--;
low++;
high--;
}
}
}
}
return result;
}
};
⚠️ Overflow trap: Writing long long sum = nums[i] + nums[j] + nums[low] + nums[high] does not prevent overflow — all four operands are int, so the addition is performed in int arithmetic first and only then assigned to long long. Cast the very first operand before any + is evaluated, as done above.
Time Complexity: O(n^3) + O(nlogn)
Space Complexity - O(t) where t is the number of unique triplets