The problem statement in short is given below:
Given an array of integers nums and an integer target, Find all unique quadruplets [a, b, c, d] in the array such that:
a + b + c + d == target
SOLUTION
FIRST APPROACH
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> fourSum = new ArrayList<List<Integer>>();
Arrays.sort(nums);
int len = nums.length;
for(int i=0; i<len-3; i++) {
// skip duplicates
if(i>0 && nums[i] == nums[i-1])
continue;
// skip duplicates
for(int j=i+1; j<len-2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1])
continue;
int left = j+1;
int right = nums.length-1;
while(left < right) {
long sum = (long) nums[i] + nums[j] + nums[left]
+ nums[right];
if(sum == target) {
fourSum.add(Arrays.asList(nums[i] , nums[j], nums[left] ,
nums[right]));
// skip duplicates
while (left < right && nums[right] == nums[right - 1])
right--;
while (left < right && nums[left] == nums[left + 1])
left++;
left++;
right--;
} //endif
else if(sum < target) {
left++;
}
else if(sum > target) {
right--;
}
} // endwhile
}
}// end outer for loop
return fourSum;
}
You can checkout the code from Github here – 4Sum – Leetcode #18 – FirstAppraoch
PERFORMANCE ANALYSIS
| RUNTIME | 16 ms | Beats 80.88 % |
| MEMORY | 44.10 MB | Beats 46.54 % |
| TIME COMPLEXITY | O (N2) |
| SPACE COMPLEXITY | O (N) |