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 < na,b,c, anddare distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
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]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
Constraints:
1 <= nums.length <= 200-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>-10<sup>9</sup> <= target <= 10<sup>9</sup>
Solution
The approaches to the 4 sum is similar to the 3 sum solutions (link)
Brute Force Approach
We use 4 nested loops to get 4 numbers which sums upto the given target.
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Set<List<Integer>> set = new HashSet<>();
for(int i=0; i<nums.length; i++){
for(int j=i+1; j<nums.length; j++){
for(int k=j+1; k<nums.length; k++){
for(int l=k+1; l<nums.length; l++){
if(nums[i]+nums[j]+nums[k]+nums[l]==target){
List<Integer> ans = new ArrayList<>();
ans.add(nums[i]);
ans.add(nums[j]);
ans.add(nums[k]);
ans.add(nums[l]);
Collections.sort(ans);
set.add(ans);
}
}
}
}
}
return new ArrayList<>(set);
}
}
Better Approach using Set
Eliminating the fourth loop, we retrieve the fourth value through the target. We check whether we have encountered the fourth element within the set up to the current index. If the fourth element is found in the set, we sort and add all four elements to the answer set.
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Set<List<Integer>> ans = new HashSet<>();
for(int i=0; i<nums.length; i++){
for(int j=i+1; j<nums.length; j++){
Set<Long> store = new HashSet<>();
for(int k=j+1; k<nums.length; k++){
long sum = nums[i];
sum+=nums[j];
sum+=nums[k];
long fourth = target - sum;
if(store.contains(fourth)){
store.remove(fourth);
List<Integer> quadruplets = Arrays.asList(nums[i],nums[j],
nums[k],(int)fourth);
Collections.sort(quadruplets);
ans.add(quadruplets);
}else{
store.add((long)nums[k]);
}
}
}
}
return new ArrayList<>(ans);
}
}
Note: Dont add the sum of 3 data types at a time it might give some issues
[1000000000,1000000000,1000000000,1000000000]
target = -294967296
Optimal Approach (4 Pointers)
In the brute-force approach, we employ four nested for loops. In a more efficient approach, we utilize three nested for loops (using a set). In the optimal approach, we use three nested loops, with the core loop being a while loop where pointers play a crucial role without the use of any sets.
In the optimal approach, we first sort the given list. This method is an extension of the three-sum optimal approach. The core idea involves keeping one pointer at the beginning and the other at the end. Here, we initialize four pointers: i, j, k, and l. We iterate i and j systematically from start to end, with i and j starting next to each other. k starts with the next index of j, and i starts at the end. Now, with four pointers, we have four elements. We add these four elements and compare the result with the target.
If the sum value is less than the target, we increase k to the next index because the array is sorted, and increasing the k index will result in an increase in the element value. If the sum value is greater than the target, we decrease i, moving towards the left of the array, resulting in a decrease in the element value since the array is sorted. If the target is equal to the sum, we increment k by 1 and decrement l by 1.
We skip duplicates after each for loop begins. We don't check duplicates for the first element because i and j can take up the same element value (with different indices), and the four-sum might be equal to the target. Similarly, we skip the first index check for j because j and k might take the same value with different indices, and the four-sum might be equal to the target.
There is no need for a set because we are skipping duplicates. Sorting the array at the beginning ensures that the quadruplets are also unique.
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
for(int i=0; i<nums.length; i++){
if(i>0 && nums[i-1]==nums[i]) continue;
for(int j=i+1; j<nums.length; j++){
if(j>i+1 && nums[j-1]==nums[j]) continue;
int k=j+1;
int l=nums.length-1;
while(k<l){
long sum = nums[i];
sum+=nums[j];
sum+=nums[k];
sum+=nums[l];
if(sum<target){
k+=1;
}
else if(sum>target){
l-=1;
}
else{
List<Integer> quad = Arrays.asList(nums[i],nums[j],nums[k],nums[l]);
ans.add(quad);
k+=1;
l-=1;
while(k<l && nums[k-1]==nums[k]) k+=1;
while(k<l && nums[l]==nums[l+1]) l-=1;
}
}
}
}
return new ArrayList<>(ans);
}
}