[LeetCode] 1711. Count Good Meals

 Problem : https://leetcode.com/problems/count-good-meals/

This problem is like an enhanced 2sum problem. The only difference is, the 'target' number is not explicitly given.

class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        M = 10 ** 9 + 7
        result = 0
        seen = defaultdict(int)
        
        # sort the numbers first
        # for one given number there is no larger number before it.
        deliciousness.sort()
        
        for n in deliciousness:
            # the maximum sum of 'n' is n + n
            # try every power of two less than n + n
            target = 1
            while target <= n + n:
                result += seen[target - n]
                result %= M
                target *= 2
            
            # increase the counter of n
            seen[n] += 1
        
        return result

[LeetCode] 170. Two Sum III - Data structure design

 Problem : https://leetcode.com/problems/two-sum-iii-data-structure-design/

M = Value - N.   Use hash table to find whether M exists when given Value and N.

class TwoSum:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.seen = {}
        self.memo = set()
        
    def add(self, number: int) -> None:
        """
        Add the number to an internal data structure..
        """
        
        if number in self.seen:
            self.seen[number] += 1
        else:
            self.seen[number] = 1
        
    def find(self, value: int) -> bool:
        """
        Find if there exists any pair of numbers which sum is equal to the value.
        """
        
        if value in self.memo: return True

        for n in self.seen.keys():
            if value - n == n:
                if self.seen.get(n, 0) >= 2: 
                    self.memo.add(value)
                    return True
            elif self.seen.get(value - n, 0) > 0: 
                self.memo.add(value)
                return True
        
        return False

[LeetCode] 18. 4Sum

Problem : https://leetcode.com/problems/4sum/

Similar to 3Sum.

Time Complexity : O ( len(nums) *len(nums) * len(nums)/2 )

Space Complexity: O (len(nums)*len(nums)*len(nums)*len(nums))

 
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        nums.sort()
        L = len(nums)
        
        result = []
        
        for i in range(L-3):
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            for j in range(i+1, L-2):
                if j > i + 1 and nums[j] == nums[j-1]:
                    continue
                    
                left, right = j + 1, L - 1
                
                while left < right:
                    # early termination
                    if nums[i] + nums[j] + nums[left] + nums[left] > target:
                        break
                        
                    tmp = nums[i] + nums[j] + nums[left] + nums[right]
                    
                    if tmp < target:
                        k = left + 1
                        while k < right and nums[k] == nums[left]:
                            k += 1
                            continue
                            
                        left = k
                    elif tmp > target:
                         l = right - 1
                         while l > left and nums[l] == nums[right]:
                            l -= 1
                            continue
                        
                         right = l
                    else:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        
                        k = left + 1
                        while k < right and nums[k] == nums[left]:
                            k += 1
                            continue
                            
                        left = k
                        
                        l = right - 1
                        while l > left and nums[l] == nums[right]:
                            l -= 1
                            continue
                        
                        right = l
                        
        return result

[LeetCode] 16. 3Sum Closest

Problem : https://leetcode.com/problems/3sum-closest/

Use the same two pointers approach as the 3Sum quiz.

Time Complexity :  O ( N * LogN + N ** 2 )

Space Complexity: O ( log N ) or O ( N ), depending on the sort algorithm. 

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        
        nums.sort()
        N = len(nums)
        
        result = nums[0] + nums[1] + nums[2] # assume the init value of result
        
        for i in range(N-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            left, right = i + 1, N-1
                        
            while left < right:
                tmp = sum([nums[i], nums[left], nums[right]])
                
                if abs(result - target) > abs(tmp - target):
                    result = tmp
                
                if tmp == target:
                    return target
                
                if tmp < target:
                    j = left + 1
                    while j < right and nums[j] == nums[left]:
                        j += 1
                    left = j
                else:
                    k = right - 1
                    while k > left and nums[k] == nums[right]:
                        k -= 1
                    right = k
                    
        return result

Edited of 07/27/2021. Update result variable's init value.

[LeetCode] 15. 3Sum

Problem : https://leetcode.com/problems/3sum/

Sort the input number array first. Then iterate the number array to pick up the number 'a'.  After that use 2 pointers algorithm to locate the number 'b' and 'c' which meet the equation  b + c = 0 - a

Time Complexity :   O ( len(nums) * len(nums) /  2) 

Space Complexity:   O ( len(nums) ) 

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        # sort input numbers
        nums.sort()
        
        L = len(nums)
        result = []
        
        for i in range(L - 2):
            # skip duplicate number 'a'
            if i > 0 and nums[i] == nums[i-1]:
                continue
            
            target = 0 - nums[i]
            
            left, right = i + 1, L - 1
            
            while left < right:
                if nums[left] + nums[right] == target:
                    result.append([nums[i], nums[left], nums[right]])
                    
                    # skip duplicate number 'b'
                    j = left + 1
                    while j < right and nums[j] == nums[left]:
                        j += 1
                    
                    left = j
                    
                    # skip duplicate number 'c'
                    k = right - 1
                    while  k > left and nums[k] == nums[right]:
                        k -= 1
                        
                    right = k
                    
                    # continue to search next combination
                    continue
                    
                if nums[left] + nums[right] < target:
                    left += 1
                else:
                    right -= 1
        
        return result

[LeetCode] 1. Two Sum

Problem : https://leetcode.com/problems/two-sum/

With the formula "A + B = Target" in mind,  the problem basically equals to by given number A search number B in the array.

Solution1, Binarch search based solution

Time Complexity = O(N + N*LogN + N * LogN) = O (N * LogN)
Space Complexity = O(N), for the space used by the sorted array.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sortedNums = sorted([(n, i) for i, n in enumerate(nums)])
    
        def bsearch(left, right, target):
            while left < right:
                mid = left + (right - left) // 2
                
                if sortedNums[mid][0] == target:
                    return sortedNums[mid][1]
                
                elif sortedNums[mid][0] < target:
                    left = mid + 1
                else:
                    right = mid
            
            return -1
        
        for si, (n, i) in enumerate(sortedNums):
            j = bsearch(si+1, len(sortedNums), target - n)
            if j != -1:
                return [i, j]

Solution 2, Two-pointers based solutin:

Time Complexity = O(N + N * Log N + LogN) = O ( N * Log N )
Space Complexity = O(N), for the space used by the sorted array.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sortedNums = sorted([(n, i) for i, n in enumerate(nums)])
    
        left, right = 0, len(sortedNums) - 1
        
        while left < right:
            sums = sortedNums[left][0] + sortedNums[right][0]
            
            if sums == target:
                return sortedNums[left][1], sortedNums[right][1]
            
            if sums < target:
                left += 1
            else:
                right -= 1

Solution 3, use hash table to save all encountered number and its index. Return the corresponding indices when 'target - n' is found in the hash table.

Time Complexity = O(N)
Space Complexity = O(N), for space used by hash map.

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