LC 0018 [M] 4Sum - ALawliet/algorithms GitHub Wiki

prereq: 3sum

---

the difference from 3Sum is to include j we have to add another loop and addend

https://www.youtube.com/watch?v=EYeR-_1NRlQ&ab_channel=NeetCode

# O(n^3)
for # 1
  for # 2
    while l < r # 3, 4 (2Sum II)

class Solution:
    def fourSum(self, arr: List[int], target: int) -> List[List[int]]:
        n = len(arr)

        def threesum(i): # same as 3Sum
          start = i+1

          for j in range(start, n - (4-2)): # new 
              if j > start and arr[j] == arr[j-1]: continue # new, check past left bound which is i+1
                
              l = j + 1 # if we have i and j, then use the rightmost which is j, and +1
              r = n - 1

              while l < r:
                s = arr[i] + arr[j] + arr[l] + arr[r] # just add another variable

                if s == target: 
                  quads.append([arr[i], arr[j], arr[l], arr[r]]) # just add another variable
                  while l < r and arr[l] == arr[l+1]: l += 1 
                  while l < r and arr[r] == arr[r-1]: r -= 1
                  l += 1 ; r -= 1

                elif s < target: # total is too small, go bigger values
                  l += 1

                elif s > target: # total is too big, go smaller values
                  r -= 1 
        
        arr.sort()
        quads = []
        for i in range(0, n - (4-1)):
            if i > 0 and arr[i] == arr[i-1]: continue

            threesum(i) # same as 3Sum but add another outer loop variable

        return quads

class Solution:
    def fourSum(self, arr: List[int], target: int) -> List[List[int]]:
        n = len(arr)

        def search_pairs(i, j): # same as 3Sum
          l = j + 1 # if we have i and j, then use the rightmost which is j, and +1
          r = n - 1

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

            if s == target: 
              quads.append([arr[i], arr[j], arr[l], arr[r]])
              while l < r and arr[l] == arr[l + 1]: l += 1 
              while l < r and arr[r] == arr[r - 1]: r -= 1
              l += 1 ; r -= 1

            elif s < target:
              l += 1

            elif s > target:
              r -= 1 
        
        arr.sort()
        quads = []
        for i in range(0, n - (4-1)): # 4sum, new
            if i > 0 and arr[i] == arr[i-1]: continue

            for j in range(i+1, n - (3-1)): # 3sum 
              if j > i+1 and arr[j] == arr[j - 1]: continue # new, check past left bound which is i+1

              search_pairs(i, j) # same as 3Sum but add j

        return quads

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = []
        
        def kSum(k, start, target, quad):
            if k != 2:
                for i in range(start, len(nums) - k + 1): # if k == 4, then leave the last 3
                    if i > start and nums [i] == nums[i-1]:
                        continue
                    kSum(k - 1, i + 1, target - nums[i], quad + [nums[i]])
            else:
                # at this point, target remains after the first 2 numbers subtracted, so find the last 2 numbers (l, r)
                # base case, two sum II
                l, r = start, 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
                        while l < r and nums[l] == nums[l+1]: l += 1 
                        while l < r and nums[r] == nums[r-1]: r -= 1
                        l += 1 ; r -= 1

        kSum(4, 0, target, [])
        return res