18. 4Sum

4Sum

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 <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

We have seen problems like this before — Two Sum, 3 Sum, and 3 Sum Closest.

A simple way to solve the 4 Sum problem is to reduce it to the 3 Sum problem which can further be reduced to the Two Sum problem. Therefore, here our aim is to find a combination of four numbers, and all such combinations are unique.

Approach) Contracting window

We start by looping through the sorted array of numbers, excluding the final 3 (as we need 4 elements to add together). For each number, we then loop through the remaining elements (excluding the final 2, as we now need 3 numbers). 

What we have left, is a series of numbers that can make up the 3rd and 4th numbers in the equation, so here is where we establish our contracting window. 

Our window’s left-hand side goes immediately after the inner loop’s number, and our right-hand side goes to the end of the array. We then sum together the 4 chosen numbers.

If the sum of all 4 numbers matches our target, we add this combination of numbers to a list of potential solutions, and then we contract the window on both sides (as contracting on one side couldn’t possibly give us another solution).

If the sum is below our target, then we move the left-hand side of the window inwards until we reach a different number. Likewise, if the sum is above our target, we move the right-hand side of the window inwards until we reach a different number. Then, the check is performed again

Code:

var fourSum = function (nums, target) {
    let solutionArrays = [];

    // Sort the array
    sortedNums = nums.sort((a, b) => a - b);

    // Loop through the array (excluding the last 3 entries)
    for (let i = 0; i < sortedNums.length - 3; i++) {
        // Check if this is the same number as the last one
        if (i > 0 && sortedNums[i] == sortedNums[i - 1]) {
            continue;
        }

        // Loop through the remaining numbers
        for (let j = i + 1; j < sortedNums.length - 2; j++) {
            // Check if this is the same number as the last one
            if (j > i + 1 && sortedNums[j] == sortedNums[j - 1]) {
                continue;
            }

            // Establish a window from the next number to the end of the array
            let left = j + 1;
            let right = sortedNums.length - 1;

            // Run until the window is closed
            while (left < right) {
                // Add together the current numbers, and each side of the window
                const total =
                    sortedNums[i] +
                    sortedNums[j] +
                    sortedNums[left] +
                    sortedNums[right];

                // If we've reached an answer, add it to the array of answers
                if (total == target) {
                    solutionArrays.push([
                        sortedNums[i],
                        sortedNums[j],
                        sortedNums[left],
                        sortedNums[right],
                    ]);

                    // Move the left-hand edge of the window to the right until it reaches a different number
                    do {
                        left++;
                    } while (sortedNums[left] == sortedNums[left - 1]);

                    // Move the right-hand edge of the window to the left until it reaches a different number
                    do {
                        right--;
                    } while (sortedNums[right] == sortedNums[right + 1]);
                }
                // If we're too low
                else if (total < target) {
                    left++;
                }
                // If we're too high
                else {
                    right--;
                }
            }
        }
    }

    return solutionArrays;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #18. 4Sum

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!