My website

```python class Solution: def kSmallestPairs(self, A: List[int], B: List[int], k: int) -> List[List[int]]: “"”tc O(KlgK) sc O(K) main idea: min PQ, (pair_sum,i_A,j_B) constrains: (1) for each array, we consider at most k elements (2) for each val in A, if its smallest pairt in B at pos j is pop... [Read More]

```python class Solution: def maxDepth(self, s: str) -> int: “"”tc O(N) sc O(1) ignore sign and digit, only count open paranthesis and get the max """ res = opens = 0 for c in s: if c == '(': opens += 1 res = max(res,opens) if c == ')': opens... [Read More]

```python class Solution: def minimumDeviation(self, A: List[int]) -> int: “"”tc O(KNlgKN) K:lg(max(A)) sc O(N) main idea: use max PQ. preprocess all odd number into even, keep halfing max even val until max number is odd meanwhile keep a min_v to “”” res = float(‘inf’) pq = [] # max PQ... [Read More]

```python class Solution: def kthSmallest(self, mat: List[List[int]], k: int) -> int: “”” tc (m-1)*klgk sc O(K) main idea: use k pairs with smalleset sum of two arrays to call m-1 times, there m = len(mat) """ def k_small_pairs(A,B,k): res = [] pq = [] #(sum, A[i],B[i]) j = 0 n... [Read More]

Three TreeSet/ SortedList solution: ```python from sortedcontainers import SortedList class MKAverage: “"”tc O(MlgM) M: size of q “”” def init(self, m: int, k: int): self.left,self.mid,self.right = SortedList([]),SortedList([]),SortedList([]) self.q = deque() self.m_sum = 0 self.m = m self.k = k def addElement(self, x: int) -> None: # alwayse insert into mid... [Read More]