Skip to main content

4Sum (LeetCode)

Problem Description​

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]]

Constraints​

  • 1≤nums.length≤2001 \leq \text{nums.length} \leq 200
  • −109≤nums[i]≤109-10^9 \leq \text{nums[i]} \leq 10^9
  • −109≤target≤109-10^9 \leq \text{target} \leq 10^9

Approach​

To solve the problem, we can use the following approach:

  1. Sort the input array in non-decreasing order.
  2. Traverse the array from 0 to n-3 and use a variable i to keep track of the first element in the quadruplet.
  3. If the current element is the same as the previous element, skip it to avoid duplicates.
  4. Traverse the array from i+1 to n-2 and use a variable j to keep track of the second element in the quadruplet.
  5. If the current element is the same as the previous element, skip it to avoid duplicates.
  6. Use two pointers, left = j+1 and right = n-1, to find the other two elements in the quadruplet whose sum equals the target value.
  7. If the sum of the four elements is less than the target value, increment left pointer.
  8. If the sum of the four elements is greater than the target value, decrement right pointer.
  9. If the sum of the four elements is equal to the target value, add the quadruplet to the result and increment left and decrement right pointers.
  10. Skip duplicate values of left and right pointers to avoid duplicate quadruplets.
  11. Return the result.

Solution Code​

Python​

class Solution(object):
def fourSum(self, nums, target):
quadruplets = []
n = len(nums)
# Sorting the array
nums.sort()
for i in range(n - 3):
# Skip duplicates
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n - 2):
# Skip duplicates
if j > i + 1 and nums[j] == nums[j - 1]:
continue
left = j + 1
right = n - 1
while left < right:
sum = nums[i] + nums[j] + nums[left] + nums[right]
if sum < target:
left += 1
elif sum > target:
right -= 1
else:
quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return result

while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1

left += 1
right -= 1
elif sum_ < target:
left += 1
else:
right -= 1

return result

C++​

class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> quadruplets;
int n = nums.size();
// Sorting the array
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 3; i++) {
// Skip duplicates
if (i > 0 && nums[i] == nums[i - 1]){
continue;
}
for (int j = i + 1; j < n - 2; j++) {
// Skip duplicates
if (j > i + 1 && nums[j] == nums[j - 1]){
continue;
}
int left = j + 1;
int right = n - 1;
while (left < right) {
long long sum = static_cast<long long>(nums[i]) + nums[j] + nums[left] + nums[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
quadruplets.push_back({nums[i], nums[j], nums[left], nums[right]});
// Skip duplicates
while (left < right && nums[left] == nums[left + 1]){
left++;
}
while (left < right && nums[right] == nums[right - 1]){
right--;
}
left++;
right--;
}
}
}
}
return quadruplets;
}
};

Java​

class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> quadruplets = new ArrayList<>();
int n = nums.length;
// Sorting the array
Arrays.sort(nums);
for (int i = 0; i < n - 3; i++) {
// Skip duplicates
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < n - 2; j++) {
// Skip duplicates
if (j > i + 1 && nums[j] == nums[j - 1]) {
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) {
left++;
} else if (sum > target) {
right--;
} else {
quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
// Skip duplicates
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
}
}
}
}
return quadruplets;
}
}

Javascript​

var fourSum = function(nums, target) {
nums.sort((a, b) => a - b);
const quadruplets = [];
const n = nums.length;
for (let i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
for (let j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] === nums[j - 1]) {
continue;
}
let left = j + 1;
let right = n - 1;
while (left < right) {
const sum = BigInt(nums[i]) + BigInt(nums[j]) + BigInt(nums[left]) + BigInt(nums[right]);
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
quadruplets.push([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--;
}
}
}
}
return quadruplets;
};

Conclusion​

The given solution sorts the input list and uses a nested loop structure with two pointers to find all unique quadruplets that sum up to the target. By using a set to store the quadruplets, it ensures that duplicates are avoided. The solution efficiently narrows down potential combinations by adjusting the pointers based on the current sum relative to the target. This approach is effective for generating the required output while maintaining uniqueness.

Step-by-Step Algorithm​

  1. Input Validation: Check if the array is null or has fewer than 4 elements. If so, return an empty list.
  2. Sort the Array: Sort the input array nums.
  3. Outer Loop: Iterate over the array with index i from 0 to n-4.
    • Skip duplicate elements by checking if nums[i] == nums[i-1] (for i > 0).
  4. Inner Loop: For each i, iterate with index j from i+1 to n-3.
    • Skip duplicate elements by checking if nums[j] == nums[j-1] (for j > i+1).
  5. Two Pointers: Initialize two pointers left = j+1 and right = n-1.
  6. Finding Quadruplets:
    • While left < right:
      • Calculate the sum of the quadruplet: sum = nums[i] + nums[j] + nums[left] + nums[right].
      • If the sum equals the target:
        • Add [nums[i], nums[j], nums[left], nums[right]] to the result.
        • Move left to the right, skipping duplicates.
        • Move right to the left, skipping duplicates.
      • If the sum is less than the target, move left to the right.
      • If the sum is greater than the target, move right to the left.
  7. Return the Result: After processing all elements, return the list of quadruplets.