Leetcode 18. 4Sum

Problem

Leetcode 18 - 4Sum

Example:

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

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

Approach

We can generalize this question as kSum question where k is the value for amount of elements that we’re looking for.

To make this problem easier, and since we’re not in need for element’s index we can first sort the array

• Base Case (2 Sum):
  • have 2 pointer left, right where left = 0, right = len(nums)-1
  • While left < right start iteration
    • There can be 3 scenarios for target:
      • if nums[left] + nums[right] < target
        • increment left
      • if nums[left] + nums[right] > target
        • decrement right
      • if nums[left] + nums[right] == target
        • add nums[left], nums[right] to one of the result
        • increment left
        • while left < right and nums[left] == nums[left-1] -increment left
• Recursive Case (nSum where n > 2):
  • start for loop from ‘start’ to ‘len(nums) - n + 1’

    (We start the iteration at start because i-x element were run at n+xSum iteration)__ (We end the iteration at len(nums)-n+1 because we need at least n element’s space in result)

    • Since we can have duplicates in array, we check if nums[i] == nums[i-1]
      • continue if nums[i] == nums[i-1]
    • We append nums[i] into result
    • run n-1 Sum
    • pop the last element in result

Here is the Python code for the solution:

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

        def kSum(k, start, target):
            # recursive case
            if k != 2:
                # we start the iteration at start because quad will already include nums[i-1]
                # we end the iteration at len(nums)-k+1 because we want at least k values in the quad list
                for i in range(start, len(nums) - k + 1):
                    if i > start and nums[i] == nums[i-1]:
                        continue
                    quad.append(nums[i])
                    # start recursion with k-1Sum
                    kSum(k-1, i+1, target-nums[i])
                    quad.pop()
                return
            
            # base case, 2sum
            l = start
            r = len(nums)-1
            while l < r:
                if nums[l] + nums[r] < target:
                    l += 1
                elif nums[l] + nums[r] > target:
                    r -= 1
                else:
                    res.append(quad + [nums[l], nums[r]])
                    l += 1
                    while l < r and nums[l] == nums[l-1]:
                        l += 1

        kSum(4, 0, target)
        return res      

Time Complexity and Space Complexity

Time Complexity: $O(n^3)$ Since this is 4Sum, and we’re doing for loop 3 times

Space Complexity: $O(m)$ for output array