We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

4Sum

Difficulty: Medium

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.

Key Insights

We need to find quadruplets that sum up to a target value.
To avoid duplicates, we should use a set or sort the array and skip over duplicate values.
A two-pointer approach can be applied after fixing the first two numbers of the quadruplet.
The time complexity can be reduced by sorting the array first, which allows us to use efficient searching for the remaining two numbers.

Space and Time Complexity

Time Complexity: O(n^3)
Space Complexity: O(1) (excluding the space required for the output)

Solution

The approach involves:

Sorting the input array to facilitate the use of two pointers.
Fixing two numbers and then using two pointers to find the other two numbers that complete the quadruplet to match the target.
Collecting unique quadruplets by ensuring no duplicates are added to the result list.

Code Solutions

def fourSum(nums, target):
    nums.sort()  # Sort the array
    result = []
    n = len(nums)

    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:  # Skip duplicates
            continue
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:  # Skip duplicates
                continue
            left, right = j + 1, n - 1
            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]
                if total < target:
                    left += 1
                elif total > target:
                    right -= 1
                else:
                    result.append([nums[i], nums[j], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:  # Skip duplicates
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:  # Skip duplicates
                        right -= 1
                    left += 1
                    right -= 1
    return result

← Back to All Questions