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 \leq \text{nums.length} \leq 200$
• $-10^9 \leq \text{nums[i]} \leq 10^9$
• $-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.