Homework 6

[JinJinQuant]

Difficulty	Topic	Problem Name	Importance
Medium	Sorting	Sort an Array	1
Easy	Sorting	Maximum Product of Three Numbers	2
Easy	Sorting	Sort Array by Increasing Frequency	3
Medium	Recursion	Pow(x, n)	2
Easy	Sliding Window	Maximum Average Subarray I	1
Hard	Sliding Window	Sliding Window Maximum	3
Hard	Sliding Window	Sliding Window Median	3
Medium	Sliding Window	Subarray Product Less Than K	3
Easy	Sliding Window	Minimum Difference Between Highest and Lowest of K Scores	3
Easy	Hash Table	Two Sum	1
Hard	Hash Table	First Missing Positive	2
Medium	Hash Table	Longest Consecutive Sequence	2
Easy	Hash Table	Intersection of Two Arrays	2

[JinJinQuant]

912. Sort an Array

1. Quick, Merge, Heap Sort

class Solution: def sortArray(self, nums: List[int]) -> List[int]: self.mergeSort(nums, 0, len(nums) - 1) return nums

# def quickSort(self, arr, left, right):
#     if left < right:
#         pivot = self.partition(arr, left, right)
#         self.quickSort(arr, left, pivot - 1)
#         self.quickSort(arr, pivot + 1, right)

# def partition(self, arr, left, right):
#     pivot = arr[right]
#     i = left - 1

#     for j in range(left, right):
#         if arr[j] <= pivot:
#             i += 1
#             arr[i], arr[j] = arr[j], arr[i]

#     arr[i+1], arr[right] = arr[right], arr[i+1]
#     return i+1

def mergeSort(self, arr: List[int], left: int, right: int):
    if left < right:
        mid = (left + right) // 2
        self.mergeSort(arr, left, mid)
        self.mergeSort(arr, mid + 1, right)
        self.merge(arr, left, mid, right)

def merge(self, arr: List[int], left: int, mid: int, right: int):
    temp_left = arr[left:mid + 1]
    temp_right = arr[mid + 1:right + 1]
    i = left
    il = 0
    ir = 0

    while il < len(temp_left) and ir < len(temp_right):
        if temp_left[il] <= temp_right[ir]:
            arr[i] = temp_left[il]
            il += 1
        else:
            arr[i] = temp_right[ir]
            ir += 1
        i += 1

    while il < len(temp_left):
        arr[i] = temp_left[il]
        il += 1
        i += 1

    while ir < len(temp_right):
        arr[i] = temp_right[ir]
        ir += 1
        i += 1

def heapSort(self, arr: List[int]) -> List[int]:
    def heapify(arr, size, i):
        largest = i # Initialize largest as root
        left = 2 * i + 1 # left = 2*i + 1
        right = 2 * i + 2 # right = 2*i + 2

        # See if left child of root exists and is greater than root
        if left < size and arr[i] < arr[left]:
            largest = left

        # See if right child of root exists and is greater than root
        if right < size and arr[largest] < arr[right]:
            largest = right

        # Change root, if needed
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i] # swap
            # Heapify the root.
            heapify(arr, size, largest)

    size = len(arr)

    # Build a maxheap.
    for i in range(size // 2 - 1, -1, -1):
        heapify(arr, size, i)

    # One by one extract elements
    for i in range(size-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i] # swap
        heapify(arr, i, 0)

    return arr

[JinJinQuant]

628. Maximum Product of Three Numbers

1. sort and figure out

   
   class Solution:
   def maximumProduct(self, nums: List[int]) -> int:
       nums.sort() # quick + merge
       lst_asc = nums
       lst_dsc = nums[::-1]
   
       num1 = lst_dsc[0] * lst_dsc[1] * lst_dsc[2]
       num2 = lst_asc[0] * lst_asc[1] * lst_dsc[0]
   
       return max(num1, num2)

[JinJinQuant]

1636. Sort Array by Increasing Frequency

1. collection.Counter() --> dict{ elem : freq}

   
   from collections import Counter
   class Solution:
   def frequencySort(self, nums: List[int]) -> List[int]:
       freq = Counter(nums)
       lst = [(freq[v], v) for v in freq]
       lst.sort(key = lambda x: (x[0], -x[1]))
       result = []
       for i in lst:
           result.extend(i[0]*[i[1]])
       return result

[JinJinQuant]

50. Pow(x, n)

1. Recursive

   
   class Solution:
   def myPow(self, x: float, n: int) -> float:
       if n == 0: return 1
       if x == 0: return 0
   
       if n < 0:
           x = 1/x
           n = abs(n)
   
       return self.pastPow(x, n)
   
   def pastPow(self, x, n):
       if n == 0:
           return 1
       half = self.pastPow(x, n//2)
       if n % 2 == 0: 
           return half * half
       else:
           return half * half * x