Algorithm - Two Pointers (2)

Two pointers problem set (2)

• 11.Container With Most Water
• 532.K-diff Pairs in an Array

N Sum problem set:

• 1.Two Sum
• 167.Two Sum II - Input array is sorted
• 15.3Sum
• 16.3Sum Closest
• 18.4Sum

11. Container With Most Water

def maxArea(self, height: List[int]) -> int:
    left = 0
    right = len(height) - 1
    res = 0
    while left < right:
        cur = (right - left) * min(height[left], height[right])
        res = max(cur, res)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return res

532. K-diff Pairs in an Array

Two Pointers

def findPairs(self, nums: List[int], k: int) -> int:
    res = 0
    l, r = 0, 1
    nums.sort()
    
    while r < len(nums) and l < len(nums):
        if l == r or (nums[r] - nums[l]) < k:
            r += 1
        elif nums[r] - nums[l] > k:
            l += 1
        else:
            l += 1
            res += 1
            while l < len(nums) and nums[l] == nums[l - 1]:
                l += 1
    return res

Hashmap

Much eaiser than two pointers solution, time is O(n)

from collections import Counter
def findPairs(self, nums: List[int], k: int) -> int:
    counter = Counter(nums)
    res = 0
    for x in counter:
        if k == 0 and counter[x] > 1:
            res += 1
        elif k > 0 and x + k in counter:
            res += 1
    return res

N Sum Problem:

1. Two Sum

Unsort array, use hash map

def twoSum(self, nums: List[int], target: int) -> List[int]:
    dic = {}
    for i, n in enumerate(nums):
        if n in dic:
            return [dic[n], i]
        dic[target - n] = i

167. Two Sum II - Input array is sorted

Sorted array use 2 pointers

def twoSum(self, numbers: List[int], target: int) -> List[int]:
    lo, hi = 0, len(numbers) - 1
    while lo < hi:
        cur = numbers[lo] + numbers[hi]
        if cur == target:
            return (lo + 1, hi + 1)
        elif cur < target:
            lo += 1
        else:
            hi -= 1

15. 3Sum

Two Pointers

Remember to skip duplicate result.

def threeSum(self, nums: List[int]) -> List[List[int]]:
    def twoSum(nums, target, start):
        res = []
        lo, hi = start, len(nums) - 1
        while lo < hi:
            cur = nums[lo] + nums[hi]
            if cur < target:
                lo += 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
            elif cur > target:
                hi -= 1
                while lo < hi and nums[hi] == nums[hi + 1]:
                    hi -= 1
            else:
                res.append([nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
                while lo < hi and nums[hi] == nums[hi + 1]:
                    hi -= 1
        return res

    res = []
    nums.sort()
    i = 0
    while i < len(nums) - 2:
        two_sums = twoSum(nums, -nums[i], i + 1)
        for s in two_sums:
            res.append([nums[i]] + s)
        i += 1
        while i < len(nums) - 2 and nums[i] == nums[i - 1]:
            i += 1
    
    return res

Hashmap

def threeSum(self, nums: List[int]) -> List[List[int]]:
    def twoSum(nums, target, res):
        seen = set()
        i = 0
        while i < len(nums):
            x = target - nums[i]
            if x in seen:
                res.append([-target, nums[i], x])
                while i + 1 < len(nums) and nums[i] == nums[i + 1]:
                    i += 1
            seen.add(nums[i])
            i += 1

    res = []
    nums.sort()
    for i in range(len(nums)):

        # all following nums are greater than 0
        if nums[i] > 0:
            break

        if i == 0 or nums[i - 1] != nums[i]:
            twoSum(nums[i + 1:], -nums[i], res)
    return res

16. 3Sum Closest

Similar with 3Sum

def threeSumClosest(self, nums: List[int], target: int) -> int:
        
    def twoSum(nums, target, start):
        res = None
        diff = float('inf')
        lo, hi = start, len(nums) - 1
        
        while lo < hi:
            cur = nums[lo] + nums[hi]
            if cur == target:
                return cur

            cur_diff = abs(target - cur)
            if cur_diff < diff:
                res = cur
                diff = cur_diff

            if cur < target:
                lo += 1
            else:
                hi -= 1
        return res
    
    nums.sort()
    res = None
    diff = float('inf')
    for i in range(len(nums) - 2):
        cur_sum = nums[i] + twoSum(nums, target - nums[i], i + 1)
        cur_diff = abs(target - cur_sum)
        if cur_diff == 0:
            return cur_sum
        if cur_diff < diff:
            res = cur_sum
            diff = cur_diff
    return res

18. 4Sum

The same as 3 sum.

class Solution:
    
    def twoSum(self, nums, target, start):
        res = []
        lo, hi = start, len(nums) - 1
        while lo < hi:
            cur = nums[lo] + nums[hi]
            if cur < target:
                lo += 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
            elif cur > target:
                hi -= 1
                while lo < hi and nums[hi] == nums[hi + 1]:
                    hi -= 1
            else:
                res.append([nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
                while lo < hi and nums[hi] == nums[hi + 1]:
                    hi -= 1
        return res
    
    def threeSum(self, nums: List[int], target, start, ) -> List[List[int]]:
        res = []
        i = start
        while i < len(nums) - 2:
            two_sums = self.twoSum(nums, target - nums[i], i + 1)
            for s in two_sums:
                res.append([nums[i]] + s)
            i += 1
            while i < len(nums) - 2 and nums[i] == nums[i - 1]:
                i += 1
        return res
    
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = []
        i = 0
        while i < len(nums) - 3:
            triples = self.threeSum(nums, target - nums[i], i + 1)
            for t in triples:
                res.append([nums[i]] + t)
            i += 1
            while i < len(nums) - 3 and nums[i] == nums[i - 1]:
                i += 1
        return res

But, we can generlize it to a N Sum function

N Sum

The list nums should sort outside of the function, or else the list will resort in every recursion.

def nSum(self, nums, target, n, start=0):
        # nums.sort()  # assume the nums is sorted.
        res = []
        
        # 2 sum is base case.
        if n < 2 or len(nums) < n:
            return res
        
        if n == 2:
            lo, hi = start, len(nums) - 1
            while lo < hi:
                cur = nums[lo] + nums[hi]
                if cur < target:
                    lo += 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
                elif cur > target:
                    hi -= 1
                    while lo < hi and nums[hi] == nums[hi + 1]:
                        hi -= 1
                else:
                    res.append([nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
                    while lo < hi and nums[hi] == nums[hi + 1]:
                        hi -= 1
            return res

        i = start
        while i < len(nums) - (n - 1):
            nsum = self.nSum(nums, target - nums[i], n - 1, i + 1)
            for s in nsum:
                res.append([nums[i]] + s)
            i += 1
            while i < len(nums) - (n - 1) and nums[i] == nums[i - 1]:
                i += 1
        return res

So, for the four sum problem, just simplly call

def fourSum(self, nums, target):
    nums.sort()
    return self.nSum(nums, target, 4)