4SUM Leetcode Problem 18 [Python Solution]

To sharpen your competitive programming and algorithmic problem-solving skills, lets solve the 4SUM Leetcode Problem.

LeetCode is a renowned platform that offers a plethora of challenges to test your coding skills.

One such problem that we’ll tackle in this guide is the 4SUM problem (LeetCode Problem 18).

This problem falls under the category of “Two Pointers.” We will provide a detailed explanation of the problem, explore its constraints, and present an efficient Python solution to solve it.

If you’re a beginner, don’t worry.

We will break down the problem step by step, provide code examples, and offer a clear understanding of the thought process behind the solution.

By the end of this guide, you’ll be well-equipped to solve similar problems and enhance your problem-solving skills.

Problem Overview

4Sum is a variation of the classic “Two Sum” and “Three Sum” problems.

In this problem, you are given an array of integers nums and a target value.

Your task is to find all unique quadruplets of values (nums[a], nums[b], nums[c], nums[d]) in the array such that:

1. 0 <= a, b, c, d < n, where n is the length of the array.
2. a, b, c, and d are distinct, meaning each index is used only once.
3. The sum of these four values, i.e., nums[a] + nums[b] + nums[c] + nums[d], is equal to the given target value.

You can return the resulting quadruplets in any order.

Example:

Let’s consider an example to illustrate the problem:

Input:

nums = [1, 0, -1, 0, -2, 2]
target = 0

Output:

[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

This example demonstrates that there are three unique quadruplets in the given array that sum up to the target value of 0.

Constraints:

To solve this problem efficiently, it’s essential to understand the constraints:

• The length of the nums array is between 1 and 200.
• The values in the nums array range from -10^9 to 10^9.
• The target value is within the range of -10^9 to 10^9. Now, let’s dive into the solution for the 4sum problem.

Efficient Python Code Solution

To efficiently solve the 4sum problem, we’ll utilize a combination of sorting the input array and employing recursion.

This approach not only meets the constraints but also provides a generic solution that can be applied to problems requiring sums of varying numbers of elements.

Let’s break down the solution step by step.

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:
                return
            if N == 2:
                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:
                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

Now, let’s break down the code and understand how it works.

1. Sorting the Input Array

The first step is to sort the nums array.

Sorting the array is crucial as it allows us to identify and eliminate duplicates efficiently.

Duplicates can be easily detected since they will be adjacent in a sorted array.

nums.sort()

2. Recursive Solution

To find unique quadruplets, we implement a recursive function called findNsum.

This function takes several parameters:

• l: The left pointer.
• r: The right pointer.
• target: The target value we’re trying to achieve.
• N: The number of values we’re currently looking for (decreasing with each recursion).
• result: A list containing the values in the current quadruplet.
• results: A list to store all the valid quadruplets.

We use recursion to simulate the process of selecting values for the quadruplet.

The goal is to start with N = 4 (for a 4Sum problem) and recursively reduce N until it becomes 2. When N reaches 2, we apply a two-pointer approach to find pairs that sum up to the target.

3. Base Cases

We have two base cases in our recursive function:

a. N == 2:

When N reaches 2, we use a two-pointer approach to find pairs that sum up to the target.

This part of the code is similar to the “Two Sum” problem, where we maintain a left pointer (l) and a right pointer (r) within the subarray.

We adjust the pointers based on the current sum and target value.

if N == 2:
    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

b. N > 2:

For N greater than 2, we use a loop to iterate through the array and recursively call findNsum to find the remaining values.

We ensure that we don’t pick the same value in the same position (to avoid duplicates) by checking if nums[i] is not equal to nums[i - 1].

We also update the starting index for the next call and adjust the target value accordingly.

else:
    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)

4. Calling the Recursive Function

Finally, we call the findNsum function initially with N = 4 (for a 4Sum problem) and other necessary parameters to start the recursive process

.

The results list will contain all the unique quadruplets that meet the criteria.

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

This approach efficiently handles the problem, ensuring uniqueness and meeting the constraints.

Now that we’ve covered the code solution, let’s discuss the time and space complexity.

Time and Space Complexity

Time Complexity

The time complexity of our solution is primarily determined by the recursive function findNsum.

In the worst case, the function performs a combination of loops and two-pointer techniques.

As a result, the time complexity is O(n^3), where n represents the number of elements in the nums array.

The sorting step, while essential, doesn’t significantly affect the overall complexity.

Space Complexity

The space complexity is determined by the space required for the results list to store the unique quadruplets.

In the worst case, the space complexity is O(n^2), as there can be a quadratic number of valid quadruplets.

Reasoning Behind Our Approach

Understanding the thought process behind our approach is crucial for becoming a more skilled problem solver.

Let’s summarize the key steps and strategies used in our solution:

1. Sorting the Input: Sorting the input array is essential to identify and eliminate duplicates efficiently.

It also allows us to apply the two-pointer technique effectively.

2. Recursion for Generic Solution: Instead of creating nested loops for different values of k (in this case, k is 4 for a 4Sum problem), we use recursion.

This approach can handle variable values of k, making the solution generic and applicable to similar problems.

3. Two-Pointer Technique: When we reduce N to 2 (in the case of “Two Sum”), we employ a two-pointer technique.

This technique is used to find pairs that sum up to the target efficiently.

4. Base Cases: We define two base cases in our recursive function: one for N == 2 and another for N > 2.

These cases determine how we handle different values of N.

5. Uniqueness: We ensure uniqueness by checking for duplicate values and avoiding the selection of the same value in the same position within a quadruplet.

By implementing these strategies, we create an efficient and generic solution that can handle the 4Sum problem and similar challenges.

Related Interview Questions By Company:

• Combination Sum LeetCode
• Minimum Path Sum LeetCode
• Permutations II LeetCode

Related Interview Questions By Difficulty:

• Boats To Save People LeetCode
• Valid Palindrome II LeetCode
• Rotate Array LeetCode

Conclusion

In this comprehensive guide, we’ve explored the 4sum problem on LeetCode.

We’ve provided a clear and efficient Python solution that uses a combination of sorting, recursion, and two-pointer techniques to find unique quadruplets that sum up to a target value.

By understanding the problem, its constraints, and the reasoning behind our approach, you can enhance your problem-solving skills and tackle more complex algorithmic challenges.

If you’re a beginner, don’t hesitate to practice this solution, experiment with different test cases, and seek further opportunities to apply the knowledge gained.

LeetCode offers a wide range of problems that will help you grow as a programmer and algorithm enthusiast.

Feel free to comment, ask questions, make suggestions, and share this content to help others on their coding journey.

Happy coding!

Question Link: 4Sum LeetCode Problem 18

Now, it’s your turn to dive into the world of algorithmic problem-solving and explore the exciting realm of competitive programming.