The 4Sum problem is a variation of the classic two-sum problem. The task is to find all unique quadruplets in an array that sum up to a target value. This problem is often encountered in coding interviews and algorithm competitions. In this blog post, we will discuss various solutions for the 4Sum problem, ranging from naive to optimized approaches, with explanations and time complexities.
Problem Description
You are given an array nums of n integers, and an integer target. Your task is to find all unique quadruplets [nums[i], nums[j], nums[k], nums[l]] such that:
0 <= i < j < k < l < nnums[i] + nums[j] + nums[k] + nums[l] == target
Return a list of all unique quadruplets.
Approaches for 4Sum problem
Naive Solution: Brute Force solution for 4Sum problem
The brute force approach is the simplest but least efficient. We will use four nested loops to find all possible quadruplets. For each combination, we check if their sum equals the target. If it does, we add it to the result.
Code (Naive Solution)
import java.util.*;
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
// Sort the array to handle duplicates more easily
Arrays.sort(nums);
for (int i = 0; i < n - 3; i++) {
for (int j = i + 1; j < n - 2; j++) {
for (int k = j + 1; k < n - 1; k++) {
for (int l = k + 1; l < n; l++) {
if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
List<Integer> quadruplet = Arrays.asList(nums[i], nums[j],
nums[k], nums[l]);
if (!result.contains(quadruplet)) {
result.add(quadruplet);
}
}
}
}
}
}
return result;
}
}Time Complexity:
- Time Complexity:
O(n^4)because of the four nested loops. - Space Complexity:
O(1)excluding the space used for storing the result.
The brute force approach is highly inefficient for large arrays, as it requires checking all possible combinations.
Optimized Solution: Using Two Pointers for 4Sum problem
We can optimize the brute force solution by reducing the problem to a two-pointer technique. By sorting the array, we can avoid checking the same quadruplet multiple times, and we can quickly move the pointers to find combinations that sum up to the target.
Code (Optimized Solution)
import java.util.*;
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
if (n < 4) return result;
// Sort the array to enable the two-pointer technique
Arrays.sort(nums);
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue; // Skip duplicates
int left = j + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
result.add(Arrays.asList(nums[i], nums[j], nums[left],
nums[right]));
// Skip duplicates for left pointer
while (left < right && nums[left] == nums[left + 1]) left++;
// Skip duplicates for right pointer
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return result;
}
}Time Complexity:
- Time Complexity:
O(n^3)because we have two loops (iandj) and a two-pointer approach inside (leftandright). - Space Complexity:
O(k)wherekis the number of quadruplets found, due to storing the result.
This approach is much faster than the brute force method, as we reduce the problem to O(n^3) complexity using sorting and the two-pointer technique.
Further Optimization: Hashing (Alternative Approach) for 4Sum problem
Another way to optimize this problem is by using a hash set to store the two sums. Instead of using two pointers, we can store pairs of numbers and their sums in a hash set and then check for the required complementary sum.
Code (Using Hashing)
import java.util.*;
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
if (n < 4) return result;
// Sort the array to handle duplicates
Arrays.sort(nums);
// Map to store pairs and their corresponding indices
Map<Integer, List<int[]>> pairSumMap = new HashMap<>();
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int sum = nums[i] + nums[j];
if (!pairSumMap.containsKey(sum)) {
pairSumMap.put(sum, new ArrayList<>());
}
pairSumMap.get(sum).add(new int[]{i, j});
}
}
// Now find the two sums that add up to the target
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 remainingTarget = target - (nums[i] + nums[j]);
if (pairSumMap.containsKey(remainingTarget)) {
for (int[] pair : pairSumMap.get(remainingTarget)) {
if (pair[0] > j) {
List<Integer> quad = Arrays.asList(nums[i], nums[j],
nums[pair[0]], nums[pair[1]]);
result.add(quad);
}
}
}
}
}
return result;
}
}Time Complexity:
- Time Complexity:
O(n^2)for building the pair sum map andO(n^2)for finding the pairs, so overall it isO(n^2). - Space Complexity:
O(n^2)due to storing the pair sums.
While the time complexity is improved, this method is more complex and less intuitive than the two-pointer method. However, it can be useful when dealing with larger inputs.
Conclusion for 4Sum problem
The 4Sum problem is a classic example of problems that can be solved using different approaches, each with its own trade-offs:
- Naive Solution (Brute Force): Simple but inefficient with a time complexity of
O(n^4). - Optimized Solution (Two Pointers): A much faster solution with time complexity
O(n^3)and reduced space usage. - Hashing Solution: A hybrid approach using a hash map to store pair sums, with a time complexity of
O(n^2).
For most practical purposes, the Two Pointer approach strikes the best balance between simplicity and efficiency.
Feel free to try out the code on Leetcode to get more familiar with solving similar problems efficiently!