LeetCode Solutions Blog

4Sum

Number: 18

Difficulty: Medium

Paid? No

Problem Description

Given an array of integers and a target value, the task is to find all unique quadruplets in the array that sum up to the target value. Each quadruplet must consist of four distinct elements from the array.

Key Insights

Sort the array to simplify handling duplicates and employ two pointers efficiently.
Use nested loops to fix the first two numbers and then use the two-pointer technique for the remaining two numbers.
Carefully skip duplicates at each step to ensure all quadruplets in the result are unique.
Manage potential overflow or large input sizes by careful index manipulation.

Space and Time Complexity

Time Complexity: O(n^3)
Space Complexity: O(n) for the output space assuming sorting space does not count.

Solution

The solution begins by sorting the input array to make duplicate elimination easier. Two nested loops are used to select the first and second elements of the quadruplet. For the remaining two numbers, the two-pointer approach is applied by initializing pointers at the start and the end of the remaining subarray. The sum of the four numbers is compared to the target:

If the sum equals the target, the quadruplet is added to the results and the pointers move inward while skipping duplicate numbers.
If the sum is less than the target, the left pointer is moved right to increase the sum.
If the sum is greater than the target, the right pointer is moved left to decrease the sum. This strategy efficiently finds all unique quadruplets that meet the condition.

Code Solutions

# Define a function to find all quadruplets that sum to the target.
def fourSum(nums, target):
    # Sort the input list to facilitate the two-pointer technique and duplicate handling.
    nums.sort()
    quadruplets = []
    n = len(nums)
    
    # First loop: iterate through the list for the first element.
    for i in range(n - 3):
        # Skip duplicate values for the first element.
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # Second loop: iterate for the second element.
        for j in range(i + 1, n - 2):
            # Skip duplicate values for the second element.
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            # Two pointers for the third and fourth element.
            left = j + 1
            right = n - 1
            while left < right:
                current_sum = nums[i] + nums[j] + nums[left] + nums[right]
                # If quadruplet sum matches target, add to result.
                if current_sum == target:
                    quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
                    # Skip duplicates for the third element.
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    # Skip duplicates for the fourth element.
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                # Move left pointer if sum is less.
                elif current_sum < target:
                    left += 1
                # Move right pointer if sum is more.
                else:
                    right -= 1
    return quadruplets

# Example usage:
print(fourSum([1, 0, -1, 0, -2, 2], 0))