```python class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: # time O(Nlg(N)) N = colsrows space O(1) “”” main idea: convert 2D to 1D ,and mirrow 1D value to 2D by // col and % col for row_pos and col_pos. “”” # edge case: if not matrix or...
[Read More]
791. Custom Sort String
```python
[Read More]
22. Generate Parentheses
```python class Solution: time O(2^2) space O(N) def generateParenthesis(self, n: int) -> List[str]: res = [] left = right = n s = '' def dfs(l,r,s,res): # early exit: if l > r: return # base case: if l == 0 and r == 0: res.append(s) if l : dfs(l-1,r,s+'(',res)...
[Read More]
791. Custom Sort String
class Solution:
def customSortString(self, S: str, T: str) -> str:
# time O(T+S) space O(T)
cnt = collections.Counter(T)
res = []
for c in S:
if c in cnt:
res.append(c*cnt.pop(c))
for c,v in cnt.items():
res.append(c*v)
return ''.join(res)
[Read More]
42. Trapping Rain Water
Brute Force solution: TLE class Solution: def trap(self, height: List[int]) -> int: # time O(N^2) space O(1) if not height:return 0 size = len(height) water =0 for i in range(1,size-1): l_max = r_max = 0 # each time check l,r max at pos i, need to reset # l_max for...
[Read More]