algoadvance

Given an array nums of n integers and an integer target, find all unique quadruplets in the array which gives the sum of target.

Note:

You must write a function:

def fourSum(nums: List[int], target: int) -> List[List[int]]:

Example:

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

Clarifying Questions

  1. Can the input array contain both positive and negative numbers?
    • Yes, the array can contain both.
  2. Can the input contain duplicates?
    • Yes, the array can contain duplicate values.
  3. Is the input array always non-empty?
    • Assume the array has at least one element.
  4. How should the quadruplets be returned?
    • The quadruplets should be returned as a list of lists, where each list represents a quadruplet.

Strategy

  1. Sorting: First, sort the array. This allows us to apply a more systematic approach to finding quadruplets and helps in skipping duplicates effectively.

  2. Iterate with Two Pointers: Use four nested loops, but optimize the innermost two with the two-pointer technique.

  3. Avoid Duplicate Quadruplets:
    • After choosing the first and second elements of the quadruplet, ensure the third and fourth elements (found with the two-pointer technique) do not repeat previous elements.
  4. Optimization:
    • Skip the same elements to avoid redundant calculations.
    • Break out early if the current smallest sum exceeds the target or if the largest possible sum is less than the target.

Code

Here’s the implementation of the above strategy:

from typing import List

def fourSum(nums: List[int], target: int) -> List[List[int]]:
    result = []
    nums.sort()
    n = len(nums)
    
    for i in range(n-3):
        if i > 0 and nums[i] == nums[i-1]:
            continue
            
        if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
            break
            
        if nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target:
            continue
            
        for j in range(i+1, n-2):
            if j > i+1 and nums[j] == nums[j-1]:
                continue
                
            if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:
                break
                
            if nums[i] + nums[j] + nums[n-1] + nums[n-2] < target:
                continue
                
            left, right = j+1, n-1
            
            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]
                if total == target:
                    result.append([nums[i], nums[j], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif total < target:
                    left += 1
                else:
                    right -= 1
                    
    return result

Time Complexity

Thus, the overall time complexity is (O(n^3)).

The space complexity is (O(1)) for extra space (results list doesn’t count as extra space).

Try our interview co-pilot at AlgoAdvance.com