š Problem Link: https://leetcode.com/problems/4sum/
The 4Sum problem is an extension of the famous Two Sum and Three Sum problems. The goal is to find all unique quadruplets whose sum equals the target.
While the brute force approach checks every possible combination of four numbers, the optimal solution leverages sorting, recursion, and the Two Pointer technique to efficiently solve the problem.
Brute Force Approach
Intuition
Generate every possible combination of four elements using four nested loops.
For each quadruplet, check whether its sum equals the target. If yes, add it to the answer while ensuring duplicates are avoided.
This works but becomes very slow as the array size grows.
Time & Space Complexity
- Time Complexity: O(Nā“)
- Space Complexity: O(1) (excluding result storage)
Java Solution
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Set<List<Integer>> set = new HashSet<>();
int n = nums.length;
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 sum = (long) nums[i]
+ nums[j]
+ nums[k]
+ nums[l];
if(sum == target) {
List<Integer> temp =
Arrays.asList(
nums[i],
nums[j],
nums[k],
nums[l]
);
Collections.sort(temp);
set.add(temp);
}
}
}
}
}
return new ArrayList<>(set);
}
}
Optimizing the Solution
The key idea is to sort the array first.
Once sorted:
- Duplicates can be skipped easily.
- We can reduce the problem from 4Sum ā 3Sum ā 2Sum.
- The final 2Sum can be solved efficiently using the Two Pointer technique.
This generalized approach is commonly known as the K-Sum Pattern.
Optimal Approach (K-Sum + Two Pointers)
Time & Space Complexity
- Time Complexity: O(NĀ³)
- Space Complexity: O(K) Recursive Stack
Java Solution
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
return kSum(nums, target, 0, 4);
}
public List<List<Integer>> kSum(int[] nums,
long target,
int start,
int k) {
List<List<Integer>> res = new ArrayList<>();
if(start == nums.length) {
return res;
}
long average = target / k;
if(nums[start] > average ||
average > nums[nums.length - 1]) {
return res;
}
if(k == 2) {
return twoSum(nums, target, start);
}
for(int i = start; i < nums.length; i++) {
if(i == start || nums[i] != nums[i - 1]) {
for(List<Integer> subset :
kSum(nums,
target - nums[i],
i + 1,
k - 1)) {
List<Integer> temp =
new ArrayList<>();
temp.add(nums[i]);
temp.addAll(subset);
res.add(temp);
}
}
}
return res;
}
public List<List<Integer>> twoSum(int[] nums,
long target,
int start) {
List<List<Integer>> res =
new ArrayList<>();
int left = start;
int right = nums.length - 1;
while(left < right) {
long sum = nums[left] + nums[right];
if(sum < target ||
(left > start &&
nums[left] == nums[left - 1])) {
left++;
} else if(sum > target ||
(right < nums.length - 1 &&
nums[right] == nums[right + 1])) {
right--;
} else {
res.add(
Arrays.asList(
nums[left++],
nums[right--]
)
);
}
}
return res;
}
}
Dry Run
Input
nums = [1,0,-1,0,-2,2]
target = 0
After Sorting
[-2,-1,0,0,1,2]
Fix the first element:
-2
Remaining target becomes:
2
Now recursively solve the remaining 3Sum problem and eventually reduce it to 2Sum.
Valid quadruplets found:
[-2,-1,1,2]
[-2,0,0,2]
[-1,0,0,1]
Final Answer
[
[-2,-1,1,2],
[-2,0,0,2],
[-1,0,0,1]
]
Key Interview Takeaway
The real learning in this problem isn't just finding quadruplets.
It's recognizing how a complex problem like 4Sum can be reduced recursively into 3Sum and eventually 2Sum, where the Two Pointer technique does the heavy lifting.
This K-Sum pattern is a powerful interview concept and can be extended to solve 5Sum, 6Sum, and beyond.
Follow along as I break down the intuition, brute force, better, and optimal solutions for every problem.
Master K-Sum once, and every Sum problem starts looking like the same pattern.
Top comments (0)