LeetCode #18: 4Sum - Stack Thrive

Hello, coding enthusiasts! Today, we’re solving the “4Sum” problem from LeetCode using Python and JavaScript.

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

Constraints

1 <= nums.length <= 200
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹

Analysis

The problem is to find all unique quadruplets in the array that sum up to the target. This problem is a variant of the 2Sum and 3Sum problems, but instead of finding pairs or triplets that sum to a target, we need to find quadruplets.

This problem is interesting because it involves handling the complexity of iterating over the array elements in a way that we can check for all possible quadruplets, and at the same time, we need to ensure that the quadruplets are unique.

Approach

Here’s a step-by-step approach to solve this problem:

Sort the Array: We start by sorting the array. This is important because we will be using a two-pointer technique which requires the array to be sorted.
Initialize Variables: We initialize an empty list quadruplets to store all unique quadruplets.
Iterate Over Array: We iterate over the array with a pointer i from 0 to length-4. This is because we need at least four numbers to form a quadruplet.
Nested Iteration: Inside the first loop, we run another loop with a pointer j from i+1 to length-3. Inside this loop, we use a two-pointer technique to find the pair in the sorted array that, along with nums[i] and nums[j], has the sum equal to the target. The two pointers are k and l, where k is initialized to j+1 and l is initialized to the last index of the array.
Move Pointers: If the sum of the values at the i, j, k, and l pointers is less than the target, we increment k. If the sum is greater than the target, we decrement l. If the sum is equal to the target, we add the quadruplet to the list of quadruplets and move both k and l.
Avoid Duplicates: To avoid adding duplicate quadruplets, we add checks to continue the loop when the current number is the same as the previous number for pointers i, j, k, and l.

Time Complexity

The time complexity of this approach is O(n^3), where n is the number of elements in the array. This is because we are iterating over the array with two pointers and for each iteration, we are using two pointers to find the pair that, along with nums[i] and nums[j], has the sum equal to the target.

Space Complexity

The space complexity is O(n), as we are using an extra space to store the quadruplets.

Code

Python

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        def findNsum(l, r, target, N, result, results):
            if r-l+1 < N or N < 2 or target < nums[l]*N or target > nums[r]*N:  # early termination
                return
            if N == 2:  # two pointers solve sorted 2-sum problem
                while l < r:
                    s = nums[l] + nums[r]
                    if s == target:
                        results.append(result + [nums[l], nums[r]])
                        l += 1
                        while l < r and nums[l] == nums[l - 1]:
                            l += 1
                    elif s < target:
                        l += 1
                    else:
                        r -= 1
            else:  # recursively reduce N
                for i in range(l, r+1):
                    if i == l or (i > l and nums[i-1] != nums[i]):
                        findNsum(i+1, r, target-nums[i], N-1, result+[nums[i]], results)

        nums.sort()
        results = []
        findNsum(0, len(nums)-1, target, 4, [], results)
        return results

JavaScript

var fourSum = function(nums, target) {
    nums.sort((a, b) => a - b);
    const results = [];
    findNSum(0, nums.length - 1, target, 4, [], results);
    return results;

    function findNSum(l, r, target, N, result, results) {
        if (r - l + 1 < N || N < 2 || target < nums[l] * N || target > nums[r] * N) {
            return;
        }
        if (N === 2) {
            while (l < r) {
                const s = nums[l] + nums[r];
                if (s === target) {
                    results.push(result.concat([nums[l], nums[r]]));
                    l++;
                    while (l < r && nums[l] === nums[l - 1]) {
                        l++;
                    }
                } else if (s < target) {
                    l++;
                } else {
                    r--;
                }
            }
        } else {
            for (let i = l; i <= r; i++) {
                if (i === l || (i > l && nums[i - 1] !== nums[i])) {
                    findNSum(i + 1, r, target - nums[i], N - 1, result.concat([nums[i]]), results);
                }
            }
        }
    }
};

Conclusion

In this post, we tackled the “4Sum” problem from LeetCode.

The time complexity of the “4Sum” problem is O(n^3), where n is the number of elements in the array. This is because we are iterating over the array with two pointers and for each iteration, we are using two pointers to find the pair that, along with nums[i] and nums[j], has the sum equal to the target.

The space complexity is O(n), as we are using an extra space to store the quadruplets.

With this approach, we successfully solved the “4Sum” problem from LeetCode using Python and JavaScript.

Happy coding!

Learn More: