How Can You Solve the 4Sum Problem?

The 4Sum problem is a popular question asked in technical interviews, especially for software engineering positions. It involves finding all unique quadruplets in an array that sum up to a given target. This problem can be a bit tricky, but with a structured approach, it becomes manageable.

Let’s consider the problem statement in detail. Given an integer array nums and an integer target, the goal is to find all unique quadruplets nums[a], nums[b], nums[c], nums[d] such that:

a, b, c, and d are distinct indices.
nums[a] + nums[b] + nums[c] + nums[d] = target.

To tackle this problem, we can take inspiration from the approach used in the 3Sum problem, which typically involves sorting the array and using a two-pointer technique. The added complexity in 4Sum is the extra nesting due to the need for four elements. Here’s a step-by-step breakdown of how to implement a solution:

Sort the Array: Begin by sorting the array. Sorting helps in easily avoiding duplicates and allows the use of two pointers efficiently.
Use Nested Loops: The outer two loops will select the first two elements of the quadruplets. The innermost part will utilize the two-pointer technique on the remaining portion of the array.
Skip Duplicates: To ensure that the result contains unique quadruplets, we need to skip over any duplicate values.

Here’s a sample implementation in Python:

python

1def four_sum(nums, target):
2    nums.sort()
3    result = []
4    length = len(nums)
5    
6    for i in range(length - 3):
7        if i > 0 and nums[i] == nums[i - 1]:
8            continue
9
10        for j in range(i + 1, length - 2):
11            if j > i + 1 and nums[j] == nums[j - 1]:
12                continue
13
14            left, right = j + 1, length - 1
15            
16            while left < right:
17                total = nums[i] + nums[j] + nums[left] + nums[right]
18                if total < target:
19                    left += 1
20                elif total > target:
21                    right -= 1
22                else:
23                    # Found a quadruplet
24                    result.append([nums[i], nums[j], nums[left], nums[right]])
25                    while left < right and nums[left] == nums[left + 1]:
26                        left += 1
27                    while left < right and nums[right] == nums[right - 1]:
28                        right -= 1
29                    left += 1
30                    right -= 1
31
32    return result
33
34# Example usage:
35nums = [1, 0, -1, 0, -2, 2]
36target = 0
37print(four_sum(nums, target))

Explanation of the Code:

Sorting: The input array is sorted initially, which prepares it for the two-pointer approach.
Outer Loops: The outer two loops (i and j) iterate through the first two elements. We skip duplicates to ensure unique results.
Two Pointers: The left pointer starts just after j, and the right pointer starts at the end of the array. As the nested loop iterates, we compute the sum of the four chosen elements.
Sum Comparison: Depending on the comparison of total with target, the pointers left and right are adjusted accordingly to explore the next potential quadruplet.