18. 4Sum

Medium LeetCode

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.

Example 1

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

Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2

Input: nums = [2,2,2,2,2], target = 8

Output: [[2,2,2,2]]

Constraints

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

How to solve the problem

• Hash Table Using Set Code

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

        # Preprocess: store all pairs (i, j) whose sum is nums[i] + nums[j]
        for i in range(n):
            for j in range(i + 1, n):
                two_sum = nums[i] + nums[j]
                two_sum_map[two_sum].append((i, j))

        # Search for two pairs whose sums add up to the target
        for sum1 in two_sum_map:
            sum2 = target - sum1
            if sum2 not in two_sum_map:
                continue

            list1 = two_sum_map[sum1]
            list2 = two_sum_map[sum2]

            for (i, j) in list1:
                for (k, l) in list2:
                    # Ensure all indices are distinct
                    if len(set([i, j, k, l])) == 4:
                        quad = sorted([nums[i], nums[j], nums[k], nums[l]])
                        res.add(tuple(quad))  # Use a set to avoid duplicates

        # Convert the result back to list of lists
        return [list(r) for r in res]

Complexity

• Time complexity: O(n^4)
• Space complexity: O(n)