LC 15 & LC 18

Solution to LeetCode 15 3Sum and LeetCode 18 4Sum.

LeetCode 15

3 Sum (Medium) [link]

HashTable is not the best method here. The idea of using HashTable is to record all num1, and find whether -num2-num3 is in the record. The time complexity is O(n^2). The space complexity is O(n). The most difficult barrier we are facing with is to remove duplicated values since the indices of the three values should not be the same.

Double pointers is a better idea. First sort the list. Then for each i, move right and left pointers in the range of nums[i+1:]. If nums[i] + nums[left] + nums[right] > 0, move right pointer to the left by 1 step. If nums[i] + nums[left] + nums[right] < 0 , move left pointer to the right by 1 step. This procedure goes until left = right. Since our target is zero, after sorting the list, any nums[i]>0 would be impossible to form a combination with a sum of zero.

Time complexity O(n^2). Space complexity O(1).

Remember that double pointer method require sorting the list. If the problem requires to return the index, we cannot use double pointers.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        nums.sort()
        for i in range(n):
            left = i+1
            right = n-1
            if nums[i] > 0:
                break # impossible to sum to 0
            if i > 0 and nums[i] == nums[i-1]:
                continue # remove duplicates

            while left < right:
                SUM = nums[i] + nums[left] + nums[right]
                if SUM > 0:
                    right -= 1
                elif SUM < 0:
                    left += 1
                else:
                    res.append([nums[i], nums[left], nums[right]])
                    while left != right and nums[right-1] == nums[right]:
                        right -= 1 # remove duplicates
                    while left != right and nums[left+1] == nums[left]:
                        left += 1 # remove duplicates
                    left += 1
                    right -= 1
        return res

LeetCode 18

4 Sum (Medium) [link]

The same idea as LC 15. We use two nested for loop to determine nums[i]+nums[j], and double pointers to determine nums[k] + nums[i] + nums[left] + nums[right] == target. Instead of breaking if nums[i]>0, break if nums[i] > target && (nums[i] >=0 || target >= 0).

Time complexity O(n^3).

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

        for i in range(n):
            if nums[i] > target and (nums[i] >=0 or target >= 0):
                break # prune the tree
            if i > 0 and nums[i] == nums[i - 1]: continue

            for j in range(i+1,n):
                if j > i+1 and nums[j] == nums[j - 1]: continue
                left = j+1
                right = n-1
                
                while left < right:
                    SUM = nums[i]+nums[j]+nums[left]+nums[right]
                    if SUM > target:
                        right -= 1
                    elif SUM < target:
                        left += 1
                    else:
                        res.append([nums[i], nums[j], nums[left], nums[right]])
                        while left != right and nums[left+1] == nums[left]:
                            left += 1
                        while left != right and nums[right-1] == nums[right]:
                            right -= 1
                        left += 1
                        right -= 1
        return res