Problem Statement in English

You’re given an array nums of n integers and an integer target. Find all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that the sum of the four elements is equal to target (i.e., nums[a] + nums[b] + nums[c] + nums[d] == target).

Return the list of unique quadruplets in any order.

Approach

We can mix this with a previous problem we’ve solved 3Sum to solve this problem. The idea is to use two nested loops to fix the first two numbers and then use the two-pointer technique to find the other two numbers.

Apart from that everything else stays the exact same.

And we’re done!

Solution in Python


class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        res = []
        n = len(nums)
        nums.sort()

        for i in range(n):
            if i > 0 and nums[i - 1] == nums[i]: continue

            for j in range(i + 1, n):
                if j > i + 1 and nums[j - 1] == nums[j]: continue

                l, r = j + 1, n - 1

                while l < r:
                    s = nums[i] + nums[j] + nums[l] + nums[r]

                    if s > target:
                        r -= 1
                    elif s < target:
                        l += 1
                    else:
                        res.append([nums[i], nums[j], nums[l], nums[r]])
                        l += 1
                        r -= 1

                        while l < r and nums[l - 1] == nums[l]: l += 1
                        while l < r and nums[r] == nums[r + 1]: r -= 1

        return res

Complexity

  • Time: $O(n^3)$
    Since we have 3 nested loops, the time complexity is $O(n^3)$, where $n$ is the length of the input array nums.

  • Space: $O(1)$
    Since we are not using any extra space that scales with the input size, the space complexity is $O(1)$.

And we are done.