Searching & SortingProblem 11 of 36
Find four elements that sum to a given value
Problem Statement
Given an array of integers and a target sum, find all unique quadruplets (four elements) that sum to the target value.
Constraints:
- Return all unique quadruplets (no duplicates)
- The same element cannot be used twice in a quadruplet
- Order of elements within a quadruplet doesn't matter
Example:
- Input:
arr = [1, 0, -1, 0, -2, 2],target = 0 - Output:
[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
Example 2:
- Input:
arr = [2, 2, 2, 2, 2],target = 8 - Output:
[[2, 2, 2, 2]]
Approach 1: Brute Force (Four Loops)
Intuition
Check all possible combinations of four elements.
Algorithm
- Use four nested loops to select four elements
- If their sum equals target, add to result
- Use a set to avoid duplicates
java
import java.util.*;
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Set<List<Integer>> resultSet = new HashSet<>();
int n = nums.length;
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++) {
long sum = (long) nums[i] + nums[j] + nums[k] + nums[l];
if (sum == target) {
List<Integer> quad = Arrays.asList(nums[i], nums[j], nums[k], nums[l]);
Collections.sort(quad);
resultSet.add(quad);
}
}
}
}
}
return new ArrayList<>(resultSet);
}
}Complexity Analysis
- Time Complexity: O(n⁴) - Four nested loops
- Space Complexity: O(n⁴) - Set to store quadruplets (worst case)
Approach 2: Sorting + Two Pointers (Better)
Intuition
Sort the array, fix two elements, use two pointers for the remaining two.
Algorithm
- Sort the array
- Fix first element with loop i
- Fix second element with loop j
- Use two pointers (left, right) for remaining two elements
- Skip duplicates at each level
java
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;
Arrays.sort(nums);
for (int i = 0; i < n - 3; i++) {
// Skip duplicates
if (i > 0 && nums[i] == nums[i - 1]) continue;
// Early termination
if ((long) nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break;
if ((long) nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target) continue;
for (int j = i + 1; j < n - 2; j++) {
// Skip duplicates
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
// Early termination
if ((long) nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;
if ((long) nums[i] + nums[j] + nums[n-2] + nums[n-1] < target) continue;
int left = j + 1;
int right = n - 1;
while (left < right) {
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return result;
}
}Dry Run Example
nums = [1, 0, -1, 0, -2, 2], target = 0
sorted = [-2, -1, 0, 0, 1, 2]
i=0 (nums[i]=-2):
j=1 (nums[j]=-1):
left=2, right=5: sum = -2 + -1 + 0 + 2 = -1 < 0, left++
left=3, right=5: sum = -2 + -1 + 0 + 2 = -1 < 0, left++
left=4, right=5: sum = -2 + -1 + 1 + 2 = 0 == 0 ✓
Add [-2, -1, 1, 2]
j=2 (nums[j]=0):
left=3, right=5: sum = -2 + 0 + 0 + 2 = 0 == 0 ✓
Add [-2, 0, 0, 2]
i=1 (nums[i]=-1):
j=2 (nums[j]=0):
left=3, right=5: sum = -1 + 0 + 0 + 2 = 1 > 0, right--
left=3, right=4: sum = -1 + 0 + 0 + 1 = 0 == 0 ✓
Add [-1, 0, 0, 1]
Result: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
Complexity Analysis
- Time Complexity: O(n³) - Two loops + two pointers
- Space Complexity: O(1) - Excluding output space
Approach 3: HashMap of Pair Sums (Optimal for Finding)
Intuition
Precompute all pair sums. For each pair, check if complement pair exists.
Algorithm
- Compute all pair sums and store in hashmap
- For each pair (i, j), look for pairs that sum to target - (nums[i] + nums[j])
- Ensure all four indices are distinct
java
import java.util.*;
public class Solution {
public List<List<Integer>> fourSumHashMap(int[] nums, int target) {
Set<List<Integer>> resultSet = new HashSet<>();
int n = nums.length;
if (n < 4) return new ArrayList<>();
// Map: sum -> list of index pairs
Map<Long, List<int[]>> pairSums = new HashMap<>();
// Store all pair sums
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
long sum = (long) nums[i] + nums[j];
pairSums.computeIfAbsent(sum, k -> new ArrayList<>()).add(new int[]{i, j});
}
}
// Find quadruplets
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
long complement = (long) target - nums[i] - nums[j];
if (pairSums.containsKey(complement)) {
for (int[] pair : pairSums.get(complement)) {
int k = pair[0], l = pair[1];
if (k != i && k != j && l != i && l != j) {
List<Integer> quad = Arrays.asList(nums[i], nums[j], nums[k], nums[l]);
Collections.sort(quad);
resultSet.add(quad);
}
}
}
}
}
return new ArrayList<>(resultSet);
}
}Complexity Analysis
- Time Complexity: O(n² log n) average (with good hashing)
- Space Complexity: O(n²) - Storing all pair sums
K-Sum Generalization
Key Takeaways
- Sorting + Two Pointers: Reduces 4Sum to 3Sum to 2Sum
- Early Termination: Pruning with min/max sums greatly improves performance
- Duplicate Handling: Skip duplicates at each level to avoid duplicate quadruplets
- HashMap Approach: Trade space for time, but complex index management
- Overflow Handling: Use long long for sum calculations
- K-Sum Generalization: Can extend to any k using recursion