18. 4Sum

https://leetcode.com/problems/4sum/description/

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.

Constraints:

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

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

Algorithm:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> ans;
        if (n < 4) {
            return ans;
        }
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 3; ++i) {
            if (i && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < n - 2; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int k = j + 1, l = n - 1;
                while (k < l) {
                    long long x = (long long) nums[i] + nums[j] + nums[k] + nums[l];
                    if (x < target) {
                        ++k;
                    } else if (x > target) {
                        --l;
                    } else {
                        ans.push_back({nums[i], nums[j], nums[k++], nums[l--]});
                        while (k < l && nums[k] == nums[k - 1]) {
                            ++k;
                        }
                        while (k < l && nums[l] == nums[l + 1]) {
                            --l;
                        }
                    }
                }
            }
        }
        return ans;
    }
};

This 4Sum algorithm finds all unique quadruplets (groups of 4 numbers) from an array that sum up to a given target.

Test Case 1: [1,0,-1,0,-2,2], Target: 0

1. Sort the Array: The input array becomes [-2, -1, 0 , 0 , 1, 2].
2. Loop Structure:

• The outer two loops (i and j) pick two numbers at a time. i starts at the first element, jstarts just after i.
• Then, two pointers (k and l) are used. k starts after j , and l starts at the end of the array.

3. Process:

• For each combination of i and j , you check sums of nums[i] , nums[j], nums[k] , and nums[l].
• If the sum equals the target, add the quadruplet to the result list.
• If the sum is less than the target, move k (to try a larger value).
• If the sum is greater, move l (to try a smaller value).
• Skip duplicates (to ensure only unique quadruplets).

Breakdown:

• For i = 0 (nums[0] = -2), j = 1 (nums[1] = -1):
• k = 2 (nums[2] = 0), l = 5 (nums[5] = 2): sum = (-2) + (-1) + 0 + 2 = -1 (less than 0, move k )
• k = 3 (nums[3] = 0), l = 5 : sum = -2 + (-1) + 0 + 1 = 0 (match, add [-2, -1, 1, 2] to the result)
• Continue with other combinations like i = 0, j = 2 , etc., to find more matches ([-2, 0, 0, 2] , [-1, 0, 0, 1]).

Final result for this case: [[ -2, -1, 1, 2] , [-2, 0, 0, 2] , [-1, 0, 0, 1]].

Get ABHINAV ANAND’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

In short, the algorithm sorts the array and uses a two-pointer approach for efficient searching of all quadruplets that sum to the target. It avoids duplicates by skipping over repeated values.

Test Case: [2, 2, 2, 2, 2], Target: 8

1. Sort the Array: The array is already sorted: [2, 2, 2, 2, 2].
2. Loop Structure:

• The outer loops ( i and j ) pick the first two numbers, while k and l pointers try to find the other two numbers that, when added together, hit the target.

3. Process:

• For i = 0 (nums[0] = 2), j = 1(nums[1] = 2):
• k = 2 (nums[2] = 2), l = 4 (nums[4] = 2): sum = 2 + 2 + 2 + 2 = 8 (match, so add [2, 2, 2, 2] to the result).
• After this, move both k and l , but since all the values are the same, you skip the duplicates.

4. Skipping Duplicates:

• After adding [2, 2, 2, 2] , the algorithm continues, but the subsequent iterations will skip over repeated values to avoid adding the same quadruplet again.

Final result for this case: [[2, 2, 2, 2]].

Summary:

Since all the numbers are the same and the target is 8 , the only valid quadruplet is [2, 2, 2, 2] . The algorithm efficiently avoids duplicates and only returns this unique solution.