Skip to content

LC18. 4Sum

Problem Description

LeetCode Problem xx: 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.

Clarification

  • unique quadruplets
  • index different
  • sum == target
  • no particular order
  • target or array values can be negative

Assumption

Solution

Approach - Sort + Two Pointers

Here are general steps:

  1. Sort array first. Since it involves at least two for-loops \(O(n^2)\), the time complexity from sort \(O(n \log n)\) won't make it worse
  2. Fix nums[i] and nums[j] by iterating the combination of nums[i] and nums[j]. Then the problem become to a smaller problem Two Sum
  3. Using two pointers left and right for remaining elements to find nums[left] + nums[right] == target - nums[i] - nums[j]
Note

Remember to remove duplicates

class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
    n = len(nums)
    quadruplets = []
    nums.sort()
    for i in range(n):
        # Skip duplicates on the 1st element
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, n):
            # Skip duplicates on the 1st element
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            left = j + 1
            right = n - 1
            target_2sum = target - nums[i] - nums[j]
            while left < right:
                s = nums[left] + nums[right]
                if s < target_2sum:
                    left += 1
                elif s > target_2sum:
                    right -= 1
                else:
                    current_quadruplet = [nums[i], nums[j], nums[left], nums[right]]
                    quadruplets.append(current_quadruplet)

                    # Skip duplicates on the 3rd element
                    while left < right and nums[left] == current_quadruplet[2]:
                        left += 1

                    # Skip duplicates on the 4th element
                    while left < right and nums[right] == current_quadruplet[3]:
                        right -= 1

    return quadruplets

Complexity Analysis

  • Time complexity: \(O(n^3)\)
    • Before two for-loops, the sort complexity is \(O(n \log n)\).
    • Two for-loops count for \(O(n^2)\). In the 2nd for loop, using two pointers will take \(O(n)\) time. So time complexity of two for-loops is \(O(n^3)\)
      So the total time complexity is \(O(n \log n) + O(n^3) = O(n^3)\)
  • Space complexity: \(O(sorting)\)
    • Sort algorithm will take some space. For quick sort, the space complexity is \(O(sorting) = O(\log n)\). For merge sort, the space complexity is \(O(sorting) = O(n)\)
    • The rest of code using index variables, which take \(O(1)\) space
      So the total space complexity is \(O(sorting) + O(1) = O(sorting)\)

Test