Last updated on January 13th, 2025 at 09:38 pm
Here, we see a 4Sum LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Dynamic Programming, Recursion
Companies
Level of Question
Medium
4Sum LeetCode Solution
Table of Contents
1. Problem Statement
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 < n
- a, b, c, and d are 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]]
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Two Pointers. This pattern is evident because the algorithms use two pointers (low and high) to traverse the sorted array and find combinations of numbers that sum up to the target. The two-pointer approach is nested within loops to handle the higher-level combinations (e.g., the outer loops for the first two numbers in the quadrupled).
3. Code Implementation in Different Languages
3.1 4Sum C++
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> total;
int n = nums.size();
if(n<4) return total;
sort(nums.begin(),nums.end());
for(int i=0;i<n-3;i++)
{
if(i>0&&nums[i]==nums[i-1]) continue;
if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
for(int j=i+1;j<n-2;j++)
{
if(j>i+1&&nums[j]==nums[j-1]) continue;
if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
int left=j+1,right=n-1;
while(left<right){
int sum=nums[left]+nums[right]+nums[i]+nums[j];
if(sum<target) left++;
else if(sum>target) right--;
else{
total.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
do{left++;}while(nums[left]==nums[left-1]&&left<right);
do{right--;}while(nums[right]==nums[right+1]&&left<right);
}
}
}
}
return total;
}
};
3.2 4Sum Java
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
int len = nums.length;
if (nums == null || len < 4)
return res;
Arrays.sort(nums);
int max = nums[len - 1];
if (4 * nums[0] > target || 4 * max < target)
return res;
int i, z;
for (i = 0; i < len; i++) {
z = nums[i];
if (i > 0 && z == nums[i - 1])
continue;
if (z + 3 * max < target)
continue;
if (4 * z > target)
break;
if (4 * z == target) {
if (i + 3 < len && nums[i + 3] == z)
res.add(Arrays.asList(z, z, z, z));
break;
}
threeSumForFourSum(nums, target - z, i + 1, len - 1, res, z);
}
return res;
}
public void threeSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList,
int z1) {
if (low + 1 >= high)
return;
int max = nums[high];
if (3 * nums[low] > target || 3 * max < target)
return;
int i, z;
for (i = low; i < high - 1; i++) {
z = nums[i];
if (i > low && z == nums[i - 1])
continue;
if (z + 2 * max < target)
continue;
if (3 * z > target)
break;
if (3 * z == target) {
if (i + 1 < high && nums[i + 2] == z)
fourSumList.add(Arrays.asList(z1, z, z, z));
break;
}
twoSumForFourSum(nums, target - z, i + 1, high, fourSumList, z1, z);
}
}
public void twoSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList,
int z1, int z2) {
if (low >= high)
return;
if (2 * nums[low] > target || 2 * nums[high] < target)
return;
int i = low, j = high, sum, x;
while (i < j) {
sum = nums[i] + nums[j];
if (sum == target) {
fourSumList.add(Arrays.asList(z1, z2, nums[i], nums[j]));
x = nums[i];
while (++i < j && x == nums[i])
;
x = nums[j];
while (i < --j && x == nums[j])
;
}
if (sum < target)
i++;
if (sum > target)
j--;
}
return;
}
}
3.3 4Sum JavaScript
var fourSum = function(nums, target) {
nums.sort((a, b) => a - b);
const result = []
for(let i = 0; i < nums.length - 3; i++) {
for(let j = i + 1; j < nums.length - 2; j++) {
let low = j + 1;
let high = nums.length - 1
while(low < high) {
const sum = nums[i] + nums[j] + nums[low] + nums[high];
if(sum === target) {
result.push([nums[i], nums[j], nums[low], nums[high]])
while(nums[low] === nums[low + 1]) low++;
while(nums[high] === nums[high - 1]) high--;
low++;
high--;
} else if(sum < target) {
low++
} else {
high--
}
}
while(nums[j] === nums[j + 1]) j++;
}
while(nums[i] === nums[i + 1]) i++;
}
return result
};
3.4 4Sum Python
class Solution(object):
def fourSum(self, nums, target):
nums.sort()
results = []
self.findNsum(nums, target, 4, [], results)
return results
def findNsum(self, nums, target, N, result, results):
if len(nums) < N or N < 2: return
if N == 2:
l,r = 0,len(nums)-1
while l < r:
if nums[l] + nums[r] == target:
results.append(result + [nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while r > l and nums[r] == nums[r + 1]:
r -= 1
elif nums[l] + nums[r] < target:
l += 1
else:
r -= 1
else:
for i in range(0, len(nums)-N+1):
if target < nums[i]*N or target > nums[-1]*N:
break
if i == 0 or i > 0 and nums[i-1] != nums[i]:
self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
return
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n³) | O(n) |
| Java | O(n³) | O(n) |
| JavaScript | O(n³) | O(n) |
| Python | O(n³) | O(n) |
- Time Complexity: The dominant factor is the triple nested loop structure, which results in O(n³) complexity. Sorting (O(n log n)) is negligible compared to this.
- Space Complexity: The space complexity is O(n) due to the sorting step. No additional data structures are used that grow with the input size.
- Efficiency: The two-pointer approach reduces the complexity of finding pairs from O(n²) to O(n), making the algorithm more efficient than a brute-force approach.