My website

optimization class Solution: def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool: """ tc O(len(pieces) + len(arr) ) sc O(len(pieces)) main idea: since both arr and pieces are distinct, we can use first element in one pieces[i] as key and check if we can comcate pieces[i] into arr[j:len(p[i])] """ d =... [Read More]

class Solution: def findLengthOfLCIS(self, A: List[int]) -> int: """ main idea: use pre to keep track last number as continuous strcictly increasing subsequence(actually subarray) tc O(N) sc O(1) [1,0,0,8,6] => 2 [1,3,5,4,2,3,4,5] => 4 """ max_cnt = cnt = 1 pre = A[0] n = len(A) for i in range(1,... [Read More]

class Solution: def findNumberOfLIS(self, A: List[int]) -> int: """ tc O(N^2) sc O(N) main idea: DP 1. create two dp array cnt[i] : number of subsequence ending with i ; LIS[i]: max length of strictly increasing subsequence ending with i 2. loop through the whole array, and within the inner... [Read More]

class Solution: def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int: """ tc O(C*C*R*lgR) => O(max(R,C)^2 * min(R,C) * lg(min(R,C))) sc O(R) *** here assume rows >> cols 1. create an array to save prefix sum for each row 2. for psum[0] ... psum[right-1], find an idx s.t. psum[idx] >= psum[right]... [Read More]

class Solution: def getFood(self, grid: List[List[str]]) -> int: """ tc O(R*C) sc O(R*C) main idea: BFS 1. find start point, put its position into queue 2. expand from four directions (1) check if neighbour position is valid O, push onto queue (2) if neighour is target location, return final res... [Read More]