Homework 5

[JinJinQuant]

Difficulty	Data Structure	Problem	Links	Importance
Medium	Stack	Online Stock Span	Link	3
Easy	Queue	Moving Average from Data Stream	Link	1
Medium	Queue	Stock Price Fluctuation	Link	3
Medium	Heap	Meeting Rooms II	Link	1
Medium	Heap	Kth Largest Element in an Array	Link	1
Easy	Tree	Binary Tree Inorder Traversal	Link	2
Easy	Tree	Maximum Depth of Binary Tree	Link	2
Medium	Tree	Binary Tree Level Order Traversal	Link	2
Easy	Binary Search	Binary Search	Link	1
Medium	Binary Search	Find First and Last Position of Element in Sorted Array	Link	1
Medium	Binary Search	Longest Increasing Subsequence	Link	2
Medium	Binary Search	Peak Index in a Mountain Array	Link	2
Easy	Binary Search	Kth Missing Positive Number	Link	3

[JinJinQuant]

901. Online Stock Span

1. Stack Crawling with retrospective view --> Stack to avoid repetitions, use stack

class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        span = 1

        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]

        self.stack.append([price, span])
        return span

2. Brute-force iterative approach makes checking the same elements repeatedly

class StockSpanner:

    def __init__(self):
        self.lst = []

    def next(self, price: int) -> int:
        self.lst.append(price)

        cnt = 0
        i = len(self.lst) - 1
        while i >= 0:
            if self.lst[i] <= price:
                cnt += 1
            else:
                break
            i -= 1

        return cnt

[JinJinQuant]

346. Moving Average from Data Stream

1. Queue Given size, crawling an array --> Queue

from queue import Queue

class MovingAverage:

def __init__(self, size: int):
    self.q = Queue(maxsize = size)
    self.size = size
    self.sum = 0

def next(self, val: int) -> float:
    if self.q.qsize() == self.size:
        self.sum -= self.q.get()
    self.q.put(val)
    self.sum += val

    return self.sum / self.q.qsize()

2. Time complexity reduced (`O(1)`
```Python3
from collections import deque

class MovingAverage:
    def __init__(self, size: int):
        self.length = 0
        self.max = size
        self.sum = 0
        self.queue = deque()

    def next(self, val: int) -> float:
        if self.length < self.max:
            self.length +=1
            self.queue.append(val)
            self.sum += val
        else:
            self.sum -= self.queue.popleft()
            self.queue.append(val)
            self.sum += val
        return self.sum/self.length

[JinJinQuant]

2034. Stock Price Fluctuation

keep track of the lowest and highest value efficiently --> heap access and update historical prices effectively --> hashmap

Problem: updating old prices in a heap is very costly (O(nlogn)) Solution: just put all updated elements in the heap and then remove outdated ones when we call the function to find the max or min value

class StockPrice:
    def __init__(self):
        self.hmap = {} # hash map {ts:price}
        self.maxp = [] # max heap
        self.minp = [] # min heap
        self.latest = 0 # latest timestamp

    def update(self, timestamp: int, price: int) -> None:
        self.hmap[timestamp] = price # keep the hash map always to be updated
        self.latest = max(self.latest, timestamp) # to retrieve the current price
        heappush(self.maxp, (-price, timestamp))
        heappush(self.minp, (price, timestamp))

    def current(self) -> int:
        return self.hmap[self.latest]

    def maximum(self) -> int:
        price, timestamp = self.maxp[0]
        while -price != self.hmap[timestamp]:
            heappop(self.maxp) # remove an outdated price from the max heap
            price, timestamp = self.maxp[0]
        return -price

    def minimum(self) -> int:
        price, timestamp = self.minp[0]
        while price != self.hmap[timestamp]:
            heappop(self.minp)
            price, timestamp = self.minp[0]
        return price

# Your StockPrice object will be instantiated and called as such:
# obj = StockPrice()
# obj.update(timestamp,price)
# param_2 = obj.current()
# param_3 = obj.maximum()
# param_4 = obj.minimum()

[JinJinQuant]

253. Meeting Rooms II

this problem is very similar to allocating and processing taks by OS def of overlap: begin[now] < min(ends) --> need a new meeting room if the current time slot's begin > smallest end time in the minium heap <=> we don't have overlap <=> don't need a new room <=> can share the room with the smallest end time in the minimum heap

import heapq

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        pq = [] # initialize a priority queue (heap) for end time
        sort = sorted(intervals) # sort the list by first element
        for slot in sort:
            # need a new meeting room (current slot's begin < smallest end time)
            if pq == [] or pq[0] > slot[0]:
                heapq.heappush(pq, slot[1]) # heap push end time
            else:
                heapq.heappop(pq) # don't need a new meeting room, just updated the end time
                heapq.heappush(pq, slot[1])
        return len(pq)

[JinJinQuant]

215. Kth Largest Element in an Array

1. Heap O(n log(n)) find kth largest value --> use heap

   import heapq
   class Solution:
   def findKthLargest(self, nums: List[int], k: int) -> int:
       h = []
       for num in nums:
           heapq.heappush(h, -num)
       for i in range(k-1):
           heapq.heappop(h)
       return -h[0]

2. Hoare's selection algorithm (Quickselect Algorithm) O(n) it is unnecessary to memorize this algorithm, just notice this

class Solution:
    def findKthLargest(self, nums, k):
        def quick_select(nums, k):
            pivot = random.choice(nums)
            left, mid, right = [], [], []

            for num in nums:
                if num > pivot:
                    left.append(num)
                elif num < pivot:
                    right.append(num)
                else:
                    mid.append(num)

            if k <= len(left):
                return quick_select(left, k)

            if len(left) + len(mid) < k:
                return quick_select(right, k - len(left) - len(mid))

            return pivot

        return quick_select(nums, k)

[JinJinQuant]

94. Binary Tree Inorder Traversal

1. Recrusion Pre-order Traversal (DFS): Root -> Left -> Right In-order Traversal (DFS): Left -> Root -> Right Post-order Traversal (DFS): Left -> Right -> Root Level-order Traversal (BFS): Level by level from left to right

   
   # Definition for a binary tree node.
   # class TreeNode:
   #     def __init__(self, val=0, left=None, right=None):
   #         self.val = val
   #         self.left = left
   #         self.right = right
   class Solution:
   def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
       ans = []
       self.recursion(root, ans)
       return ans
   
   def recursion(self, root, ans):
       if root is None:
           return None
       else:
           self.recursion(root.left, ans)
           ans.append(root.val)
           self.recursion(root.right, ans)

pre-order: append / call left / call right

in-order: call left / append / call right

post-order: call left / call right / call append

2. Use a stack
```Python3
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        stack = []
        curr = root
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            ans.append(curr.val)
            curr = curr.right
        return ans

[JinJinQuant]

104. Maximum Depth of Binary Tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        else:
            left_height = self.maxDepth(root.left)
            right_height = self.maxDepth(root.right)
            return max(left_height, right_height) + 1

[JinJinQuant]

102. Binary Tree Level Order Traversal

BFS (Breadth First Search) can be used to blind search, like finding a path in a maze. This method is likely to be used to guarantee the shortest length between nodes. It needs a queue to search for the closest nodes first.

1. Queue

   
   # Definition for a binary tree node.
   # class TreeNode:
   #     def __init__(self, val=0, left=None, right=None):
   #         self.val = val
   #         self.left = left
   #         self.right = right

from collections import deque class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:

Initialize an empty list to store the result

    result = []

    # Initialize a deque to perform BFS
    q = deque()
    q.append(root)

    # Perform BFS until the queue is empty
    while q:
        # Get the number of nodes at the current level
        n = len(q)
        level = []

        # Process each node at the current level
        for i in range(n):
            node = q.popleft()

            # If the node is not None, add its value to the current level list
            if node:
                level.append(node.val)

                # Enqueue its left and right children if they exist
                q.append(node.left)
                q.append(node.right)

        # If the level list is not empty, add it to the result list
        if level:
            result.append(level)    

    # Return the final result
    return result

[JinJinQuant]

704. Binary Search

1. Binary Search Sorted array, Find a value --> binary search, take care of the finishing condition

   
   class Solution:
   def search(self, nums: List[int], target: int) -> int:
       left = 0
       right = len(nums) - 1
   
       # left > right means that an index searched is out of range
       # This means that no value matches the value we're looking for
       while left <= right:
           mid = (left + right) // 2
   
           if nums[mid] == target:
               return mid
   
           if nums[mid] < target:
               left = mid + 1
           else:
               right = mid - 1
   
       # If we finish the search without finding target
       return -1

[JinJinQuant]

34. Find First and Last Position of Element in Sorted Array

1. Brute-force (find the target and then find the range by broadening it around the target)

   class Solution:
   def searchRange(self, nums: List[int], target: int) -> List[int]:
       ref = self.binarySearch(nums, target)
       if ref == -1:
           return [-1,-1]
   
       i_left = ref
       while nums[i_left] == target:
           i_left -= 1
           if i_left < 0:
               break
   
       i_right = ref
       while nums[i_right] == target:
           i_right += 1
           if i_right > len(nums) - 1:
               break
   
       return [i_left+1, i_right-1]
   
   def binarySearch(self, nums, target):
       left = 0
       right = len(nums) - 1
   
       while left <= right:
           mid = (left + right) // 2
   
           if nums[mid] == target:
               return mid
   
           if nums[mid] < target:
               left = mid + 1
           else:
               right = mid - 1
   
       return -1

2. More elaborated version

   
   class Solution:
   def searchRange(self, nums: List[int], target: int) -> List[int]:
       left = self.binarySearch(nums, target, True)
       right = self.binarySearch(nums, target, False)
       return [left, right]
   
   def binarySearch(self, nums, target, is_searching_left):
       left = 0
       right = len(nums) - 1
       idx = -1
   
       while left <= right:
           mid = (left + right) // 2
   
           if nums[mid] == target:
               idx = mid
               if is_searching_left:
                   right = mid - 1
               else:
                   left = mid + 1
           elif nums[mid] < target:
               left = mid + 1
           else:
               right = mid - 1
   
       return idx

[JinJinQuant]

A Framework to Solve Dynamic Programming Problems

Typically, dynamic programming problems can be solved with three main components. If you're new to dynamic programming, this might be hard to understand but is extremely valuable to learn since most dynamic programming problems can be solved this way.

1. Function or Array to Represent the Answer

First, we need some function or array that represents the answer to the problem from a given state. For many solutions on LeetCode, you will see this function/array named "dp". For this problem, let's say that we have an array dp. This array needs to represent the answer to the problem for a given state, so let's say that dp[i] represents the length of the longest increasing subsequence that ends with the ith element. The "state" is one-dimensional since it can be represented with only one variable - the index i.

2. Transition Between States

Second, we need a way to transition between states, such as dp[5] and dp[7]. This is called a recurrence relation and can sometimes be tricky to figure out. Let's say we know dp[0], dp[1], and dp[2]. How can we find dp[3] given this information? Well, since dp[2] represents the length of the longest increasing subsequence that ends with nums[2], if nums[3] > nums[2], then we can simply take the subsequence ending at i = 2 and append nums[3] to it, increasing the length by 1. The same can be said for nums[0] and nums[1] if nums[3] is larger. Of course, we should try to maximize dp[3], so we need to check all 3. Formally, the recurrence relation is:

dp[i]=max(dp[j]+1) for all j where nums[j]<nums[i] and j<i

3. Base Case

The third component is the simplest: we need a base case. For this problem, we can initialize every element of dp to 1, since every element on its own is technically an increasing subsequence.

[JinJinQuant]

300. Longest Increasing Subsequence

1. DP asking for max / min & the word "subsequence"

   class Solution:
   def lengthOfLIS(self, nums: List[int]) -> int:
       dp = [1] * len(nums)
       for i in range(1, len(nums)):
           for j in range(i):
               if nums[i] > nums[j]:
                   dp[i] = max(dp[i], dp[j] + 1)
   
       return max(dp)

   How do I find the length of the longest strictly increasing continuing subsequence?

2. Binary Search

   class Solution:
   def lengthOfLIS(self, nums: List[int]) -> int:
       sub = []
       for num in nums:
           i = bisect_left(sub, num)
   
           # If num is greater than any element in sub
           if i == len(sub):
               sub.append(num)
   
           # Otherwise, replace the first element in sub greater than or equal to num
           else:
               sub[i] = num
   
       return len(sub)

[JinJinQuant]

1. Wrong answer (has 'O(n)` time complexity

   class Solution:
   def peakIndexInMountainArray(self, arr: List[int]) -> int:
       for i in range(1, len(arr)-1):
           if arr[i-1] < arr[i] and arr[i] > arr[i+1]:
               return i

2. Binary Search search a half -> search again in a leftover

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        left = 0
        right = len(arr) - 1

        while left < right:
            mid = (left + right) // 2

            # if mid is in uphill, we only see the right-side to find the peak
            if arr[mid] < arr[mid+1]:
                left = mid + 1
            # if mid is in downhill, 
            else:
                right = mid

        # left > right means that the left is a peak
        return left