Dare2Solve
The problem requires finding all unique quadruplets in an array that sum up to a given target value. The solution must account for duplicate quadruplets and ensure that the final result contains only unique combinations.
To solve this problem, we need to efficiently find combinations of four numbers that sum up to the target. A brute-force approach would involve checking all possible combinations of four numbers, which is computationally expensive. Instead, sorting the array and using a two-pointer technique can help us efficiently find the required combinations while avoiding duplicates.
Sort the Array: First, sort the input array. Sorting helps in efficiently finding combinations using two pointers and avoids processing duplicate combinations.
Iterate with Two Pointers: Use two nested loops to iterate through the array. The outer loops fix the first two numbers of the quadruplet, and the two-pointer technique is applied on the remaining part of the array to find the other two numbers.
Skip Duplicates: To ensure all quadruplets are unique, skip over duplicate values by checking if the current value is the same as the previous value.
Add to Results: Store each valid quadruplet (which sums up to the target) in a set to avoid duplicates. Convert the set to a list before returning.
(O(n^3)), where (n) is the number of elements in the array. The outer two loops run in (O(n^2)) time, and the two-pointer technique within the innermost loop runs in (O(n)) time.
(O(n^2)) due to the space required to store the result set which contains unique quadruplets. The space complexity is mainly influenced by the number of unique quadruplets that can be stored in the set.
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
set<vector<int>> results;
int n = nums.size();
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) {
long long total = static_cast<long long>(nums[i]) + nums[j] + nums[left] + nums[right];
if (total == target) {
results.insert({nums[i], nums[j], nums[left], nums[right]});
++left;
--right;
while (left < right && nums[left] == nums[left - 1]) ++left; // Skip duplicates
while (left < right && nums[right] == nums[right + 1]) --right; // Skip duplicates
} else if (total < target) {
++left;
} else {
--right;
}
}
}
}
return vector<vector<int>>(results.begin(), results.end());
}
};
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
results = set()
n = len(nums)
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]: # Skip duplicates
continue
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]: # Skip duplicates
continue
left, right = j + 1, n - 1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total == target:
results.add((nums[i], nums[j], nums[left], nums[right]))
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]: # Skip duplicates
left += 1
while left < right and nums[right] == nums[right + 1]: # Skip duplicates
right -= 1
elif total < target:
left += 1
else:
right -= 1
return [list(result) for result in results]
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
Set<List<Integer>> results = new HashSet<>();
for (int i = 0; i < nums.length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.length - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1, right = nums.length - 1;
while (left < right) {
long total = (long)nums[i] + nums[j] + nums[left] + nums[right];
if (total == target) {
results.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (total < target) {
left++;
} else {
right--;
}
}
}
}
return new ArrayList<>(results);
}
}
const removeDupes = (arr) => {
const map = {};
const ret = [];
for(let i=0;i<arr.length;i++){
const hit = map[arr[i]] || 0;
if(hit < 4){
ret.push(arr[i]);
map[arr[i]] = hit + 1;
}
}
return ret;
}
var fourSum = function(nums, target) {
nums = removeDupes(nums).sort();
const ret = {};
for(let i=0;i<nums.length-3;i++){
for(let j=i+1;j<nums.length-2;j++){
for(let k=j+1;k<nums.length-1;k++){
for(let l=k+1;l<nums.length;l++){
const sum = nums[i] + nums[j] + nums[k] + nums[l];
if(sum === target){
const arr = [nums[i], nums[j], nums[k], nums[l]].sort();
ret[arr.join(",")] = arr;
}
}
}
}
}
return Object.values(ret);
};