My website

DP with age limit class Solution: def bestTeamScore(self, scores: List[int], ages: List[int]) -> int: """tc O(N^2) sc O(N) main idea: LIS dp[i]: max total scores by sorted ages[i] 1. sort age,score pair by age 2. at any age[i], find age[j] where score[j] <= score[i] and j < i 3. update... [Read More]

class Solution: def shortestSubarray(self, A: List[int], k: int) -> int: """ tc O(N) sc O(N) main idea: mono queue (increasing) 1. initialize queue with [0,-1] 2. if psum - queue[0] >= k, update result 3. before insert current psum with index in the queue, remove elements from the tail that... [Read More]

class Solution: def maxSubArrayLen(self, A: List[int], k: int) -> int: """ tc O(N) sc O(N) main idea: use a cache to record a kv pair where key is psum and value is first occurance index + Two sum """ d = {0: -1} maxLen = psum = 0 for idx,... [Read More]

class Solution: def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int: """ tc O(R*C*C) sc O(R) main idea: refer to 363. Max Sum of Rectangle No Larger Than K """ r,c = len(matrix), len(matrix[0]) res = 0 for col_left in range(c): arr = [0] * r for col_right in range(col_left,c): for... [Read More]

class Solution: def subarraySum(self, A: List[int], k: int) -> int: """tc O(N) sc O(N) main idea: two sum + prefix sum (psum[i] - psum[j-1] = k => psum[i] - k = psum[j-1], where j < i => count occurance of psum by far and check number of time that psum[i]... [Read More]