My website

Presum + DP solution class Solution: def splitArray0(self, nums: List[int], m: int) -> int: """ tc O(M*N*N) sc O(M*N) dp[i][j] : min val for j elements to split into i subarray, among their bigest subarray sum dp[0][0] = 0 dp[1][j] = A[0] + A[1] + ... + A[j-1] dp[2][j] =... [Read More]

```python class Solution: def matrixReshape(self, nums: List[List[int]], r: int, c: int) -> List[List[int]]: “”” tc O(RC) sp O(C) main idea: 1. check total number of elements in arr if the same as rc 2. loop through by col , row of original arr and keep a temporary array to cache... [Read More]

hashtable solution class Solution: def longestLine(self, M: List[List[int]]) -> int: """ 1. edge case: if M is empty 2. create 4 dictionary caches for 4 direction 3. loop through matrix M each time there is val == 1, keep incrementing cnt until encounter a '0', reset values corresponding to each... [Read More]

```python class Solution: def reverseStr(self, s: str, k: int) -> str: “”” tc O(N) sc O(N) 1. list string 2. while loop cnt per k, reverse i: i+k, (within boundry) skip to i + 2k 3. join """ l = list(s) n = len(l) for i in range(0,n,2*k): z =... [Read More]

```python class Solution: def maxEnvelopes(self, envelopes: List[List[int]]) -> int: “”” tc O(NlgN) sc O(N) 1. sort by w asc and h by desc 2. LIS baesd on h “”” if not envelopes or len(envelopes)==1 : return len(envelopes) envelopes.sort(key = lambda x:(x[0],-x[1])) h = [x[1] for x in envelopes ] #store... [Read More]