### 1. 366. Find Leaves of Binary Tree

• Binary Tree / DFS
• Medium
• O(N)

Categorize nodes by height. Post-order traversal as node’s height = max(children’s height) + 1. If deletion is wanted, go through level by level, set children to None and delete object?

class Solution:
def findLeaves(self, root: TreeNode) -> List[List[int]]:
heights = dict()
levels = defaultdict(list)
stack = [(root, 0)]
while stack:
node, backtrack = stack.pop()
if node is None: continue
if backtrack:
heights[node] = max(heights.get(node.left, -1), heights.get(node.right, -1)) + 1
levels[heights[node]].append(node.val)
else:
stack.extend([(node, 1), (node.left, 0), (node.right, 0)])
return levels.values()


### 2. 1293. Shortest Path in a Grid with Obstacles Elimination

• BFS Search
• Hard
• O(NK) -> O(NK*KlogK) (but empirically faster)

BFS brute force -> Improve with Priority Queue where priority is (distance + steps used). A*? Hash (r, c, k) to avoid duplicate.

A*: f(n) = g(n) + h(n) where n is the next node on the path, g(n) is the cost of the path from the start node to n, and h(n) is a heuristic function that estimates the cost of the cheapest path from n to the goal.

Since we are exploring the problem space with notion of order, if we find the state already visited, the previous visit is guaranteed to be cheaper / better etc.

class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
state = m-1, n-1, k
queue = [(m+n-2, 0, state)]
seen = {state}
while queue:
_, steps, (i, j, k) = heapq.heappop(queue)
if k >= i + j - 1:
return steps + i + j
for i, j in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
if m > i >= 0 <= j < n:
state = i, j, k - grid[i][j]
if state not in seen and state[2] >= 0:
heapq.heappush(queue, (i+j+steps+1, steps+1, state))
return -1


### 3. 1146. Snapshot Array

• Design / Binary Search
• Medium
• O(1) set O(logN) get

For each index keep a stack of (snap_id, val). For get, use binary search.

class SnapshotArray:
def __init__(self, length: int):
self.snap_id = -1
self.data = [[[-1, 0]] for _ in range(length)]

def set(self, index: int, val: int) -> None:
if self.data[index][-1][0] == self.snap_id:
self.data[index][-1][1] = val
else:
self.data[index].append([self.snap_id, val])

def snap(self) -> int:
self.snap_id += 1
return self.snap_id

def get(self, index: int, snap_id: int) -> int:
loc = bisect_left(self.data[index], [snap_id, ]) - 1  # why
return self.data[index][loc][1]


### 4. 1937. Maximum Number of Points with Cost

• DP
• Medium
• O(N^3) brute force; O(N^2) if smart

f(i,j) is maximum score of (i, j), f(i+1, j) = max(f(i,j) + abs(k - j) for j ) + points(i+1,j). Instead of brute foce max of, which make inner loop quadratic, do relaxation with kadane from both directions.

class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
nrow, ncol = len(points), len(points[0])

dp = points.copy()
for r, row in enumerate(points[1:], 1):
max_score = 0
for c, cell in enumerate(row):
max_score = max(max_score - 1, dp[r-1][c])
dp[r][c] = max_score

max_score = 0
for c, cell in reversed(list(enumerate(row))):
max_score = max(max_score - 1, dp[r-1][c])
dp[r][c] = max(dp[r][c], max_score + cell)

return max(dp[-1])


### 5. 2007. Find Original Array From Doubled Array

• Math / Sort
• Medium
• O(N)

From smallest to largest, 2x has two sources, original or doubled. How do we know how many are doubled? Count(X), when Count(x//2) = 0, or we work on this from smallest x to largest. Ordering! Special care to case when x = 0.

class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
freq_counts = Counter(changed)
if freq_counts[0] % 2: return []
for x in sorted(freq_counts):
if x == 0:
freq_counts[x] //= 2
continue
if freq_counts[x] > freq_counts[2 * x]:
return []
freq_counts[2 * x] -= freq_counts[x]
return list(freq_counts.elements())


### 6. 2096. Step-By-Step Directions From a Binary Tree Node to Another

• Tree / LCA / Postorder
• Medium
• O(N)

Traverse the tree postorder to find LCA and two nodes, build parent pointers. Form paths, from startNode up to LCA and from LCA down to distNode. Can do one pass with postorder traversal.

def find_lca(root, startValue, destValue):
# post order traversal to find both nodes as well as lca
# populating parent pointers along the way
parents = dict()
parents[root] = None
stack = [(root, 0)] # backtrack or not
found = defaultdict(int) # node to 0/1 indicator whether on of the target node is found
found[None] = 0
lca, start_node, dest_node = None, None, None

while stack and lca is None:
node, backtrack = stack.pop()
if backtrack:
if node.val == startValue:
start_node = node
found[node] = 1
if node.val == destValue:
dest_node = node
found[node] = 1
if found[node.left] and found[node.right]:
lca = node
if (found[node.left] or found[node.right]) and node.val in [startValue, destValue]:
lca = node

found[node] += found[node.left] + found[node.right]
else:
stack.append((node, 1))
for child in node.left, node.right:
parents[child] = node
if child is None: continue
stack.append((child, 0))

return lca, start_node, dest_node, parents

def build_path(parents, lca, start_node, dest_node):
# build the path from two sides and stitch them together
path = []
node = start_node
while node != lca:
path.append("U")
node = parents[node]

tmp = []
node = dest_node
while node != lca:
if parents[node].left == node:
tmp.append("L")
else:
tmp.append("R")
node = parents[node]

path.extend(reversed(tmp))
return "".join(path)

class Solution:
def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
lca, start_node, dest_node, parents = find_lca(root, startValue, destValue)
return build_path(parents, lca, start_node, dest_node)

def lca(node):
"""Return lowest common ancestor of start and dest nodes."""
if not node or node.val in (startValue , destValue): return node
left, right = lca(node.left), lca(node.right)
return node if left and right else left or right

root = lca(root) # only this sub-tree matters

ps = pd = ""
stack = [(root, "")]
while stack:
node, path = stack.pop()
if node.val == startValue: ps = path
if node.val == destValue: pd = path
if node.left: stack.append((node.left, path + "L"))
if node.right: stack.append((node.right, path + "R"))
return "U"*len(ps) + pd


### 7. 833. Find And Replace in String

• Sweep line / Two Pointers
• Medium
• O(N + KlogK)

Sweep line process replacements from left to right. If we replace, we advance to beyond the substring we just matched.

class Solution:
def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
results = []
l = 0
for r, source, target in sorted(zip(indices, sources, targets)):
if r > l:
results.append(s[l:r])
l = r
if s[r:r+len(source)] == source:
results.append(target)
l = r + len(source)
if l < len(s): results.append(s[l:])
return "".join(results)


### 8. 68. Text Justification

• Greedy / DP
• Hard
• O(N) or O(N^2)

Depends on how we define desired white space placement. If MS word Greedy. If LaTeX then DP. f(i) = min(f(k) + badness(i, k))

class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
justified_text = []

def formatline(line_words):
if len(line_words) == 1:
# return line_words[0] + " " * (maxWidth - len(line_words[0]))
return line_words[0].ljust(maxWidth)

num_words = len(line_words)
num_spaces = maxWidth - sum(map(len, line_words))
space_size, extra = divmod(num_spaces, num_words - 1)

line = []
for i, word in enumerate(line_words):
line.append(word)
if i != len(line_words) - 1:
line.append(" " * space_size)
if extra:
line.append(" ")
extra -= 1
return "".join(line)

def formatline_last(line_words):
line = " ".join(line_words)
return line.ljust(maxWidth)

line = []
length = 0
for r, word in enumerate(words):
if length + len(word) + len(line) > maxWidth:
justified_text.append(formatline(line))
line = []
length = 0
length += len(word)
line.append(word)

justified_text.append(formatline_last(line))
return justified_text


### 9. 2128. Remove All Ones With Row and Column Flips

• Math
• Medium
• O(MN)
Consider 4 cells (r1, c1), (r1, c2), (r2, c1), (r2, c2)

If the matrix is obtained by flipping rows and columns from an initially all 0 matrix.

cell value at (r1, c1) is (# row 1 flip + # column 1 flip) % 2
cell value at (r1, c2) is (# row 1 flip + # column 2 flip) % 2
cell value at (r2, c1) is (# row 2 flip + # column 1 flip) % 2
cell value at (r2, c2) is (# row 2 flip + # column 2 flip) % 2

We do additional column flip to make (r1, c1) and (r1, c2) to be 0 it they are not already, and do additional row flip to make (r2, c1) to be 0 if needed.

Then

(# row 1 flip + # column 1 flip) = 2i
(# row 1 flip + # column 2 flip) = 2j
(# row 2 flip + # column 1 flip) = 2k
If we now look at the value at (r2, c2), it is (# row 2 flip + # column 2 flip) = 2j + 2k - 2i = 2m thus it has to be 0.

Thus if we flip a entire row to be 0 using column flip and then an entire column to 0 using row flip, the matrix has to be all 0.

class Solution:
def removeOnes(self, grid: List[List[int]]) -> bool:
nrow, ncol = len(grid), len(grid[0])

def flip_col(c): for r in range(nrow): grid[r][c] ^= 1

def flip_row(r): for c in range(ncol): grid[r][c] ^= 1

for c in range(ncol): if grid[0][c] == 1: flip_col(c)

for r in range(1, nrow): if grid[r][0] == 1: flip_row(r)

for r, c in product(range(1, nrow), range(1, ncol)):
if grid[r][c] == 1: return False
return True


### 10. 2034. Stock Price Fluctuation

• Sorted Containers / DLL with HashMap
• Medium
• O(logK) for update, O(1) for current, maximum, minimum. SortedContainers index 0 or -1 has constant access

time -> price for current price lookup: sorted by key - time; price -> timestamps for min max price lookup: sorted by key - price

class StockPrice:
def __init__(self):
self.time_to_prices = SortedDict()    # time -> price lookup  sorted by key - time
self.prices = SortedList()            # sorted list of prices

def update(self, timestamp: int, price: int) -> None:
if timestamp in self.time_to_prices:                  # O(1) look up
prev_price = self.time_to_prices[timestamp]
self.prices.remove(prev_price)                    # O(logN) removal

self.time_to_prices[timestamp] = price

def current(self) -> int:  # O(1)
return self.time_to_prices.peekitem(-1)[1]

def maximum(self) -> int:  # O(1)
return self.prices[-1]

def minimum(self) -> int:  # O(1)
return self.prices[0]


### 11. 843. Guess the Word

• Random / Math
• Hard
• Does not apply

If our guess has 2 right, then the true answer must also has at least 2 match with our guess. Random guess -> match guess with secret -> filter words have a different match with guess -> try again.

Can we have a better strategy? Instead of random guess, maybe try a guess that can potentially allow us to reduce the candidate set size most dramatically.

def match(word1, word2):
count = 0
for c1, c2 in zip(word1, word2):
count += c1 == c2
return count

class Solution:
def findSecretWord(self, wordlist: List[str], master: 'Master') -> None:
matches = 0
while matches !=6:
guess = wordlist[random.randint(0, len(wordlist)-1)]
matches = master.guess(guess)
wordlist = [w for w in wordlist  if matches == match(w, guess)]

def findSecretWord(self, wordlist: List[str], master: 'Master') -> None:
matches = 0
while matches != 6:
count = [Counter(w[i] for w in wordlist) for i in range(6)]
guess = max(wordlist, key=lambda w: sum(count[i][c] for i, c in enumerate(w)))
matches = master.guess(guess)
wordlist = [w for w in wordlist if matches == match(w, guess)]


### 12. 2013. Detect Squares

• Hash Map / Math
• Medium
• O(N^2)

Hash point to counts. Given p1, iterate over p3, let p1, p3 form the diag, check counts for p2, p4. Do math.

class DetectSquares:
def __init__(self):
self.X = defaultdict(dict)
self.Y = defaultdict(dict)

def add(self, point: List[int]) -> None:
x,y = point
X,Y = self.X, self.Y
X[x][y] = X[x].get(y, 0)+1
Y[y][x] = Y[y].get(x, 0)+1

def count(self, point: List[int]) -> int:
x,y = point
X,Y = self.X, self.Y
ans = 0
for q in X[x]:
d = q-y
ans += Y[y].get(x-d, 0)*Y[q].get(x-d, 0)*X[x][q]*(q != y)
ans += Y[y].get(x+d, 0)*Y[q].get(x+d, 0)*X[x][q]*(q != y)
return ans


### 13. 1610. Maximum Number of Visible Points

• Geometry / Sliding Window
• Hard
• O(NlogN)

Sort by degree angle. Stand on the point and rotate the view counterclockwise. To hangle wrap, copy points and add 360 and append to tail.

class Solution:
def visiblePoints(self, points: list[tuple[int, int]], angle: int, location: list[int, int]) -> int:
px, py = location
degrees = []
for x, y in points:
if [x, y] == location: continue
degrees.append(math.degrees(math.atan2(y-py, x-px)))
degrees.sort()

max_points = baseline = len(points) - len(degrees)
degrees += [d + 360 for d in degrees]
l = 0
for r in range(len(degrees)):
while degrees[r] - degrees[l] > angle: l += 1
max_points = max(max_points, baseline + r - l + 1)
if degrees[l] > 360: break
return max_points


### 14. 150. Evaluate Reverse Polish Notation

• Stack
• Medium
• O(N)

Put number on stack, when encounter operator, pop two numbers out and carry out operation, put result back on stack.

class Solution:
def evalRPN(self, tokens: List[str]) -> int:
operators = {'+', '-', '*', '/'}
stack = []
for token in tokens:
if token in operators:
r = stack.pop()
l = stack.pop()
if token == '+':   stack.append(l + r)
elif token == '-': stack.append(l - r)
elif token == '*': stack.append(l * r)
else:              stack.append(int(l / r))
else:
stack.append(int(token))
return stack[-1]


### 15. 792. Number of Matching Subsequences

• Sweep Line / HashMap
• Medium
• O(N+MK)

Hash first character to next_iterator. Go over S, pop matching iterators, get next, and hash back.

class Solution:
def numMatchingSubseq(self, S, words):
m = defaultdict(list)
for i, word in enumerate(words):
m[word[0]].append((i, 1))   # char to match -> (word_index, next_char_index)

total = 0
for c in S:
ws = m.pop(c, []) # match the char if possible
for i, j in ws:
if j == len(words[i]): total += 1
else:                  m[words[i][j]].append((i, j + 1))


### 16. 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

• Backtrack
• Hard
• O((MN)^2)

Not sure a better solution exists? Brute force backtrack is accepted in OJ. Can we optimize this a bit with bitmask?

Use bitmask to represent the matrix state (32 is only 5 x 5??) hash seen board to step we used to get here and prune???

class Solution:
def minFlips(self, mat: List[List[int]]) -> int:
nrow, ncol = len(mat), len(mat[0])

def flip(r, c):
for nr, nc in (r, c), (r-1, c), (r+1, c), (r, c-1), (r, c+1):
if nrow > nr >= 0 <= nc < ncol:
mat[nr][nc] ^= 1

def allZero(): return all(mat[r][c] == 0 for r, c in product(range(nrow), range(ncol)))

INT_MAX = 2 ** 32

def backtrack(i, pos):
if allZero(): return 0
if i == len(pos): return INT_MAX

moves = INT_MAX
for j, (r, c) in enumerate(pos[i:], i):
flip(r, c)
moves = min(moves, backtrack(j + 1, pos))
flip(r, c)
return moves + 1

pos=[(r, c) for r in range(nrow) for c in range(ncol)]
result = backtrack(0, pos)
return result if result < INT_MAX else -1


### 17. 1048. Longest String Chain

• DP
• Medium
• O(N*(log(N) + L^2))

Sort words by length. Hash word to its chain length where length is max(chain_length up to this one) + 1 or 1 if no chain.

class Solution:
def longestStrChain(self, words: List[str]) -> int:
words.sort(key=lambda x: (len(x), x))
chain_length = dict()

for word in words:
chain_length[word] = max(
chain_length.get(word[:i] + word[i+1:], 0)
for i in range(len(word))
) + 1

return max(chain_length.values())


• Priority Queue / Sweep line
• Medium
• O(N*logQ)

Simulate timeline. Use two priority queues, one for tasks one for working tasks, one for tasks to work on

the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.

-> elements on priority working use priority (pt, i)

class Solution:
def getOrder(self, tasks: List[List[int]]) -> List[int]:
#  st - start time  / pt - processing time / i - task index
working = []
order = []
current_time = 0
heapq.heappush(working, (pt, i, st))

if not working:
else:
pt, i, st = heapq.heappop(working)
current_time += pt
order.append(i)

return order


### 19. 359. Logger Rate Limiter

• Design / Hashmap
• Medium
• O(1) Armortized or O(Q) Worst case

Memory not concern: Hash messages to timestamps. Limited: Queue memory size -> deque + set

class Logger:
def __init__(T, limit=limit):
T.messages = set()
T.queue = deque()
T.limite = limite

def shouldPrintMessage(T, timestamp: int, message: str) -> bool:
while T.queue and timestamp - T.queue[0][1] >= T.limite:
msg = T.queue[0][0]
T.queue.popleft()
T.messages.remove(msg)

if message not in T.messages:
T.queue.append((message, timestamp))
return True
return False


### 20. 2115. Find All Possible Recipes from Given Supplies

• BFS Topsort
• Medium
• O()
class Solution:
def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
indegrees = dict()

for recipe, ingredents in zip(recipes, ingredients):
for ingredent in ingredents:
indegrees[recipe] = len(ingredents)

feasible = []
queue = deque(supplies)
while queue:
ingredent = queue.popleft()
indegrees[recipe] -= 1
if indegrees[recipe] == 0:
feasible.append(recipe)
queue.append(recipe)

return feasible


### 21. 552. Student Attendance Record II

• DP / State Machine
• Hard
• O(logN*M^3)

DP or state machine -> matrix power vector of init state * (state_trans_matrix) ^ N

m = 10 ** 9 + 7

# States

# A0L0 A0L1 A0L2 A1L0 A1L1 A1L2 Invalid

# 0 A0L0 = 0 A0L0 + P or 1 A0L1 + P or 2 A0L2 + P
# 1 A0L1 = 0 A0L0 + L
# 2 A0L2 = 1 A0L1 + L
# 3 A1L0 = 0 A0L0 + A or 4 A1L1 + P or 5 A1L2 + P or 1 A0L1 + A or 2 A0L2 + A
# 4 A1L1 = 3 A1L0 + L
# 5 A1L2 = 4 A1L1 + L

# Invalid = A0L2 + L or A1L2 + L or A1L0 + A or A1L1 + A or A1L2 + A

class Solution:
def checkRecord(self, n: int) -> int:
state = [1, 0, 0, 0, 0, 0]

for day in range(n):
new_state = [0] * 6
new_state[0] = (state[0] + state[1] + state[2])  % m
new_state[1] = state[0]
new_state[2] = state[1]
new_state[3] = (state[0] + state[1] + state[2] + state[3] + state[4] + state[5]) % m
new_state[4] = state[3]
new_state[5] = state[4]

state = new_state

return sum(state) % m


### 22. 2158. Amount of New Area Painted Each Day

• Sweep Line
• Hard
• O(NlogN)

Sort by time. Sweep through time, maintain a sorted window of open intervals.

class Solution:
def amountPainted(self, paint: List[List[int]]) -> List[int]:
records = []
max_pos = 0
for day, (start, end) in enumerate(paint):
records.append((start, day, 1))
records.append((end, day, -1))
max_pos = max(max_pos, end)
records.sort()

worklog = [0] * len(paint)
schedule = SortedList()
i = 0
for pos in range(max_pos + 1):
while i < len(records) and records[i][0] == pos:
_, day, job_type = records[i]
else:             schedule.remove(day)
i += 1
if schedule: worklog[schedule[0]] += 1
return worklog


### 23. 539. Minimum Time Difference

• Sort / Circular Array
• Medium
• O(NlogN)

Conver all time to minutes since midnight then sort, add time_0 + 24 * 60 to the end, so that the min difference with time wrap can be evaluated.

Compare adjacent time points and record the minimum difference.

class Solution:
def findMinDifference(self, timePoints: List[str]) -> int:
def _to_mins(timepoint):
hour, minutes = map(int, timepoint.split(":"))
return hour * 60 + minutes

times = list(map(_to_mins, timePoints))
times.sort()
times.append(times[0] + 24 * 60)

min_diff = 24 * 60
for t1, t2 in pairwise(times):
min_diff = min(min_diff, t2 - t1)

return min_diff


### 24. 777. Swap Adjacent in LR String

• Two Pointers
• Medium
• O(N)

R can only go right and can not cross other R or L. L can only go left and can not cross other R or L.
Hence, The numbers of “R”s and “L”s in “start “must be same as the numbers of “L”s and “R”s in “end”. The index “i” of “R” in “start” must be smaller than/in the left of the index “j” of the corresponding “R” in “end”. The index “i” of “L” in “start” must be greater than/in the right of the index “j” of the corresponding “L” in “end”.

class Solution:
def canTransform(self, start: str, end: str) -> bool:
if len(start) != len(end): return False

A = [(s, idx) for idx, s in enumerate(start) if s == 'L' or s == 'R']
B = [(e, idx) for idx, e in enumerate(end) if e == 'L' or e == 'R']
if len(A) != len(B): return False

for (s, i), (e, j) in zip(A, B):
if s != e: return False
if s == 'L' and i < j: return False
if s == 'R' and i > j: return False
return True


### 25. 302. Smallest Rectangle Enclosing Black Pixels

• DFS/BFS / Binary Search
• Hard
• O(MN) or O(MlogN + NlogM)

DFS to find min_r, max_r, min_c, max_c; or binary search twice on [1 in row[i]] which evals to FFFTTTFFF to find min and max. Do the same on columns.

class Solution:
def minArea(self, image: List[List[str]], x: int, y: int) -> int:
nrow, ncol = len(image), len(image[0])

# bisect_left
l, h = 0, y
while l < h:
m = (l + h) // 2
if any(image[r][m] == '1' for r in range(nrow)):
h = m
else:
l = m + 1
left = l  # left is the leftmost column on the left that has a '1'

# bisect_right
l, h = y, ncol
while l < h:
m = (l + h) // 2
if any(image[r][m] == '1' for r in range(nrow)):
l = m + 1
else:
h = m
right = l # right is the leftmost column on the right that don't has '1'

# bisect left
l, h = 0, x
while l < h:
m = (l + h) // 2
if "1" in image[m]:
h = m
else:
l = m + 1
top = l

#bisect_right
l, h = x, nrow
while l < h:
m = (l + h) // 2
if "1" in image[m]:
l = m + 1
else:
h = m
bottom = l

return (bottom - top) * (right - left)


### 26. 652. Find Duplicate Subtrees

• Hash Map / Tree
• Medium
• O(N^2) Time and Space.

Hash subtree to list of subtree roots. Optimize how to hash subtree?

class Solution:
def findDuplicateSubtrees(self, root):
stack = [(root, 0)]
trees = dict()
node_to_key = dict()
node_to_key[None] = -1

while stack:
node, post = stack.pop()
if post:
subtree_key = node.val, node_to_key[node.left], node_to_key[node.right]  # serialization of post-order traversal
trees.setdefault(subtree_key, []).append(node)
node_to_key[node] = subtree_key
else:
stack.append((node, 1))
if node.left: stack.append((node.left, 0))
if node.right: stack.append((node.right, 0))

return [roots[0] for roots in trees.values() if len(roots) > 1]


### 27. 329. Longest Increasing Path in a Matrix

• Topological Sort / BFS / DFS + Memoization
• Hard
• O(MN)

Make directed graph where cell with lower value has out edge to neighboring cells with higher value.

Start from cells with 0 in degree. Do BFS and decrease in_degrees of the cell moved to. Once a cell’s in degree decreased to 0, on queue the cell location. Count the depth for the BFS search tree.

class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
# edge case handle
if not matrix or not matrix[0]: return 0

nrow, ncol = len(matrix), len(matrix[0])

# graph processing
out_edges = defaultdict(list) # O(N) space
in_degrees = defaultdict(int) # O(N) space

def get_neighbor(r, c):
for nr, nc in (r-1,c),(r+1,c),(r,c-1),(r,c+1):
if nrow > nr >= 0 <= nc < ncol:
yield nr, nc

# O(N)
for r, c in product(range(nrow), range(ncol)):
for nr, nc in get_neighbor(r, c):
if matrix[nr][nc] > matrix[r][c]:
out_edges[(r,c)].append((nr, nc))
in_degrees[(nr, nc)] += 1

# find the starting level
queue = deque([]) # O(N) space
# O(N)
for r, c in product(range(nrow), range(ncol)):
if in_degrees[(r, c)] == 0:
queue.append((r, c, f"({r},{c})"))

# bfs topological sort to count the number of levels
length = 0
best = None
# O(4N) Time
while queue:
length += 1
for _ in range(len(queue)):
r, c, path = queue.popleft()
node = (r, c)
for nei in out_edges[node]:
in_degrees[nei] -= 1
if in_degrees[nei] == 0:
nr, nc = nei
best_path = path + f"->({nr},{nc})"
queue.append((nr, nc, path + f"->({nr},{nc})"))

# print(best_path)
return length

class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix or not matrix[0]: return 0
nrow, ncol = len(matrix), len(matrix[0])

stack = []
in_degrees = defaultdict(int)
for r, c in product(range(nrow), range(ncol)):
for nr, nc in (r-1,c), (r+1,c), (r,c-1), (r,c+1):
if not (nrow > nr >= 0 <= nc < ncol) or matrix[nr][nc] <= matrix[r][c]: continue
in_degrees[nr, nc] += 1

if (r, c) not in adj_list:
stack.append(((r, c), 1))

max_path_to_loc = dict()
max_path_length = 0
for r, c in product(range(nrow), range(ncol)):
if (r, c) in in_degrees: continue

stack = [((r, c), 1)]
while stack:
loc, path_length = stack.pop()
if max_path_to_loc.get(loc, 0) >= path_length: continue
max_path_length = max(max_path_length, path_length)
max_path_to_loc[loc] = path_length
stack.append((nei, path_length + 1))

return max_path_length


### 28. 418. Sentence Screen Fitting

• Greedy / Memoization
• Medium
• O(N)

Greedy fill row by row. May cache on (start_word_idx) -> [end_idx, n_rounds] to speed up next time when a row starts with the same index.

class Solution:
def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
ans = 0
memo = dict()
r, start_idx = 0, 0
total_len = sum([len(s) for s in sentence]) + len(sentence)
while r < rows:
if start_idx not in memo:
end_idx = start_idx
rounds, remainder = divmod(cols, total_len)
while remainder >= len(sentence[end_idx]):
remainder -= len(sentence[end_idx]) + 1
end_idx += 1
if end_idx == len(sentence):
end_idx = 0
rounds += 1
memo[start_idx] = [end_idx, rounds]

start_idx, rounds = memo[start_idx]
ans += rounds
r += 1
return ans


### 29. 384. Shuffle an Array

• Math
• Medium
• O(N)

The algorithm effectively puts all the elements into a hat; it continually determines the next element by randomly drawing an element from the hat until no elements remain. The algorithm produces an unbiased permutation: every permutation is equally likely. The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place.

Iterate over i in range(n), random sample i <= j < n, swap A[i], A[j]. This is call Fisher-Yates Shuffle, Also known as the Knuth shuffle after Donald Knuth proof

prob a[0] will remain at a[0] is 1 / n prob a[0] will be at a[1] is 1 a[0] swapped to a[1] and stay there 1/n * 1/(n-1) 2 a[0] swapped to a[j] j > 1 and then swapped back to a[1] 1/n * (n-2) * 1/(n-1) * 1 / (n - 1) 1 and 2 sum up to 1/n

class Solution:
def __init__(self, nums):
self.array = nums
self.original = list(nums)
self.n = len(nums)

def reset(self):
self.array = self.original
self.original = list(self.original)
return self.array

def shuffle(self):
array = self.array
for i in range(self.n):
j = random.randrange(i, self.n)
array[i], array[j] = array[j], array[i]
return array


### 30. 1554. Strings Differ by One Character

• Rabin Karp / HashMap
• Medium
• O(NM^2) worst case or O(MN) without collision

Rabin Karp hash all words h[i] = hash of word[i] = sum(26^j * word[i][j]) % m. Iterrate over positions j, create wildcard hash by (h[i] - word[i][j] * 26 ^ j) % m. check words with same hash to verify differ by one.

class Solution:
# def differByOne(self, words: List[str]) -> bool:
#     seen = set()
#     for word in words:
#         chars = list(word)
#         for i in range(len(chars)):
#             original = chars[i]
#             chars[i] = '*'
#             key = tuple(chars)
#             if key in seen: return True
#             chars[i] = original
#     return False

def differByOne(self, words):
n, m = len(words), len(words[0])
hashes = [0] * n
MOD = 1_000_000_007

for i, word in enumerate(words):
for j, char in enumerate(word):
hashes[i] = (26 * hashes[i] + (ord(char) - ord('a'))) % MOD

def diff_by_1(w1, w2):
diffs = 0
for c1, c2 in zip(w1, w2): diffs += c1 != c2
return diffs == 1

base = 1
for j in reversed(range(m)):
hashmap = defaultdict(list)
for i, h in enumerate(hashes):
hp = (h - (ord(words[i][j]) - ord('a')) * base) % MOD
if hp in hashmap and any(diff_by_1(words[i], word) for word in hashmap[hp]): return True
hashmap[hp].append(words[i])
base = 26 * base % MOD
return False


### 31. 1423. Maximum Points You Can Obtain from Cards

• Sliding Window
• Medium
• O(N)

Slide a circular window to cover all cases between the two extremes, all left and all right.

class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
if k == len(cardPoints): return sum(cardPoints)
rs = sum(cardPoints[-k:])
max_score = rs
ls = 0
for l in range(k):
ls += cardPoints[l]
rs -= cardPoints[-(k-l)]
max_score = max(max_score, ls + rs)
return max_score

• Trie
• Hard
• O(NK^2 + QK)

Build prefix and suffix Trie. Test intersection. Or build trie with suffix[:i]#prefix for all i for each word. Check suffix#prefix at run time.

Trie = lambda: defaultdict(Trie)

class WordFilter:
def __init__(self, words):
self.trie = Trie()

for idx, word in enumerate(words):
for i in range(len(word)+1):
node = self.trie
word_to_insert = word[i:]+'#'+word
for c in word_to_insert:
node, node['idx'] = node[c], idx

def f(self, prefix, suffix):
node = self.trie
for c in suffix + '#' + prefix:
if c not in node: return -1
node = node[c]
return node['idx']


### 33. 1218. Longest Arithmetic Subsequence of Given Difference

• DP
• Medium
• O(N)

1D DP O(N^2) f(i) = f(arr.index(arr[i] - diff)) + 1 or 1 -> kadane f(d) = f(d-diff) + 1 or 1

class Solution:
def longestSubsequence(self, arr: List[int], difference: int) -> int:
dp = dict()
max_length = 0
for i, d in enumerate(arr):
last_d = d - difference
dp[d] = dp.get(last_d, 0) + 1
max_length = max(max_length, dp[d])
return max_length


### 34. 631. Design Excel Sum Formula

• Design?
• Hard
• O(MN)

class Excel:
def __init__(self, H: int, W: str):
self.cells = [
{letter: {"value": 0, "sum": None}
for letter in string.ascii_uppercase
}
for h in range(H + 1)
]

def set(self, r: int, c: str, v: int) -> None:
self.cells[r][c] = {"value": v, "sum": None}

def get(self, r: int, c: str) -> int:
cell = self.cells[r][c]

def sum(self, r: int, c: str, strs: List[str]) -> int:
self.cells[r][c]["sum"] = self._parse(strs)
return self.get(r, c)

def _parse(self, strs: List[str]):
counter = Counter()
for s in strs:
start, end = s.split(":")[0], s.split(":")[1] if ":" in s else s
for r in range(int(start[1:]), int(end[1:]) + 1):
for ci in range(ord(start[0]), ord(end[0]) + 1):
counter[(r, chr(ci))] += 1
return counter


### 35. 954. Array of Doubled Pairs

• Math / Sorting
• Medium
• O(N + K)

Count -> Sort keys by abs value. Go over sorted keys, if double has 0 occurrences found a violation, otherwise, decrement the count for double.

class Solution:
def canReorderDoubled(self, arr: List[int]) -> bool:
freq_counts = Counter(arr)
for d in sorted(arr, key=abs):
if freq_counts[d] == 0: continue
if freq_counts[2 * d] == 0: return False
freq_counts[d] -= 1
freq_counts[2 * d] -= 1
return True


### 36. 2135. Count Words Obtained After Adding a Letter

• Medium
• O(MN)

Either hash the augmented version of source words or for each target word, drop a character and hash to check with source word hashes. Depeneds on which is larger.

class Solution:
def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
def hash_word(word):
result = 0
for c in word:
result += 1 << (ord(c) - ord('a'))
return result

count = 0

#         sources = set()
#         for word in startWords:

#         for t in targetWords:
#             chars = list(t)
#             for i in range(len(chars)):
#                 key = hash_word(chars[:i] + chars[i+1:])
#                 if key in sources:
#                     count += 1
#                     break

#         return count
letters = set(string.ascii_lowercase) # set('abcdefghijklmnopqrstuvwxyz')
sources = set()
for word in startWords:
for char in letters.difference(word):

for target in targetWords:
if hash_word(target) in sources:
count += 1
continue

return count


### 37. 690. Employee Importance

• Tree
• Medium
• O(N)

Traverse the tree, add up node property values.

class Solution:
def getImportance(self, employees: List['Employee'], eid: int) -> int:
total = 0
queue = deque([eid])
id_to_employee = dict()
for e in employees: id_to_employee[e.id] = e

while queue:
eid = queue.popleft()
total += id_to_employee[eid].importance
queue.extend(id_to_employee[eid].subordinates)


### 38. 394. Decode String

• Stack
• Medium
• O(N)

Keep track of string and rep, when encounter ‘[’ put both on stack, when encounter ‘]’ pop string and rep update string with string = prev + curr * rep.

class Solution:
def decodeString(self, s: str) -> str:
stack, curr, rep = [], [], 0
for c in s:
if c.isdigit(): rep = 10 * rep + int(c)
if c.isalpha(): curr.append(c)
if c == '[':
stack.append((curr, rep))
curr, rep = [], 0
if c == ']':
prev, prev_rep = stack.pop()
curr = prev + curr * prev_rep
return "".join(curr)

def decodeString(self, s: str) -> str:
def decode(i=0):
result, rep = [], 0
while i < len(s) and s[i] != ']':
c = s[i]
if c.isdigit(): rep = 10 * rep + int(c)
if c.isalpha(): result.append(c)
if c == "[":
i += 1
ds, i = decode(i)
result.extend(ds * rep)
rep = 0
i += 1
return result, i
r, _ = decode(0)
return "".join(r)


### 39. 727. Minimum Window Subsequence

• Two Pointers
• Hard
• O(MN)

Start from o rfind(next) till end mark r. From r lfind(prev) until start mark l. keep track of min(r-l+1). Move to l+1 and start again.

class Solution:
def minWindow(self, S, T):
n = len(S)

def match_to_last(l):
i, k = l, 0
while k < len(T) and i < n:
if S[i] == T[k]: k += 1
if k == len(T):  return i
i += 1
return -1

def match_to_first(r):
i, k = r, len(T) - 1
while k >= 0 and i >= 0:
if S[i] == T[k]: k -= 1
if k == -1: return i
i -= 1
return -1

i, result = -1, ""
while i < len(S):
l = i + 1
r = match_to_last(l)  # r i
if r == -1: return result
l = match_to_first(r)
if r - l + 1 < len(result) or not result: result = S[l:r+1]
i = l + 1
return result


### 40. 1277. Count Square Submatrices with All Ones

• DP
• Medium
• O(N^2)

S: f(i, j) is length of desired matrics with bottom right at i,j. R: f(i, j) = min(f[i-1,j], f(i, j-1), f(i-1,j-1)) + 1 or 0. O: Original problem is sum(f(i,j) for i for j).

class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
nrow, ncol = len(matrix), len(matrix[0])
dp = [[0] * (ncol + 1) for _ in range(nrow + 1)]
for r, c in product(range(1, nrow + 1), range(1, ncol + 1)):
if matrix[r-1][c-1] == 0: continue
dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1
return sum(sum(row) for row in dp)


### 41. 664. Strange Printer

• DP
• Hard
• O(N^2)

S: f(i,j) = # ops to cover [i to j) R: relation f(i,j) = min(f(i+1,j) +1, f(i+1, k) + f(k+1, j) for k between i and j) T: hi: left to right, lo hi to left B: f(i, j) = f(i+1,j) + 1 O: solution to original problem is f(i, n). T: O(N^2)

class Solution:
def strangePrinter(self, s: str) -> int:
s = "".join(ch for i, ch in enumerate(s) if i == 0 or s[i-1] != ch)  # compress, consecutive rep don't change answer
n = len(s)
dp = [[0] * (n + 1) for _ in range(n+1)]
for hi in range(n+1):
for lo in reverse(range(hi)):
dp[lo][hi] = dp[lo+1][hi] + 1
for mid in range(lo+1, hi):
if s[lo] == s[mid]:
dp[lo][hi] = min(dp[lo][hi], dp[lo][mid] + dp[mid+1][hi])

return dp[0][n]


### 42. 803. Bricks Falling When Hit

• Union Find
• Hard
• O(MN)

Reverse the order and do union-find. Use a sink/hook for the ceiling.
Can use r * ncol + c as integer id for location to use list as parents to speed up.

class UnionFind:
def __init__(self):
self.parents = dict()
self.sizes = defaultdict(lambda: 1)

def find(self, i):
if i not in self.parents: self.parents[i] = i
while i != self.parents[i]:
self.parents[i] = self.find(self.parents[i])
i = self.parents[i]
return i

def union(self, p, q):
root_p, root_q = map(self.find, (p, q))
if root_p == root_q: return False
small, big = sorted([root_p, root_q], key=lambda x: self.sizes[x])
self.parents[small] = big
self.sizes[big] += self.sizes[small]
return True

def size(self, i):
return self.sizes[self.find(i)]

class Solution:
def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
nrow, ncol = len(grid), len(grid[1])
uf = UnionFind()

def neighbors(r, c):
for nr, nc in (r-1,c), (r+1,c), (r,c-1), (r,c+1):
if nrow > nr >= 0 <= nc < ncol:
yield nr, nc

g = [row.copy() for row in grid]
for r, c in hits: g[r][c] = 0

ceiling = (-1, -1)
for r, c in product(range(nrow), range(ncol)):
if g[r][c] == 0: continue
if r == 0:          uf.union((r, c), ceiling)
if r and g[r-1][c]: uf.union((r, c), (r-1, c))
if c and g[r][c-1]: uf.union((r, c), (r, c-1))

dropped = []
for r, c in reversed(hits):
if grid[r][c] == 0:
dropped.append(0)
continue

num_stable = uf.size(ceiling)
for nr, nc in neighbors(r, c):
if g[nr][nc]:
uf.union((r,c), (nr,nc))

if r == 0: uf.union((r,c), ceiling)
g[r][c] = 1
now_stable = uf.size(ceiling)

if now_stable > num_stable:
dropped.append(now_stable - num_stable -1)
else:
dropped.append(0)
return list(reversed(dropped))


### 43. 528. Random Pick with Weight

• Math / Binary Search
• Medium
• O(N) init O(logN) search

Calculate CDF, do binary search on it.

class Solution:
def __init__(self, w: List[int]):
cdf = []
accum = 0
for wt in w:
accum += wt
cdf.append(accum)
self.cdf = cdf
self.n = len(cdf)

def pickIndex(self) -> int:
return bisect_left(self.cdf, randint(1, self.cdf[-1]), 0, self.n - 1)


### 44. 1691. Maximum Height by Stacking Cuboids

• DP / Greedy
• Hard
• O(NlogN + N^2)

Proof we want all boxes to be the tallest side up. Use contracdiction. Then sort and DP up. dp[i] = max(dp[j] +boxes[j].height for all j if j fit)

if the one with longest edge not as height is on the top of the cuboid stack, we can simply rotate it so the it contriubutes more height if the one with longest edge is in the middle, let’s say it is A and the 3 edges are [A1, A3, A2] (A3 > A2 && A3 > A1, A2 is not longest but it is the height), the one on top of A is B[B1, B2, B3] (B3 >= B2 >= B1): we have A1 >= B1 && A3 >= B2 && A2 >= B3 then: A3 > A2 >= B3, A2 >= B3 >= B2, A1 >= B1 so we can rotate A from [A1, A3, A2] to [A1, A2, A3] without afffecting B but make the total height larger (increase by A3 - A2)

class Solution:
def maxHeight(self, cuboids: List[List[int]]) -> int:
boxes = [[0, 0, 0]] + sorted(map(sorted, cuboids))
n = len(boxes)
dp = [0] * n
for r in range(1, n):
for l in range(r):
if all(boxes[l][k] <= boxes[r][k] for k in range(3)):
dp[r] = max(dp[r], dp[l] + boxes[r][2])
return max(dp)


### 45. 1345. Jump Game IV

• BFS
• Hard
• O(N)

Find minimum number of steps: BFS with memoization for pruning

Save a mapping from number to list of positions with the number. Since we are looking at shortest path, apply BFS with element (pos, step) on the queue. When pos == last, return step. Otherwise, collect all jumpable positions if haven’t visited those yet(ie, if we jump there, it will be shortest path to jump over there), on queue (next_pos, step + 1).

class Solution:
def minJumps(self, arr: List[int]) -> int:
n = len(arr)

num_idx = defaultdict(list)
for idx, num in enumerate(arr):
num_idx[num].append(idx)

pos_visited, num_visited = set(), set()
queue = deque([(0, 0)])
while queue:
idx, step = queue.popleft()
num, neighbors = arr[idx], []

if idx == n - 1: return step
if idx - 1 >= 0: neighbors.append(idx - 1)
if idx + 1 <= n - 1: neighbors.append(idx + 1)
if num not in num_visited: neighbors.extend(num_idx[num])
for neighbor in neighbors:
if neighbor in pos_visited: continue
queue.append((neighbor, step + 1))



### 46. 1987. Number of Unique Good Subsequences

• DP
• Hard
• O(N)

Leave dangling 0 to the last. It is just the raw count of 0. Expansion f(i, k) be # of good subsequences end at i with value k. f(i, k) = sum(f(i-1, k) + b[i] for all k)

mod = 1_000_000_007

class Solution:
def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
dp = [0, 0]
for c in binary:
if c == '0':
end_with_0 = (sum(dp)) % mod
end_with_1 = dp[1]
else:
end_with_0 = dp[0]
end_with_1 = (sum(dp) + 1) % mod
dp = [end_with_0, end_with_1]
return (sum(dp) + ('0' in binary)) % mod


### 47. 447. Number of Boomerangs

• HashMap
• Medium
• O(N^2)

Iterate over node as i. Inner loop iterate over all other nodes, count number of nodes per distance to i. Aggregate to total.

class Solution:
def numberOfBoomerangs(self, points: List[List[int]]) -> int:
def dist(x1, y1, x2, y2): return (x2 - x1) ** 2 + (y2 - y1) ** 2

total = 0
for i, p1 in enumerate(points):
dist_to_nodes = defaultdict(int)
for j, p2 in enumerate(points):
if i == j: continue
d = dist(*p1, *p2)
dist_to_nodes[d] += 1

for n in dist_to_nodes.values():
total += n * (n - 1)



### 48. 1397. Find All Good Strings

• String / KMP
• Hard
• O(N)

Treat evil as pattern, dp(i, j, lower, upper) = number of good string at string[i] matched at pattern[j] where currently we can choose lower to upper. dp(i, j, lower, upper) = sum( dp(i + 1, j’, lower’, upper’) for all k ~ (lower, upper, s1, s2, i)) Each i, we have choices depends on s1[i], s2[i] lower, upper, once we made a choice k, we find j’ by matching k with evil[j].

class Solution:
def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
def lps(p):
m = len(p)
lps = [0, 0]
j = 0
for i in range(1, m):
while j and p[i] != p[j]: j = lps[j]
if p[i] == p[j]: j += 1
lps.append(j)
return lps

def char_to_int(c): return ord(c) - ord('a')
def int_to_char(i): return chr(i + ord('a'))

table = lps(evil)
m = len(evil)

@cache
def f(i, j, lower, upper):
if j == m: return 0
if i == n: return 1

lo = char_to_int(s1[i]) if lower else 0
hi = char_to_int(s2[i]) if upper else 25

total = 0
for k, choice in enumerate(map(int_to_char, range(lo, hi+1)), lo):
jj = j
while jj and choice != evil[jj]: jj = table[jj] # don't match jump back
if choice == evil[jj]: jj += 1
total += f(i + 1, jj, lower and k == lo, upper and k == hi)

return f(0, 0, True, True) % (10 ** 9 + 7)



### 49. 489. Robot Room Cleaner

• DFS
• Hard
• O(MN)

Detail on how to manage direction. Backtrack without changing direction by rotating backward then rotating back. Try all four directions by RRRR or LLLL.

class Solution:
def cleanRoom(self, robot):
# counter clockwise
directions = [
(-1, 0), # up
(0, -1), # left
(1, 0),  # down
(0, 1),  # right
]

def step_back():
robot.turnLeft()
robot.turnLeft()
robot.move()
robot.turnLeft()
robot.turnLeft()

visited = set()

def dfs(x, y, d):
robot.clean()
for _ in range(4):
dx, dy = directions[d]
nx, ny = x + dx, y + dy
if (nx, ny) not in visited and robot.move(): dfs(nx, ny, d)
robot.turnLeft()
d = (d + 1) % 4
step_back()

dfs(0, 0, 0)


### 50. 900. RLE Iterator

• Design
• Medium
• O(N)

Use index and used to keep track of the RLE we are using and how many used. Avoid modifying encoding itself.

class RLEIterator:
def __init__(T, A: List[int]):
T.A, T.i, T.used = A, 0, 0

def next(T, n: int) -> int:
A, i, used = T.A, T.i, T.used
while i < len(A) and A[i] - used < n:
n -= A[i] - used
i += 2
used = 0

ret = -1
if i < len(A):
used += n
ret = A[i+1]

T.A, T.i, T.used = A, i, used
return ret


### 51. 407. Trapping Rain Water II

• Union Find
• Hard
• O(MN)

Keep track of area of sroundeded low grounds through time. Iterate over time, update area and accumulate. Use Union Find to keep track of connected components, each corresponds to a srounded low grounds. Use a sink point for anything touching the boundry. Total area of srounded low grounds = total size of connected components - size of sink.

class UnionFind:
def __init__(self):
self.parents = dict()
self.sizes = dict()
self.n_sets = 0

def __contains__(self, i):
return i in self.parents

def insert(self, i):
if self.__contains__(i): return
self.parents[i] = i
self.sizes[i] = 1
self.n_sets += 1

def find(self, i):
while i != self.parents[i]:
self.parents[i] = self.find(self.parents[i])
i = self.parents[i]
return i

def union(self, p, q):
root_p, root_q = map(self.find, (p, q))
if root_p == root_q: return False
small, big = sorted([root_p, root_q], key=lambda x: self.sizes[x])
self.parents[small] = big
self.sizes[big] += self.sizes[small]
self.n_sets -= 1
return True

class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
nrow, ncol = len(heightMap), len(heightMap[0])
order = defaultdict(list)
for r in range(nrow):
for c in range(ncol):
order[heightMap[r][c]].append((r, c))

sink = (nrow, ncol)
uf = UnionFind()
uf.insert(sink)

total = 0
curr_size = 0
for t in range(max(order.keys())+1):
if t not in order:
total += curr_size
continue

for r, c in order[t]: uf.insert((r, c))
for r, c in order[t]:
if 0 == r or 0 == c or r == (nrow - 1) or c == (ncol - 1): uf.union((r, c), sink)
for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)):
if nr < 0 or nr >= nrow or nc < 0 or nc >= ncol: continue
if heightMap[nr][nc] <= t: uf.union((r, c), (nr, nc))

curr_size = len(uf.parents) - uf.sizes[uf.find(sink)]
total += curr_size


### 52. 794. Valid Tic-Tac-Toe State

• Array
• Medium
• O(MN)

1 Cant have two winners 2 If X win X must has one more play than O 3 If O win O must has same play as X 4 X O must one play apart

class Solution:
def validTicTacToe(self, board: List[str]) -> bool:

def check_player(symbol):
count, has_won = 0, False

row_counts = [0] * 3
col_counts = [0] * 3
diag_counts = [0] * 2

for i in range(3):
for j in range(3):
if board[i][j] != symbol: continue
count += 1
row_counts[i] += 1
col_counts[j] += 1
if i == j: diag_counts[0] += 1
if i + j == 2: diag_counts[1] += 1

if 3 in row_counts or 3 in col_counts or 3 in diag_counts: has_won = True
return count, has_won

X_count, X_has_won = check_player('X')
O_count, O_has_won = check_player('O')

if X_has_won and O_has_won: return False
if X_has_won: return X_count == O_count + 1
if O_has_won: return X_count == O_count
return (X_count - O_count) in [0, 1]


### 53. 1877. Minimize Maximum Pair Sum in Array

• Sort + Greedy
• Medium
• O(NlogN + N)

Sort then two pinter finding max. proof four numbers. Given 4 numbers: al <= ai <= aj <= ar. Then max(al+ar, ai+aj) is always <= max(al+ai, aj+ar).

class Solution:
def minPairSum(self, nums: List[int]) -> int:
nums.sort()
max_pair_sum = 0
l, r = 0, len(nums)-1
while l < r:
max_pair_sum = max(max_pair_sum, nums[l] + nums[r])
l += 1
r -= 1
return max_pair_sum


### 54. 2018. Check if Word Can Be Placed In Crossword

• Array
• Medium
• O(MN)

Slide word sized window horizontally and vertically, trying to match word in both direction, and check for boundries.

    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
nrow, ncol = len(board), len(board[0])
m = len(word)

def check_match(slots, w):
for c1, c2 in zip(slots, w):
if c1 not in [" ", c2]: return False
return True

def row_scan(w):
for r in range(nrow):
for c in range(ncol):
if c + m > ncol: continue
if c and board[r][c-1] != "#": continue
if c + m <= ncol - 1 and board[r][c + m] != "#": continue
slots = board[r][c:c+m]
if check_match(slots, w): return True
return False

def col_scan(w):
for c in range(ncol):
for r in range(nrow):
if r + m > nrow: continue
if r and board[r-1][c] != "#": continue
if r + m <= nrow - 1 and board[r+m][c] != "#": continue
slots = [board[r + i][c] for i in range(m)]
if check_match(slots, w): return True
return False

return row_scan(word) or col_scan(word) or row_scan(word[::-1]) or col_scan(word[::-1])



### 55. 772. Basic Calculator III

• Stack
• Hard
• O(N)

Extension of 227 with parenthese. When encounter (, put it on stack and reset operand and operator. When encounter ), evaluate what is on the stack util (.

class Solution:
def calculate(self, s: str) -> int:
def operation():
if operator == '+': stack.append(operand)
if operator == '-': stack.append(-operand)
if operator == '*': stack.append(stack.pop() * operand)
if operator == '/': stack.append(int(stack.pop() / operand))

stack = []
operand, operator = 0, '+'
for c in s:
if c.isdigit():
operand = operand * 10 + int(c)
if c == '(':
stack.append(operator)
operand, operator = 0, '+'
if c in '+-*/)':
operation()
if c == ')':
operand = 0
while isinstance(stack[-1], int):
operand += stack.pop()
operator = stack.pop()
operation()
operand, operator = 0, c

operation()
return sum(stack)


### 56. 990. Satisfiability of Equality Equations

• Union Find
• Medium
• O(N)

Create connected components with equality. Then check all the inequality for violation.

class UnionFind:
def __init__(self, n=26):
self.parents = list(range(n))

def find(self, i):
while i != self.parents[i]:
self.parents[i] = self.find(self.parents[i])
i = self.parents[i]
return i

def union(self, p, q):
root_p, root_q = self.find(p), self.find(q)
if root_p == root_q: return False
self.parents[root_p] = root_q
return True

class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
uf = UnionFind(26 + 1)

for eq in equations:
if eq[1] == "!": continue
a, b = map(lambda x: ord(x) - ord("a"), [eq[0], eq[~0]])
uf.union(a, b)

for eq in equations:
if eq[1] == "=": continue
a, b = map(lambda x: ord(x) - ord("a"), [eq[0], eq[~0]])
if uf.find(a) == uf.find(b): return False

return True


### 57. 1240. Tiling a Rectangle with the Fewest Squares

• Backtrack
• Hard
• O(MN*N^M) where we sort N, M such that M < N
1. Key: fill the rectangle with squares bottom up. thus we can use 1D array to represent the state.
• i.e. [2,2,4,4,4,4,1] means bottom left is a 2 x 2 square, on its right is a 4 x 4 and then a 1 x 1 on the right.
• i.e. [2,2,4,7,7,7,1] means bottom left is a 2 x 2 square, on its right is a 4 x 4, but on the top of the 4 x 4 shifted to right by 1, there is a 3 x 3 square. And finally a 1 x 1 on the bottom right.
2. Do backtrack
class Solution:
def tilingRectangle(self, n: int, m: int) -> int:
if n > m: return self.tilingRectangle(m, n)
total = n * m # relaxation form all 1x1 upperbound

h = [0] * n   # h[i] is height at x == i

def backtrack(curr, total):

# filled the space
if (min_height := min(h)) == m: return curr

# figure out the range for height of square we can stick in here
l = r = h.index(min_height)
while r < n and h[r] == h[l] and (r - l + 1 + min_height) <= m: r += 1

# try all size squares that is allowed
for j in range(r-1, l-1, -1):
for k in range(l, j+1): h[k] += j - l + 1
total = min(total, backtrack(curr + 1, total))
for k in range(l, j+1): h[k] -= j - l + 1

return backtrack(0, total)


### 58. 726. Number of Atoms

• Stack / HashMap
• Hard
• O(N^2)
class Solution:
def countOfAtoms(self, formula: str) -> str:
def get_digit(i):
j = i
while j < len(formula) and formula[j].isdigit(): j += 1
if i == j: return 1, j
return int(formula[i:j]), j

def get_atom(i):
j = i + 1
while j < len(formula) and formula[j].islower(): j += 1
return formula[i:j], j

stack = []
i = 0
m = Counter()
while i < len(formula):
if formula[i] == "(":
stack.append(m)
m = Counter()
i += 1
elif formula[i] == ")":
repeats, j = get_digit(i + 1)
for k in m: m[k] *= repeats
if stack:
prev = stack.pop()
prev.update(m)
m = prev
i = j
else:
atom, j = get_atom(i)
repeats, k = get_digit(j)
m[atom] += repeats
i = k

result = []
for k in sorted(m.keys()):
result.append(k)
if m[k] != 1: result.append(str(m[k]))

return ''.join(result)


### 59. 1032. Stream of Characters

• Trie
• Hard
• O(K) query

Make a Trie of reversed words. Keep append characters to stream, check reverse of stream with the Trie.

class TrieNode(defaultdict):
def __init__(self):
self.default_factory = TrieNode
self.terminal = False

class StreamChecker:
def __init__(self, words: List[str]):
self.root = TrieNode()
self._init_trie(words)
self.stream = []

def _init_trie(self, words):
for word in words:
node = self.root
for c in reversed(word):
node = node[c]
node.terminal = True

def query(self, letter: str) -> bool:
self.stream.append(letter)
node = self.root
for c in reversed(self.stream):
if c not in node: return False
node = node[c]
if node.terminal: return True


### 60. 939. Minimum Area Rectangle

• Math / Geometry
• Medium
• O(N^2)
class Solution:
def minAreaRect(self, points: List[List[int]]) -> int:
S = set(map(tuple, points))
ans = float('inf')
for (x1, y1), (x2, y2) in combinations(points, 2):
if x1 != x2 and y1 != y2 and (x1, y2) in S and (x2, y1) in S:
ans = min(ans, abs(y2 - y1) * abs(x2 - x1))
return ans if ans != float('inf') else 0


### 61. 2092. Find All People With Secret

• Union Find
• Hard
• O(N^2)

Use a set to keep track of people who know the secret. Iterate over meetings grouped by time in time order.

Make undirected graph, put people in the meeting that know the secret on to a queue. Go over the people on the queue, update the people linked to this one to the set and push on to queue. (DFS or BFS both are fine)

class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [1] * n

def find(self, p: int) -> int:
"""Find with path compression"""
if p != self.parent[p]:
self.parent[p] = self.find(self.parent[p])
return self.parent[p]

def union(self, p: int, q: int) -> bool:
"""Union with rank"""
prt, qrt = self.find(p), self.find(q)
if prt == qrt: return False
if self.rank[prt] > self.rank[qrt]: prt, qrt = qrt, prt
self.parent[prt] = qrt
self.rank[qrt] += self.rank[prt]
return True

class Solution:
def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
uf = UnionFind(n)
uf.union(0, firstPerson)
for _, grp in groupby(sorted(meetings, key=lambda x: x[2]), key=lambda x: x[2]):
seen = set()
for x, y, _ in grp:
uf.union(x, y)
for x in seen:
if uf.find(x) != uf.find(0):
uf.parent[x] = x # reset
return [x for x in range(n) if uf.find(x) == uf.find(0)]


### 62. 1272. Remove Interval

• Sweep Line
• Medium
• O(N)

Go through intervals, compare l with l’, if l < l’ take min(l’, r) as r. compare r with r’ if r > r’ take max(l, r’) as l.

class Solution:
def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
ref_l, ref_r = toBeRemoved
results = []
for l, r in intervals:
if l < ref_l: results.append([l, min(r, ref_l)])
if r > ref_r: results.append([max(l, ref_r), r])
return results


### 63. 562. Longest Line of Consecutive One in Matrix

• DP
• Medium
• O(MN)

dp[r][c] is tuple (h, v, md, od) that is length of consecutive ones from left, top, main diagonal, off diagonal.

class Solution:
def longestLine(self, mat: List[List[int]]) -> int:
nrow, ncol = len(mat), len(mat[0])
#     h   v  d1 d2
dp = [[0, 0, 0, 0]] * ncol
max_length = 0
for r, row in enumerate(mat):
ndp = [[0, 0, 0, 0]] * ncol
for c, cell in enumerate(row):
if cell == 0: continue
h = 1 if c == 0 else ndp[c-1][0] + 1
v = dp[c][1] + 1
d1 = 1 if c == 0 else dp[c-1][2] + 1
d2 = 1 if c == ncol - 1 else dp[c+1][3] + 1
ndp[c] = [h, v, d1, d2]
dp = ndp
max_length = max(max_length, max(map(max, dp)))
return max_length


### 64. 853. Car Fleet

• Sort
• Medium
• O(NlogN)

sort cars by starting position. calculate the arrival times for each car as if no other car. Iterate the arrival time backward. Each peak is a leader in a fleet.

class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
cars = sorted(zip(position, speed))
arrival = [float(target - p) / s for p, s in cars]

num_fleets = 0
dt = 0
for t in reversed(arrival):
if t > dt:
num_fleets += 1
dt = t
return num_fleets


### 65. 1632. Rank Transform of a Matrix

• Sorting / Union Find
• Hard
• O(MNLogMN)

Go through the unique values in sorted order. Given a number, union locations into components, with edge be two location share same row index or column index. For each component, find the rank number by taking max for all points in component + 1 This rank finding can be done as a subsequent task after components finding or as a running update task during the components finding.

class Solution:
def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:
nrow, ncol = len(matrix), len(matrix[0])
rank = [0] * (nrow + ncol)  # column i will be indexed at nrow + i in this rank array

v2loc = defaultdict(list)
for r, c in product(range(nrow), range(ncol)):
v2loc[matrix[r][c]].append((r, c))

def find(i):
if parent[i] != i: parent[i] = find(parent[i])
return parent[i]

for num in sorted(v2loc.keys()):
parent = list(range(nrow + ncol))
new_rank = rank.copy()
for r, c in v2loc[num]:
r_rank_idx, c_rank_idx = find(r), find(nrow + c)
parent[r_rank_idx] = c_rank_idx
new_rank[c_rank_idx] = max(new_rank[r_rank_idx], new_rank[c_rank_idx])
for r, c in v2loc[num]:
rank[r] = rank[c + nrow] = matrix[r][c] = new_rank[find(r)] + 1
return matrix


### 66. 388. Longest Absolute File Path

• Stack
• Medium
• O(N)

Use stack to keep track of section length, len(stack) is the number of levels for the current path. the level can also be determined by count(“/t”) if not agree, pop.

class Solution:
def lengthLongestPath(self, input: str) -> int:
max_length = 0
stack = []

for section in input.split('\n'):
level = section.count('\t')
while len(stack) > level: stack.pop()
if not stack:
# only once the dir\n case
stack.append(len(section))
else:
# '\t' is considered to be length of 1! and add back a '/'
stack.append(len(section) - level + 1)
if '.' in section:
max_length = max(max_length, sum(stack))
return max_length


### 67. 410. Split Array Largest Sum

• Greedy / Binary Search
• Hard
• O(NlogS)

Can verify a guess in O(N) time. Apply binary search to find the max.

class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
l, h = max(nums), sum(nums)

def num_splits_no_larger_than(v):
num_subarrays = 0
accum = 0
for num in nums:
if accum + num > v:
num_subarrays += 1
accum = 0
accum += num
return num_subarrays + int(accum > 0)

while l < h:
m = l + (h - l) // 2
if num_splits_no_larger_than(m) > k:
l = m + 1
else:
h = m
return l


### 68. 679. 24 Game

• Permutation / Combination
• Hard
• O(N!)

GO through all permutation of 4 numbers, try all combinations of 3 operators, consider all 3 arrangements with 4 numbers and 3 operators, that is: op3(op2(op1(x, y), z), w) op3(w, op2(z, op1(x, y))) op3(op1(x, y), op2(z, w)) To check if we can get 24.

def div(a, b):
if b == 0: return 0
return a / b

class Solution:
def judgePoint24(self, nums):
for x, y, z, w in set(permutations(nums)):
for op1, op2, op3 in product([div, mul, add, sub], repeat=3):
r1 = round(op3(op2(op1(x, y), z), w), 6)
r2 = round(op3(w, op2(z, op1(x, y))), 6)
r3 = round(op3(op1(x, y), op2(z, w)), 6)
if 24 in [r1, r2, r3]: return True
return False


### 69. 981. Time Based Key-Value Store

• Design / Binary Search
• Medium
• O(logN)

~Map key to SortedDict with time be key. So query can be done by binary search on key-time.~

class TimeMap(defaultdict):
def __init__(self):
self.default_factory = list

def set(self, key: str, value: str, timestamp: int) -> None:
self[key].append((timestamp, value))

def get(self, key: str, timestamp: int) -> str:
if key not in self: return ""
i = bisect_right(self[key], (timestamp, chr(127)))
return self[key][i - 1][1] if i else ""

# class TimeMap(defaultdict):
#     def __init__(self):
#         self.default_factory = SortedDict

#     def set(self, key: str, value: str, timestamp: int) -> None:
#         self[key][timestamp] = value

#     def get(self, key: str, timestamp: int) -> str:
#         if key not in self: return ""
#         idx = self[key].bisect_right(timestamp)
#         if idx == 0: return ""
#         return self[key].peekitem(idx-1)[1]


### 70. 299. Bulls and Cows

• Array
• Medium
• O(N)

Two pass: count bull, when not bull count freq for each digit in secret and guess separately. Cows = sum(min_count(s.count(c), g.count(c)) for all c) One pass: count bull the same way. Keep a balance, secret + guess -. When guessed more than secret + 1

class Solution:
def two_pass(self, secret, guess):
bull, cow = 0, 0
freq_s, freq_g = [0] * 10, [0] * 10
for s, g in zip(secret, guess):
if s == g:
bull += 1
else:
freq_s[int(s)] += 1
freq_g[int(g)] += 1
for s, g in zip(freq_s, freq_g): cow += min(s, g)
return '{}A{}B'.format(bull, cow)

def one_pass(self, secret, guess):
bull, cow = 0, 0
balance = [0] * 10
for s, g in zip(secret, guess):
if s == g:
bull += 1
else:
balance[int(s)] += 1
balance[int(g)] -= 1
cow += int(balance[int(s)] <= 0)
cow += int(balance[int(g)] >= 0)
return '{}A{}B'.format(bull, cow)

getHint = two_pass # one_pass # two_pass


### 71. 158. Read N Characters Given read4 II - Call Multiple Times

• Design
• Hard
• O(N)

Use two integers indicated the number of chars read in buff and the index of the char to read in buff. For read, while haven’t read all, if buff is not exausted use it, otherwise fetch more on to buff reset the two integers. If fetch nothing or read enough don.

class Solution:
def __init__(self):
self.buf4 = [''] * 4
self.curr_used = 0

self.curr_used += 1
else:
self.curr_used = 0



### 72. 593. Valid Square

• Math / Geometry
• Medium
• O(1)

Calculate pairwise distances. Square will only have two lengths, side or diagonal. Or vector dot product = 0 means tangent / perpendicular. vector cross product = 0 means parallel. plus equal length.

class Solution:
def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
def length(p, q): return ((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2) ** .5
lengths = set()
pairs = ((p1, p2), (p1, p3), (p1, p4), (p2, p3), (p2, p4), (p3, p4))
for p, q in pairs: lengths.add(length(p, q))
return len(lengths) == 2 and 0 not in lengths


### 73. 1096. Brace Expansion II

• Stack
• Hard
• O(N!?)

Push { , and set(char) on to stack. Whenever encounter }, means we need to evaluate the operations. If stack[-2] is , we should set union stack[-1] and stack[-3] and replace all three with a single element the union. Finally replace the { by the last union Whenever the last two elements on stack are sets, we need to do cartesian product.

class Solution:
def braceExpansionII(self, expression: str) -> List[str]:
stack = []
for c in expression:
if c == '}':
union = set()
while stack[-2] == ',':
union.update(stack.pop())
stack.pop()
union.update(stack.pop())
stack[-1] = union # replacing { with union
elif c == "{" or c == ",":
stack.append(c)
else:
stack.append(set(c))

while len(stack) > 1 and isinstance(stack[-1], set) and isinstance(stack[-2], set):
V, U = stack.pop(), stack.pop()
stack.append(set(u + v for u in U for v in V))
return list(sorted(stack[-1]))


### 74. 715. Range Module

• Sorted Dictionary / TreeMap
• Hard
• O(NlogN)

Map left to right. Keep sorted order of key.

class RangeModule(SortedDict):
l, r = self.bisect(left), self.bisect(right)
# l == r means we have an entry open at left and next interval don't interact with new right
# or l == r = 0 means we don't have any interval to begin with

# check if previous interval should intersect this new one?
if l and self.peekitem(l-1)[1] >= left: l -= 1

if l != r: # delete encapsulated ranges
left, right = min(left, self.peekitem(l)[0]), max(right, self.peekitem(r-1)[1])
for _ in range(l, r): self.popitem(l)
self[left] = right

def queryRange(self, left, right):
l, r = self.bisect_right(left), self.bisect_right(right)
return not (l == 0 or self.peekitem(l - 1)[1] < right)

def removeRange(self, left, right):
l, r = self.bisect_right(left), self.bisect_right(right)

if l and self.peekitem(l-1)[1] >= left: l -= 1

if l != r:
new_left, new_right = min(left, self.peekitem(l)[0]), max(right, self.peekitem(r-1)[1])
for _ in range(l, r): self.popitem(l)
if new_left < left: self[new_left] = left
if right < new_right: self[right] = new_right


### 75. 1296. Divide Array in Sets of K Consecutive Numbers

• Greedy / Sorted HashMap / Sort + HashMap
• Medium
• O(NlogN)

Count number -> frequency. Start with minimal, build consecutive of k. Repeat until violation or used up all numbers.

class Solution:
def isPossibleDivide(self, nums, k):
counts = Counter(nums)
for x0 in sorted(counts.keys()):
if counts.get(x0, 0) >= 1:
cnt = counts[x0]
for i in range(k):
if counts.get(x0 + i, 0) < cnt:  return False
counts[x0 + i] -= cnt
return True


### 76. 1153. String Transforms Into Another String

• Greedy / Hash
• Hard
• O(N)

No character in str1 can be mapped to multiple characters in str2. str2 can’t have full alphabet, otherwise, there is no wiggle room for str1 to transform into str2.

class Solution:
def canConvert(self, str1: str, str2: str) -> bool:
if str1 == str2: return True
m = dict()
for c1, c2 in zip(str1,  str2):
m.setdefault(c1, c2)
if m[c1] != c2: return False
return len(set(str2)) < 26


### 77. 660. Remove 9

• Math
• Hard
• O(N)

The number is nth number as if base 9. Remove a single digit will be basically the same, just need to map digits. For example if we remove 7, we treat it as if it is remove 9, in the result, just turn 7 into 8, 8 into 9.

class Solution:
def newInteger(self, n: int) -> int:
result = 0
base = 1
while n:
n, remainder = divmod(n, 9)
result += remainder * base
base *= 10
return result


### 78. 642. Design Search Autocomplete System

• Trie
• Hard
• O(Vocab)
class TrieNode(defaultdict):
def __init__(self):
self.default_factory = TrieNode
self.sentence_ids = set()

class AutocompleteSystem:
def __init__(self, sentences: List[str], times: List[int]):
self.root = TrieNode()
self.sentence_freq = dict()
self.sentence_idx = dict()
self.idx_to_sentence = dict()

for sentence, time in zip(sentences, times):

self.stream = []
self.curr = self.root

if sentence in self.sentence_idx:
idx = self.sentence_idx[sentence]
else:
idx = len(self.sentence_idx) + 1
self.idx_to_sentence[idx] = sentence
self.sentence_idx[sentence] = idx
node = self.root
for c in sentence:
node = node[c]

self.sentence_freq[idx] = self.sentence_freq.get(idx, 0) + freq

def input(self, c: str) -> List[str]:
if c == "#":
sentence = "".join(self.stream)
self.stream.clear()
self.curr = self.root
return []

self.stream.append(c)

if self.curr is None or c not in self.curr:
self.curr = None
return []

self.curr = self.curr[c]

matched = nsmallest(3, self.curr.sentence_ids, key=lambda x: (-self.sentence_freq[x], self.idx_to_sentence[x]))
result = [self.idx_to_sentence[idx] for idx in matched]
return result


### 79. 1592. Rearrange Spaces Between Words

• Array
• Easy / Hard
• O(N)

Regular spaces and trailing spaces are divmod(# total spaces, # words - 1). Split and reform is Easy. If given char array and asking inplace swaps, we shift all words to one side leave 1 space in between, and then work from opposite side shift words with proper spaces.

class Solution:
def reorderSpaces(self, text: str) -> str:
num_spaces = text.count(" ")
words = text.split()
num_words = len(words)
if num_words == 1: return words[0] + " " * num_spaces

space, trailing = divmod(num_spaces, num_words - 1)
result = []
for word in words:
result.append(word)
result.append(" " * space)
result[-1] = " " * trailing
return "".join(result)

def l_shift(A, l, s, e):
"""shift A[s:e] to A[l:l + e-s]"""
stride = e - s
i, j = l, s
while j < e:
A[i], A[j] = A[j], A[i]
i += 1 ; j += 1
return l + stride + 1, e + 1

def r_shift(A, r, s, e):
"""shift A[s:e] to A[r-e-s:r]"""
stride = e - s
i, j = r, e
while j > s:
A[i], A[j] = A[j], A[i]
j -= 1 ; i -= 1
return r - stride, s

class Solution:
def reorderSpaces(self, text: str) -> str:
A = list(text)
n = len(A)

# shift words to left, leave one space in between count number of spaces
l = s = 0
num_words = 0
while s < n:
if A[s] == " ": s += 1; continue
num_words += 1
e = s
while e <n and A[e] != ' ': e += 1
l, s = l_shift(A, l, s, e)

if num_words == 1: return "".join(A)
num_spaces = A.count(" ")
space, trailing = divmod(num_spaces, num_words - 1)

# work from back ward
r = n - 1 - trailing
e = n - 1
while e > 0:
if A[e] == " ": e -= 1; continue
s = e
while s >=0 and A[s] != ' ': s -= 1
r, e = r_shift(A, r, s, e)
r -= space
return "".join(A)


### 80. 1776. Car Fleet II

• Monotonic Stack
• Hard
• O(N)

Given a car, it will only see the car on its right. Only the slowest car matters. Keep a monotonic stack of cars decreasing in speed. E -> A -> B -> C if A is slower than B, from E’s perspective, A is all that matters. if A is faster than B and crashes B before E can catch up with A. Then from E’s perspective, A is equivalent to B.

class Solution:
def getCollisionTimes(self, A: List[List[int]]) -> List[float]:
# A: tuple[pos: int, speed: int]
stack = []
n = len(A)
res = [-1] * n

for i in reversed(range(n)):
p, s = A[i]
# has car on right  right car is faster |  time to catch up with right car                time right car crashed => thus will not catch up
while stack and (s <= A[stack[-1]][1] or (A[stack[-1]][0] - p) / (s - A[stack[-1]][1]) >= res[stack[-1]] > 0): stack.pop()
# slow car on the right and this car will catch right car before rigtht car crash
if stack: res[i] = (A[stack[-1]][0] - p) / (s - A[stack[-1]][1])
stack.append(i)
return res


### 81. 837. New 21 Game

• DP / Math / Sliding Window
• Medium
• O(N)
# 6 sided dice
# pr(i) probabiliy see total i points during sequence of draws
# pr(0) = 1
# pr(1) = 1/6 -> roll once and a one
# pr(2) = 1/6 + 1/6 * 1/6 -> roll a two or from a single roll of 1 roll another 1
# pr(3) = 1/6 + 1/6 * 1/6 + 1/6 * 1/6 * 1/6 -> (0,3; 2,1; 1,2)
# pr(i) = sum(pr(i-6), pr(i-5), pr(i-4), ..., pr(i-1)) * 1/6
# true before we hit k


Pr(i) probability see total of i points during all sequences: Pr(1) = 1/w, Pr(2) = 1 / w(draw a 2) + Pr(1) * 1 / w (from a 1 draw then draw another 1)
Generally: Pr(i) = 1 / w * Sum { Pr(j) for j in range(max(0, i-w), min(i, k)) } use a sliding window for this sum.

class Solution:
#     def new21Game(self, n: int, k: int, maxPts: int) -> float:
#         if k == 0 or n >= k + maxPts: return 1

#         pr = [1.] + [0.] * n
#         for i in range(1, n + 1):
#             pr[i] = sum(pr[j]
#                         for j in range(max(0, i-maxPts), min(i, k))
#                        ) * 1 / maxPts
#         return sum(pr[k:])  # TLE since we are calculating the window from strach each time.

def new21Game(self, n: int, k: int, maxPts: int) -> float:
if k == 0 or n >= k + maxPts: return 1
pr = [1.] + [0.] * n
prob = 0
for i in range(1, n + 1):
if i > maxPts: prob -= pr[i - maxPts - 1]
if i <= k:     prob += pr[i - 1]
pr[i] = prob * 1 / maxPts
return sum(pr[k:])


### 82. 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

• Prefix Sum
• Medium
• O(N)
class Solution:
def minSumOfLengths(self, arr: List[int], target: int) -> int:#
n = len(arr)
prefix_sum = {0: -1}
prefix_shortest = [n + 1] * len(arr)
shortest = n + 1
min_sum_length = n + 1
for r, accum in enumerate(accumulate(arr)):
if accum - target in prefix_sum:
l = prefix_sum[accum - target]
if l > -1:
min_sum_length = min(min_sum_length, r - l + prefix_shortest[l])
shortest = min(shortest, r - l)
prefix_shortest[r] = shortest
prefix_sum[accum] = r
return -1 if min_sum_length == n + 1 else min_sum_length


### 83. 1254. Number of Closed Islands

• DFS
• Medium
• O(MN)
class Solution:
def closedIsland(self, grid):
nrow, ncol = len(grid), len(grid[0])
visited = set()

def dfs(r, c):
srounded = True
stack = [(r, c)]
while stack:
r, c = stack.pop()
if (r, c) in visited: continue
if r == 0 or c == 0 or r == nrow - 1 or c == ncol - 1:
srounded = False
for nr, nc in [(r,c-1), (r,c+1), (r-1, c), (r+1, c)]:
if nrow > nr >= 0 <= nc < ncol and grid[nr][nc] == 0:
stack.append((nr, nc))
return srounded

total = 0
for r in range(nrow):
for c in range(ncol):
if (r, c) in visited or grid[r][c] == 1: continue
total += dfs(r, c)


### 84. 732. My Calendar III

• SortedList
• Hard
• O(N)

Use a sorted list to store both end points for event annotated with +1 and -1. Scan the timepoints with running sum of the annotation. Max con-current event is the max of the running sum.

class MyCalendarThree(SortedList):
def book(self, start: int, end: int) -> int:
self.update([(start, 1), (end, -1)])
max_booking = 0
bookings = 0
for time, event in self:
bookings += event
max_booking = max(max_booking, bookings)
return max_booking


### 85. 1882. Process Tasks Using Servers

• Priority Queue
• Medium
• O((M+N)logN)
class Solution:
busy = []
free = [(wt, i) for i, wt in enumerate(servers)]
heapify(free)

result = []
while busy and busy[0][0] == t:
_, wt, i = heappop(busy)
heappush(free, (wt, i))
if free: wt, i = heappop(free)
else: t, wt, i = heappop(busy)
result.append(i)
return result


### 86. 1728. Cat and Mouse II

• DFS + Memoization
• Hard
• O((MN) ^ 3 * (M + N))
class Solution:
def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
nrow, ncol = len(grid), len(grid[0])
for r, c in product(range(nrow), range(ncol)):
if grid[r][c] == "F": food = (r, c)
if grid[r][c] == "C": cat = (r, c)
if grid[r][c] == "M": mouse = (r, c)

threshold = nrow * ncol * 2                 # most amount of turns for cat to get to food.

@cache
def dfs(cat, mouse, turn) -> bool: # whether mouse can win
if cat == food or cat == mouse or turn >= threshold: return False  # mouse lose

if mouse == food: return True                                      # mouse win

if turn & 1: (r, c), jump = cat, catJump
else:        (r, c), jump = mouse, mouseJump

for dr, dc in (-1, 0), (1, 0), (0, -1), (0, 1):
for step in range(1, jump + 1):
nr, nc = r + dr * step, c + dc * step
if not (nrow > nr >= 0 <= nc < ncol) or grid[nr][nc] == "#": # can't jump any further
break

if turn & 1: # cat move
if not dfs((nr, nc), mouse, turn + 1): # and cat can win
return False                                      # mouse lose
else:        # mouse move
if dfs(cat, (nr, nc), turn + 1): # and mouse can win
return True                                       # mouse win

if turn & 1 and not dfs(cat, mouse, turn + 1): # cat stay and win
return False

return turn & 1                                                  # cat can't win

return dfs(cat, mouse, 0)


### 87. 284. Peeking Iterator

• Design
• Medium
• O(1)

Cache next value. When called next or hasNext, check if cache exist or not first. When next, clear cache. In case the underlying iterator can return Null pointers, use a boolean flag to indicate whether we have cache.

class PeekingIterator:
def __init__(self, iterator):
self.iterator = iterator
self.peeked = False
self.peeked_value = None

def peek(self):
if not self.peeked:
self.peeked = True
self.peeked_value = self.iterator.next()
return self.peeked_value

def next(self):
if self.peeked:
val = self.peeked_value
self.peeked = False
self.peeked_value = None
else:
val = self.iterator.next()
return val

def hasNext(self):
return self.peeked or self.iterator.hasNext()


### 88. 564. Find the Closest Palindrome

• Array
• Hard
• O(N^2)

Break problemn into two steps, candidate generation and ranking!

class Solution:
def nearestPalindromic(self, S: str) -> str:
K = len(S)
# special cases 1001 999, 9999, 10001 which
# S = 10 the answer should be 9
# S = 99 the answer should be 101
# S = 44 the answer should be 33
# S = 100 the answer should be 99
# S = 999 the answer should be 1001
candidates = ["9" * K, "9" * (K-1), "1" + "0" * (K-1) + "1", "1" + "0" * (K-2) + "1"]
candidates = [cand for cand in candidates if cand]

prefix = S[:(K+1)//2]
P = int(prefix)

for start in map(str, (P-1, P, P+1)):
candidates.append(start + (start[:-1] if K % 2 else start)[::-1])

def delta(x): return abs(int(S) - int(x))

ans = None
for cand in candidates:
if cand != S and not cand.startswith('00'):
if (ans is None or delta(cand) < delta(ans) or
delta(cand) == delta(ans) and int(cand) < int(ans)):
ans = cand
return ans


### 89. 1088. Confusing Number II

• DFS
• Medium
• O(N)

Enumerate over all possibilities one digit at a time.

class Solution:
def confusingNumberII(self, n: int) -> int:
mapping = {0: 0, 1: 1, 6: 9, 8: 8, 9: 6}

def dfs(num, rotated, base):
result = int(num != rotated)
new_base = base * 10
for d, rd in mapping.items():
new_num = num * 10 + d
new_rotated = rd * base + rotated
if new_num > n or new_num == 0: continue
result += dfs(new_num, new_rotated, new_base)
return result
return dfs(0, 0, 1)


### 90. 818. Race Car

• DP / Bit Manipulation
• Hard
• O(NlogN)

Think of fulfilling the bits in the binary representation of t. Either overshot and do the complement. Or clear the second most significant bits. T = 1101 if overshoot we do 1111 and reverse do the complement 10 if clear most significant bit we can do 111 or 110 or 100 with 3 4 5 steps.

# t = 57         111001  bit_length = 6
# 1 overshoot and reverse
# if overshoot   111111   we get to this with 6A
#    then add 1 to turn back now we need to do the 111111 - 111001 = 110 in new direction
# 2 clear some bits
# 11111          101001                   m = 4
# 11110          100001                   m = 3
# 11100          011101                   m = 2
# 11000          011011                   m = 1
# 10000          011010                   m = 0

class Solution:
def racecar(self, t: int) -> int:
dp = {0: 0}
for i in range(t.bit_length() + 2):
dp[(1 << i) - 1] = i

def dfs(t):
if t in dp: return dp[t]

n = t.bit_length()
# over shoot then reverse the course
dp[t] = dfs((1 << n) - 1 - t) + n + 1

# clear most significant bit then back ward by 1 bit
# try all bit pos
for m in range(n - 1):
dp[t] = min(dp[t], dfs(t - (1 << n - 1) + (1 << m)) + n + m + 1)
return dp[t]

return dfs(t)


### 91. 200. Number of Islands

• DFS / BFS
• Medium
• O(MN)

Count the number of connected components.

class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
nrow, ncol = len(grid), len(grid[0])

visited = set()
num_islands = 0

def dfs(r, c):
stack = [(r, c)]
while stack:
r, c = stack.pop()
if (r, c) in visited: continue
for nr, nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
if nrow > nr >= 0 <= nc < ncol and grid[nr][nc] == "1":
stack.append((nr, nc))

for r in range(nrow):
for c in range(ncol):
if grid[r][c] == "0" or (r,c) in visited: continue
num_islands += 1
dfs(r, c)
return num_islands


### 92. 354. Russian Doll Envelopes

• LIS
• Hard
• O(NlogN)

If we have distinct widths for envelopes, sort by widths, then problem reduced to LIS. With duplicated widths, if within the same widths, we sort by heights in reverse, it will still be a LIS problem. Thus sort by (w, -h) then LIS.

class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes.sort(key = lambda x: (x[0], -x[1]))
dolls = []
for w, h in envelopes:
i = bisect.bisect_left(dolls, h)
if i == len(dolls): dolls.append(h)
else:               dolls[i] = h
return len(dolls)


### 93. 1499. Max Value of Equation

• Sliding Window / Deque
• Hard
• O(N)

Note i <= j, equation evaluates to yj + xj + yi - xi => problem is finding max(yi - xi) in window of length k(with at least 2 points). Maintain a monotonic increasing deque. With elements of tuple(yi - xi, xi) popleft as window moves right.

class Solution:
def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
q = deque()
res = -float('inf')
for x2, y2 in points:
while q and q[0][1] < x2 - k: q.popleft()
if q: res = max(res, q[0][0] + y2 + x2)
while q and q[-1][0] <= y2 - x2: q.pop()
q.append([y2 - x2, x2])
return res


### 94. 305. Number of Islands II

• Union Find
• Hard
• O(MN)

Dynamic connectivity -> Union Find.

class UnionFind(object):
def __init__(self):
self.parents = dict()
self.sizes = dict()
self.n = 0

def __contains__(self, key):
return key in self.parents

def insert(self, r, c):
if self.__contains__((r,c)): return
self.parents[(r, c)] = (r, c)
self.sizes[(r, c)] = 1
self.n += 1

def find(self, i):
while i != self.parents[i]:
self.parents[i] = self.find(self.parents[i])
i = self.parents[i]
return i

def union(self, p, q):
root_p, root_q = map(self.find, (p, q))
if root_p == root_q: return
small, big = sorted([root_p, root_q], key=lambda x: self.sizes[x])
self.parents[small] = big
self.sizes[big] += self.sizes[small]
self.n -= 1

class Solution:
def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
uf = UnionFind()
num_islands = []
for r, c in positions:
uf.insert(r, c)
for rr, cc in [(r-1,c), (r+1,c), (r,c-1), (r,c+1)]:
if (rr, cc) not in uf: continue
uf.union((r,c), (rr,cc))
num_islands.append(uf.n)
return num_islands


### 95. 1275. Find Winner on a Tic Tac Toe Game

• Array / Design
• Easy
• O(MN)
class Player:
def __init__(self, name='', n=3):
self.name = name
self.n = n
self.rows = [0] * n
self.cols = [0] * n
self.main_diag = 0
self.anti_diag = 0

def move(self, r, c):
self.rows[r] += 1
self.cols[c] += 1
if r == c: self.main_diag += 1
if r + c  + 1 == self.n: self.anti_diag += 1
return self.n in [self.rows[r], self.cols[c], self.main_diag, self.anti_diag]

class Solution:
def tictactoe(self, moves: List[List[int]], n=3) -> str:
players = [Player(name, n) for name in ["A", "B"]]
n_players = len(players)
for i, (r, c) in enumerate(moves):
turn = i % n_players
player = players[turn]
if player.move(r, c): return player.name
return 'Pending' if len(moves) != n * n else 'Draw'


### 96. 835. Image Overlap

• Sliding Window / HashMap
• Medium
• O(N^4)

Can count (x2-x1, y2-y1) if A[x1][y1] == B[x2][y2] == 1. i.e. the shifts that will cause a match. Or do sliding window convolution, which the code will be messy.

class Solution:
def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
n = len(A)

def shift_overlap(A, dx, dy, B):
lc, rc = 0, 0
for rb, ra in enumerate(range(dy, n)):
for cb, ca in enumerate(range(dx, n)):
if A[ra][ca] == B[rb][cb] == 1: lc += 1
if A[ra][cb] == B[rb][ca] == 1: rc += 1
return max(lc, rc)

max_overlaps = 0

for dx, dy in product(range(n), range(n)):
max_overlaps = max(
max_overlaps,
shift_overlap(A, dx, dy, B),
shift_overlap(B, dx, dy, A)
)

return max_overlaps

def largestOverlap(self, A, B):
n = len(A)
max_overlaps = 0
shifts = defaultdict(int)

for r1, c1 in product(range(n), range(n)):
if A[r1][c1] == 0: continue
for r2, c2 in product(range(n), range(n)):
if B[r2][c2] == 0: continue
shifts[r2-r1,c2-c1] += 1
return max(shifts.values(), default = 0)


### 97. 975. Odd Even Jump

• Sorting / Stack / DP
• Hard
• O(NlogN)

Use a monotonic stack to find the next lower / larger index. From the end location backtrack by alternating between the next_lower, next_higher arrays.

class Solution:
def oddEvenJumps(self, arr: List[int]) -> int:
n = len(arr)
next_higher, next_lower = [0] * n, [0] * n

stack = []
for a, i in sorted([a, i] for i, a in enumerate(arr)):
while stack and stack[-1] < i:
next_higher[stack.pop()] = i
stack.append(i)

stack = []
for a, i in sorted([-a, i] for i, a in enumerate(arr)):
while stack and stack[-1] < i:
next_lower[stack.pop()] = i
stack.append(i)

# backtrack
odd, even = [0] * n, [0] * n
odd[-1] = even[-1] = 1
for i in reversed(range(n - 1)):
# if we are at loc i and it is odd turn, can we jump and reach the end?
if next_higher[i]: odd[i] = even[next_higher[i]]
# if we are at loc i and it is even turn, can we jump and reach the end?
if next_lower[i]: even[i] = odd[next_lower[i]]



### 98. 307. Range Sum Query - Mutable

• Segment Tree
• Medium
• O(logN)
class TreeNode:
def __init__(self, val=None, parent=None, left=None, right=None, start=None, end=None):
self.val = val
self.parent = parent
self.left = left
self.right = right
self.start = start
self.end = end

def __repr__(self):
print('val {} start {} end {}'.format(self.val, self.start, self.end))

class SegmentTree:
def __init__(self, values):
self.build_tree(values)

def build_tree(self, values):
nodes = [TreeNode(val=val, start=i, end=i) for i, val in enumerate(values)]
self.leaves = nodes
while len(nodes) != 1:
parents = []
for l, r in zip_longest(nodes[::2], nodes[1::2], fillvalue=None):
val = l.val if not r else l.val + r.val
end = l.end if not r else r.end
parent = TreeNode(val, left=l, right=r, start=l.start, end=end)
l.parent = parent
if r: r.parent = parent
parents.append(parent)
nodes = parents
self.root = nodes[0]

def update(self, index, val):
leaf = self.leaves[index]
diff = val - leaf.val
node = leaf
while node:
node.val += diff
node = node.parent

def query(self, left, right):
l = self.leaves[left]
r = self.leaves[right]
if l == r: return l.val

total = l.val + r.val
while l.parent != r.parent:
if l == l.parent.left:
total += l.parent.right.val
if r == r.parent.right:
total += r.parent.left.val
l = l.parent
r = r.parent

class NumArray(SegmentTree):
def __init__(self, nums: List[int]):
super().__init__(nums)

def update(self, index: int, val: int) -> None:
super().update(index, val)

def sumRange(self, left: int, right: int) -> int:
return super().query(left, right)


### 99. 568. Maximum Vacation Days

• DP
• Hard
• O(N^2* K)

DP[k][j] is the max number of vaction days, when we end our kth week at city j DP[k][j] = max(dp[k-1][i] + days[i][k] if we can reach j from i, or i is j ie stay)

class Solution:
def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
n, k = len(days), len(days[0])
dp = [[0] * n for _ in range(k+1)]
dp[0][0] = 0

for t, i in product(range(k), range(n)):
for j, has_flight in enumerate(flights[i]):
if not (has_flight or i == j): continue
dp[t+1][j] = max(dp[t+1][j], dp[t][i] + days[j][t])
return max(dp[-1])


### 100. 253. Meeting Rooms II

• Priority Queue
• Medium
• O(NlogN)

Sort meetings by starting time. Push end time onto a min priority queue. Going through the rest of meetings, if priority is not empty and the top item(end time) is less than the starting time, that means a previous occupied room can be used, pop it off the priority queue and push on the new end time. The size of the priority queue is the max number of rooms needed. Follow up: to out put each room’s schedule. Push (endtime, roomid) on the queue, when we reuse room, use the same roomid, when we ran out of rooms, use size(queue) as new room’s id. Use a HashMap mapping room_id to its events.

class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
intervals.sort()
occupied = []
max_occupation = 0
meeting_ids = defaultdict(list)
for start_time, end_time in intervals:
if occupied and occupied[0][0] <= start_time: _, room_id = heapq.heappop(occupied)
else:                                         room_id = len(occupied)
meeting_ids[room_id].append((start_time, end_time))
heapq.heappush(occupied, (end_time, room_id))
max_occupation = max(max_occupation, len(occupied))
return max_occupation


### 101. 1226. The Dining Philosophers

• Concurrency
• Medium
• O(1)

When a philosopher wants to eat, lock the two folks at his left and right.

from threading import Semaphore

class DiningPhilosophers:
def __init__(self):
self.folks = [Semaphore(1) for _ in range(5)]

# call the functions directly to execute, for example, eat()
def wantsToEat(self,
philosopher: int,
pickLeftFork: 'Callable[[], None]',
pickRightFork: 'Callable[[], None]',
eat: 'Callable[[], None]',
putLeftFork: 'Callable[[], None]',
putRightFork: 'Callable[[], None]') -> None:

left, right = philosopher, (philosopher - 1) % 5
if philosopher == 0: left, right = right, left
with self.folks[left], self.folks[right]:
pickLeftFork(); pickRightFork(); eat(); putLeftFork(); putRightFork()


### 102. 465. Optimal Account Balancing

• DFS / Bit Mask DP
• Hard
• O(N2^N)

Start with everyone’s end balance. Try to cancel the debt in one trans, if we can’t, then give money from pos to neg and keep going.

class Solution:
def minTransfers(self, transactions: List[List[int]]) -> int:
counter = defaultdict(int)
for f, t, m in transactions:
counter[f] -= m
counter[t] += m

balances = tuple([v for v in counter.values() if v])

@cache
def dfs(state):
if not state:     return 0

for i in range(1, len(state)):
if state[i] == -state[0]:  return 1 + dfs(state[1:i] + state[i+1:])

ret = []
for i in range(1, len(state)):
if state[i] * state[0] < 0: ret.append(dfs(state[1:i] + tuple([state[i] + state[0]]) + state[i+1:]))
return 1 + min(ret)

return dfs(balances)


### 103. 846. Hand of Straights

• Greedy / Sorted HashMap / Sort + HashMap
• Medium
• O(NlogM)
class Solution:
def isNStraightHand(self, hand: List[int], k: int) -> bool:
counts = Counter(hand)
for x0 in sorted(counts.keys()):
if counts.get(x0, 0) >= 1:
cnt = counts[x0]
for i in range(k):
if counts.get(x0 + i, 0) < cnt:  return False
counts[x0 + i] -= cnt
return True


### 104. 1244. Design A Leaderboard

• HashMap + SortedList
• Medium
• O(logN) for all operations
class Leaderboard:
def __init__(self):
self.player_score = dict()
self.scores = SortedList()

if playerId in self.player_score:
old_score = self.player_score[playerId]
self.scores.remove(old_score)
score += old_score
self.player_score[playerId] = score

def top(self, K):
return sum(self.scores[-K:])  # logN + K

def reset(self, playerId):
self.player_score.pop(playerId)


### 105. 1263. Minimum Moves to Move a Box to Their Target Location

• Shortest Path? Priority Queue BFS
• Hard
• O(MNLog(MN))
class Solution:
def minPushBox(self, grid: List[List[str]]) -> int:
nrow, ncol = len(grid), len(grid[0])

floor = set()
for r, c in product(range(nrow), range(ncol)):
cell = grid[r][c]
if cell == "#": continue
if cell == "S": spawn = r, c
if cell == "B": box = r, c
if cell == "T": target = r, c

pq = [(0, *spawn, *box)]
seen = set()
while pq:
steps, pr_1, pc_1, br_1, bc_1 = heappop(pq)
box_loc = (br_1, bc_1)
player_loc = (pr_1, pc_1)
if box_loc== target: return steps
if (*player_loc, *box_loc) in seen: continue

for dr, dc in (-1, 0), (1, 0), (0, -1), (0, 1):
player_loc_new = pr_2, pc_2 = pr_1 + dr, pc_1 + dc
box_loc_new = br_2, bc_2 = br_1 + dr, bc_1 + dc

if player_loc_new == box_loc and box_loc_new in floor:
heappush(pq, (steps + 1, *player_loc_new, *box_loc_new))
elif player_loc_new in floor and player_loc_new != box_loc:
heappush(pq, (steps, *player_loc_new, *box_loc))

return -1


### 106. 1948. Delete Duplicate Folders in System

• Trie / DFS / Backtrack
• Hard
• O(MN)

step 1 Use trie to store the direcotries, argument each node with a indicator variable to_delete. step 2 Run dfs and build postorder serialization of the sub directory structure and hash the structure to trie node(s). step 3 Find the sub directory structure that has more than one trie node, ie duplicated folders, flag the trie nodes to be deleted. step 4 Do another round of dfs/backtrack and to collect the final path structure.

class TrieNode(defaultdict):
def __init__(self):
self.dl = False
self.default_factory = TrieNode

def __hash__(self): return id(self)

class Solution:
def deleteDuplicateFolder(self, paths):
root = TrieNode()
for path in sorted(paths):
node = root
for d in path: node = node[d]

pattern = defaultdict(list)

def dfs(node):
key = "(" + ''.join(c + dfs(nd) for c, nd in node.items()) + ")"
if key != "()": pattern[key].append(node)
return key

dfs(root)
for nodes in pattern.values():
if len(nodes) > 1:
for i in nodes: i.dl = True

result = []
def backtrack(path, node):
for c, nd in node.items():
if nd.dl: continue
path.append(c)
backtrack(path, nd)
path.pop()
if path: result.append(path.copy())

backtrack([], root)
return result


### 107. 1138. Alphabet Board Path

• Array
• Medium
• O(N)
class Solution:
def alphabetBoardPath(self, target: str) -> str:
to_loc = lambda c: divmod(ord(c) - ord('a'), 5)

@cache
def get_instructions(r, c, nr, nc):
v_moves = 'D' * (nr - r) if nr > r else 'U' * (r - nr)
h_moves = 'R' * (nc - c) if nc > c else 'L' * (c - nc)
if (r, c) == (5, 0): return [v_moves, h_moves]
return [h_moves, v_moves]

instructions = []
r, c = 0, 0
for char in target:
nr, nc = to_loc(char)
instructions.extend(get_instructions(r, c, nr, nc))
instructions.append("!")
r, c = nr, nc
return "".join(instructions)


### 108. 1. Two Sum

• HashMap
• Easy
• O(N)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
mapping = dict()  # number -> index
for idx, num in enumerate(nums):
complement = target - num
if complement in mapping: return [idx, mapping[complement]]
mapping[num] = idx


### 109. 1514. Path with Maximum Probability

• Priority Queue
• Medium
• O(V+E)
class PQItem:
def __init__(self, priority, item):
self.priority = priority
self.item = item

def __lt__(self, other): return self.priority > other.priority

class Solution:
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
for (f, t), p in zip(edges, succProb):

# visited node
visited = [False for _ in range(n)]

max_heap = [PQItem(1, start)]

# search
while max_heap:
pqitem = heappop(max_heap)
prob, node = pqitem.priority, pqitem.item
if node == end: return prob

visited[node] = True
if visited[nex_node]: continue
return 0


### 110. 1642. Furthest Building You Can Reach

• Priority Queue / Greedy
• Medium
• O(NlogN)

Use ladder when we have not enough bricks, and recover bricks amounts equal to a single climb up from past.

class PQItem:
def __init__(self, priority): self.priority = priority
def __lt__(self, other): return self.priority > other.priority

class Solution:
def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
pq = []
for i in range(1, len(heights)):
if (diff := heights[i] - heights[i - 1]) > 0:
bricks -= diff
heappush(pq, PQItem(diff))
if bricks < 0:
bricks += heappop(pq).priority
if bricks < 0 or ladders < 0: return i - 1
return len(heights) - 1


### 111. 2103. Rings and Rods

• Bit
• Easy
• O(N)

Use bit mask to indicate color, use a integer indicating the state for each rod. Use or operatior to update state.

class Solution:
def countPoints(self, rings: str) -> int:
n = len(rings) // 2
rod_color = [0] * 10
color_to_flag = {'R': 1, 'G': 2, 'B': 4}

for i in range(0, 2 * n, 2):
color, rod = rings[i], rings[i + 1]
rod_color[int(rod)] |= color_to_flag[color]

return rod_color.count(7)


### 112. 871. Minimum Number of Refueling Stops

• Priority Queue / Greedy
• Hard
• O(NlogN)

Use priority to keep track of past gas stations, where the priority is higher capacity(thus we fill up as few times as possible). Follow the stations, whenever we find ran out of fuel, go back to priority queue to see if we filled up before can we get here. If not we fail, otherwise add new station to queue and move forward.

class Solution:
def minRefuelStops(self, target: int, start_fuel: int, stations: List[List[int]]) -> int:
class Node:
def __init__(self, val): self.val = val
def __lt__(self, other): return self.val > other.val

stations.append([target, float('inf')])
tank = start_fuel
num_refills = 0
prev_location = 0
pq = []

for location, capacity in stations:
tank -= location - prev_location
while pq and tank < 0:  # must refuel in past
tank += heapq.heappop(pq).val
num_refills += 1

if tank < 0: return -1
heapq.heappush(pq, Node(capacity))
prev_location = location
return num_refills


### 113. 920. Number of Music Playlists

• DP
• Hard
• O(MN)
S: dp[i][j] # number of unique playlists of length i with j songs
# use a new song.              # reuse a song but not the most recent used k
R: dp[i][j] = dp[i-1][j-1] * (n - (j - 1)) + dp[i-1][j] * max(j-k, 0)
T: i, j
B: dp[0][0] = 1
O: dp[0][0]
T: O(goal * n)

class Solution:
def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
M = 1_000_000_007
dp = [[0] * (n + 1) for _ in range(goal + 1)]
dp[0][0] = 1
for i in range(1, goal + 1):
for j in range(1, n + 1):
dp[i][j] = (dp[i-1][j-1] * (n - (j - 1)) + dp[i-1][j] * max(j-k, 0)) % M
return dp[-1][-1]


### 114. 269. Alien Dictionary

• Topological Sort
• Hard
• O(VE)

Build graph. DFS (with cycle detection) collect postorder. Or BFS en queue when in_degree decreased to 0.

class Solution:
def alienOrder(self, words: List[str], method='dfs') -> str:
# preprocessing
nodes = reduce(set.union, map(set, words))  # char set
out_edges = defaultdict(list)
in_degrees = defaultdict(int)
for w1, w2 in zip(words, words[1:]):
for c1, c2 in zip(w1, w2):
if c1 == c2: continue
in_degrees[c2] += 1
out_edges[c1].append(c2)
break
else:
if len(w1) > len(w2): return ""

ordering = self.topsort_bfs(nodes, out_edges, in_degrees) if method == 'bfs' else self.topsort_dfs(nodes, out_edges)
return ''.join(ordering)

@staticmethod
def topsort_bfs(nodes, out_edges, in_degrees):
ordering = deque()
queue = deque(nodes.difference(in_degrees.keys()))
while queue:
node = queue.popleft()
ordering.append(node)
for nxt_node in out_edges[node]:
in_degrees[nxt_node] -= 1
if not in_degrees[nxt_node]: queue.append(nxt_node)
return ordering if len(ordering) == len(nodes) else []

@staticmethod
def topsort_dfs(nodes, out_edges):
ordering = deque()
visited = set()
path = set()

def dfs(node): # return True if has cycle
if node in visited: return False
if node in path: return True

for nxt_node in out_edges[node]:
if dfs(nxt_node): return True
ordering.appendleft(node)
return False

while nodes:
node = nodes.pop()
has_cycle = dfs(node)
if has_cycle: return ""
else: nodes = nodes.difference(visited)
return ordering


### 115. 850. Rectangle Area II

• Sweep Line
• Hard
• O(N^2) -> segment tree can improve this to O(NlogN)
class Solution:
def rectangleArea(self, rectangles: List[List[int]]) -> int:
MOD = 10 ** 9 +7
INT_MIN = - 2 ** 32

# convert list of rectangles to events
events = [] # tuple of x, event (open/close), y1, y2
for x1, y1, x2, y2 in rectangles:
events.append([x1, 0, y1, y2])
events.append([x2, 1, y1, y2])
events.sort()

# helper function to do total interval length via sweep line
def gain_area(width):
area = 0
prev = INT_MIN
for lo, hi in open_intervals:
prev = max(prev, lo)
area += max(0, (hi - prev) * width)
prev = max(hi, prev)
return area

# sweep line to realize area
# O(N^2)
area = 0
x1 = INT_MIN
open_intervals = SortedList()
for event in events: # O(N)
x2, close, y1, y2 = event
area += gain_area(x2 - x1)
if close:
open_intervals.remove((y1,y2))
else:
x1 = x2
return area % MOD


### 116. 886. Possible Bipartition

• BFS / DFS
• Medium
• O(V + E)

Component building and find conflicts.

class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
assignments = dict()
for a, b in dislikes:

for i in range(1, n+1):
if i in assignments: continue
assignments[i] = 0
dq = deque([i])
while dq:
a = dq.pop() # a = queue.popleft()
if b not in assignments:
assignments[b] = 1 ^ assignments[a]
dq.append(b)
if assignments[b] == assignments[a]: return False
return True


### 117. 778. Swim in Rising Water

• Union Find
• Hard
• O(N^2\alpha(N^2))

Iterate over cells sorting by time. Union find cell with neighboring cells that were already in set. Check if top left and bottom right is connected or not.

class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
n = len(grid)
t_to_loc = {grid[r][c]: (r,c) for r in range(n) for c in range(n)}
uf = UnionFind()
for t in range(n**2):
r, c = t_to_loc[t]
uf.insert((r,c))
for rr, cc in [(r-1,c),(r+1,c),(r,c-1),(r,c+1)]:
if (rr, cc) not in uf: continue
uf.union((r,c), (rr,cc))
if (0,0) in uf and (n-1,n-1) in uf and uf.find((0,0)) == uf.find((n-1,n-1)):
return t


### 118. 676. Implement Magic Dictionary

• HashMap / Trie
• Medium
• O(N^2)
class MagicDictionary:
def _gen_neighbors(self, word):
for i in range(len(word)):
yield word[:i] + '*' + word[i + 1:]

def buildDict(self, words) -> None:
"""Build a dictionary through a list of words."""
self.words = set(words)
self.neighbor_counts = defaultdict(int)
for word in words:
for neighbor in self._gen_neighbors(word):
self.neighbor_counts[neighbor] += 1

def search(self, word: str) -> bool:
"""
Returns if there is any word in the dictionary that equals to the given word after modifying exactly one character
"""
counts = sum(map(self.neighbor_counts.__getitem__, self._gen_neighbors(word)))
if word in self.words:
return counts > len(word)
return counts >= 1


### 119. 62. Unique Paths

• DP
• Medium
• O(MN)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [1] * n
for row, col in product(range(1, m), range(1, n)):
dp[col] = dp[col] + dp[col-1]
return dp[-1]


### 120. 233. Number of Digit One

• Math
• Hard
• O(N)

f(n) = number of digit one from number up to (10 ** n) inclusive. f(0) = 0, f(1) = 1, f(2) = 20, f(3) = 300, f(4) = 4000 etc f(i) = 10 * f(i-1) + 10 ** i 0 to 9 + all numbers of length(i-1) + add one to all numbers from 0 to 10 ** i - 1

232 -> enumerate over digits from least significant to most significant. If d and d == 1: total += f(i) + remainder + 1 (f(i) from add 1 to all numbers with length i - 1) If d and d > 1: total += f(i) * d + 10 ** i

class Solution:
def countDigitOne(self, n):
total = num_ones = 0
base, remainder = 1, 0
for i, d in enumerate(map(int, reversed(str(n)))):
if d == 1: total += num_ones + remainder + 1
if d >  1: total += num_ones * d + base
num_ones = 10 * num_ones + base
remainder += d * base
base *= 10


• Trie
• Hard
• O(L)
class TrieNode(defaultdict):
def __init__(self):
self.default_factory = TrieNode
self.type = "path"
self.content = ""

class FileSystem:
def __init__(self):
self.root = TrieNode()

@staticmethod
def _split(path):
if path == "/": return []  # root dir
return path[1:].split("/")       # sequence of sub dirs

def ls(self, path: str) -> List[str]:
node = self.root
for d in self._split(path):
if d not in node: return []
node = node[d]
if node.type == "file": return [path.split("/")[-1]]
return sorted(list(node.keys()))

def mkdir(self, path: str) -> None:
node = self.root
for d in self._split(path):
node = node[d]

def addContentToFile(self, filePath: str, content: str) -> None:
node = self.root
for d in self._split(filePath):
node = node[d]
node.type = "file"
node.content += content

def readContentFromFile(self, filePath: str) -> str:
node = self.root
for d in self._split(filePath):
node = node[d]
return node.content


### 122. 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

• Monotonic Deque
• Medium
• O(N)
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
hi = deque()
lo = deque()

i = 0
for num in nums:
while hi and hi[-1] < num: hi.pop()
while lo and lo[-1] > num: lo.pop()
hi.append(num)
lo.append(num)

if hi[0] - lo[0] > limit:
if hi[0] == nums[i]: hi.popleft()
if lo[0] == nums[i]: lo.popleft()
i += 1
return len(nums) - i


### 123. 788. Rotated Digits

• Array
• Medium
• O(N)
class Solution:
def rotatedDigits(self, n: int) -> int:
s1 = set([0, 1, 8])
s2 = set([0, 1, 8, 2, 5, 6, 9])
s = set()
res = 0
n = list(map(int, str(n)))
for i, v in enumerate(n):
for j in range(v):
if s.issubset(s2) and j in s2: res += 7 ** (len(n) - i - 1)
if s.issubset(s1) and j in s1: res -= 3 ** (len(n) - i - 1)
if v not in s2: return res
return res + (s.issubset(s2) and not s.issubset(s1))


### 124. 85. Maximal Rectangle

• Stack
• Hard
• O(MN)

Process the matrix to compute longest horizontal length from left to each cell( vertical from top, etc will do as well). Use the linear time stack based solution to largest rectangle area problem to scan these column by column.

def largestRectangleArea(heights):
heights.append(0)
stack = [-1]
max_area = 0
for i, height in enumerate(heights):
while stack and heights[stack[-1]] > height:
h = heights[stack.pop()]
w = i - stack[-1] - 1
max_area = max(max_area, h * w)
stack.append(i)
heights.pop()
return max_area

class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
nrow, ncol = len(matrix), len(matrix[0])

lengths = [[0] * ncol for _ in range(nrow)]
for r, row in enumerate(matrix):
strike = 0
for c, cell in enumerate(row):
strike = strike + 1 if cell == "1" else 0
lengths[r][c] = strike

max_area = 0
for heights in map(list, zip(*lengths)):
max_area = max(max_area, largestRectangleArea(heights))

return max_area


### 125. 1110. Delete Nodes And Return Forest

• Preorder Traversal
• Medium
• O(N)
class Solution:
def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
to_delete = set(to_delete)
roots = [] if root.val in to_delete else [root]
stack = [root]
while stack:
node = stack.pop()
for child in (node.left, node.right):
if child is None: continue
if node.val in to_delete and child.val not in to_delete: roots.append(child)
stack.append(child)

if node.left and node.left.val in to_delete: node.left = None
if node.right and node.right.val in to_delete: node.right = None
return roots


### 126. 1007. Minimum Domino Rotations For Equal Row

• Array
• Medium
• O(N)
class Solution:
def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
n = len(tops)
min_rotations = n + 1
for c in [tops[0], bottoms[0]]:
tc = bc = 0
for t, b in zip(tops, bottoms):
if t != c and b != c: break
tc += int(t == c)
bc += int(b == c)
else: min_rotations = min(min_rotations, (n - tc), (n - bc))
return -1 if min_rotations == n + 1 else min_rotations


### 127. 56. Merge Intervals

• Sweep Line
• Medium
• O(N)
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
merged_intervals = []
l1, r1 = intervals[0]
for l2, r2 in intervals[1:]:
if l2 > r1:
merged_intervals.append((l1, r1))
l1, r1 = l2, r2
elif r2 > r1:
r1 = r2
merged_intervals.append((l1, r1))
return merged_intervals


### 128. 1231. Divide Chocolate

• Binary Search
• Hard
• O(NlogN)

write a greedy function to verify if target sweetness can be achived. Binary search between 0 and average sweetness + 1. Find the largest value where the function is still true.

class Solution:
def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
def can_divide(amt):
num_chunks, accum = 0, 0
for num in sweetness:
accum += num
if accum >= amt:
num_chunks += 1
accum = 0
return num_chunks >= k + 1

lo, hi = 0, sum(sweetness) // (k + 1) + 1
while lo < hi:
mid = (lo + hi) >> 1
if not can_divide(mid):
hi = mid
else:
lo = mid + 1
return lo - 1   # lo will be the leftmost such that not can_divide, thus lo - 1 is the rightmost such that can_divide


### 129. 419. Battleships in a Board

• Array
• Medium
• O(MN)

Count only the top-left cell of the ship.

class Solution(object):
def countBattleships(self, board):
nrow, ncol = len(board), len(board[0])
count = 0
for r, c in product(range(nrow), range(ncol)):
if board[r][c] != 'X': continue
if r > 0 and board[r-1][c] == 'X': continue
if c > 0 and board[r][c-1] == 'X': continue
count += 1
return count


### 130. 659. Split Array into Consecutive Subsequences

• Greedy
• Medium
• O(N)

Keep track of sequnces by ending number and length. Greedy extending sequences as we see new number. Always add number to shortest sequence ending with number - 1. In the end there should be no length 1 or 2 sequence.

class Solution:
def isPossible(self, nums: List[int]) -> bool:
min_val = nums[0]
nums = [num - min_val for num in nums]

ends_with = [0] * (nums[-1] + 1)
one_ends_with = [0] * (nums[-1] + 1)
two_ends_with = [0] * (nums[-1] + 1)

for num in nums:
if one_ends_with[num - 1]:
one_ends_with[num-1] -= 1
two_ends_with[num] = two_ends_with[num] + 1
continue

if two_ends_with[num - 1]:
two_ends_with[num-1] -= 1
ends_with[num] = ends_with[num] + 1
continue

if ends_with[num-1]:
ends_with[num-1] -= 1
ends_with[num] = ends_with[num] + 1
continue

one_ends_with[num] = one_ends_with[num] + 1

return not (any(one_ends_with) or any(two_ends_with))


### 131. 1855. Maximum Distance Between a Pair of Values

• Two Pointers
• Medium
• O(N)

Iterate over nums1, each step, try advance in nums2 as far as possible.

class Solution:
def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
n1, n2 = len(nums1), len(nums2)
max_dist = 0
j = 0
for i in range(n1):
if j < i: j = i
while j < n2 and nums2[j] >= nums1[i]: j += 1
max_dist = max(max_dist, j - i - 1)
if j == n2: break
return max_dist


### 132. 1102. Path With Maximum Minimum Value

• Union Find / Sorting / Dijkstra
• Hard
• O(MN log MN)

Max Priority Queue with priority be the path min. When search reaches the bottom right, the running min of path min is the maximum.

class UnionFind:
def __init__(self):
self.parents = dict()
self.sizes = dict()

def __contains__(self, i):
return i in self.parents

def insert(self, i):
if self.__contains__(i): return
self.parents[i] = i
self.sizes[i] = 1

def find(self, i):
if not self.__contains__(i):
self.insert(i)
while i != self.parents[i]:
self.parents[i] = self.find(self.parents[i])
i = self.parents[i]
return i

def union(self, p, q):
root_p, root_q = map(self.find, (p, q))
if root_p == root_q: return
small, big = sorted([root_p, root_q], key=lambda x: self.sizes[x])
self.parents[small] = big
self.sizes[big] += self.sizes[small]

class Solution:
def maximumMinimumPath(self, grid: List[List[int]]) -> int:
nrow, ncol = len(grid), len(grid[0])

uf = UnionFind()
for val, r, c in sorted(((grid[r][c], r, c) for r in range(nrow) for c in range(ncol)), reverse=True):
uf.insert((r,c))
for nr, nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
if nrow > nr >= 0 <= nc < ncol and (nr, nc) in uf:
uf.union((r,c), (nr,nc))

if (0, 0) in uf and (nrow-1, ncol-1) in uf and uf.find((0, 0)) == uf.find((nrow-1, ncol-1)):
return val

class PQItem:
def __init__(self, priority, loc): self.priority, self.loc = priority, loc
def __lt__(self, other): return self.priority > other.priority

class Solution:
def maximumMinimumPath(self, grid):
nrow, ncol = len(grid), len(grid[0])
pq = [PQItem(grid[0][0], (0, 0))]
global_min = grid[0][0]

visited = set([(0, 0)])
while pq:
item = heappop(pq)
path_min, (r, c) = item.priority, item.loc
global_min = min(global_min, path_min)
if (r, c) == (nrow-1, ncol-1): return global_min
for nr, nc in (r+1,c), (r-1,c), (r,c-1), (r,c+1):
if nrow > nr >= 0 <= nc < ncol and (nr, nc) not in visited:
heappush(pq, PQItem(min(path_min, grid[nr][nc]), (nr, nc)))


### 133. 2083. Substrings That Begin and End With the Same Letter

• Count
• Medium
• O(N)

Each character, let it appears n times in the string, each pair contributes to 1 substring, thus, n * (n + 1) // 2 from this character. Aggregate over all unique characters.

class Solution:
def numberOfSubstrings(self, s: str) -> int:
return sum(map(lambda v: (v*v + v) >> 1, Counter(s).values()))


### 134. 300. Longest Increasing Subsequence

• Binary Search / Monotonic Stack
• Medium
• O(NlogN)

Brute force DP is O(N^2). DP[i] is length of LIS ending with nums[i]. For DP[i] = max(DP[j] + 1) for j in range(i) if nums[j] < nums[i]. For the monotonic stack solution, length of the stack will be the length LIS. When we encounter a number, it can potential form a prefix for the LIS with the previous LIS ending slightly smaller than it, thus bisect and update the value.

class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
tails = []
for num in nums:
i = bisect_left(tails, num)
if i == len(tails): tails.append(num)
else:               tails[i] = num
return len(tails)


### 135. 417. Pacific Atlantic Water Flow

• BFS / DFS
• Medium
• O(MN)

Find reachable locations from two oceans seperately. Find the intersection among the two sets.

class Solution:
def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:
nrow, ncol = len(matrix), len(matrix[0])

def dfs(stack):
reachable = set()
while stack:
node = stack.pop()
r, c = node
for nr, nc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if (nr, nc) in reachable: continue
if nrow > nr >= 0 <= nc < ncol and matrix[nr][nc] >= matrix[r][c]:
stack.append((nr, nc))
return reachable

p_reachable = dfs(
[(r, 0) for r in range(nrow)] +
[(0, c) for c in range(ncol)]
)
a_reachable = dfs(
[(r, ncol - 1) for r in range(nrow)] +
[(nrow - 1, c) for c in range(ncol)]
)

reachable = p_reachable.intersection(a_reachable)
return reachable


### 136. 1230. Toss Strange Coins

• DP
• Medium
• O(N)
class Solution:
def probabilityOfHeads(self, prob: List[float], target: int) -> float:
dp = [0] * (target + 1)
dp[0] = 1
for i, p in enumerate(prob, 1):
for t in range(min(target, i), -1, -1):
dp[t] = int(t != 0) * dp[t-1] * p + dp[t] * (1-p)
return dp[target]


### 137. 1509. Minimum Difference Between Largest and Smallest Value in Three Moves

• Greedy
• Medium
• O(1)

Exam the extreme cases only. sort then take min of (a[~3] - a[0], a[~2] - a[1], a[~1] - a[2], a[~0] - a[3])

class Solution:
def minDifference(self, nums: List[int]) -> int:
if len(nums) <= 4: return 0
s1, s2, s3, s4 = sorted(nums)[:4]
l1, l2, l3, l4 = sorted(nums, reverse=True)[:4]
min_diff = min(abs(l4-s1), abs(l3 - s2), abs(l2 - s3), abs(l1 - s4))
return min_diff


### 138. 224. Basic Calculator

• Stack
• Hard
• O(N)

Initialize operator to “+”, operand to 0, partial result to 0. Whenever encountering digit, update operand Whenever encountering +-, do partial = op(partial, operator, operand), reset operator and operand Whenever encountering (, put partial result and operator on to stack, and reset operator and partial Whenever encountering ), do operand = op(partial, operator, operand), then pop previous partial result and operator do partial = op(partial, operator, operand)

class BasicCalculatorI:
def calculate(self, s: str) -> int:
stack = []
operator, partial, operand = "+", 0, 0

def operation(a, o, b):
if o == "+": return a + b
if o == "-": return a - b

for c in s:
if c.isdigit():
operand = operand * 10 + int(c)
if c in '+-':
partial = operation(partial, operator, operand)
operator = c
operand = 0
if c == ")":
operand = operation(partial, operator, operand)
operator, partial = stack.pop()
partial = operation(partial, operator, operand)
operand = 0
if c == '(':
stack.append((operator, partial))
operator, partial = "+", 0
return operation(partial, operator, operand)


### 139. 505. The Maze II

• BFS / Dijkstra / Priority Queue
• Medium
• O(MN)
class Solution:
def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
nrow, ncol = len(maze), len(maze[0])
MAX_DIST = nrow * ncol

distances = [[MAX_DIST] * ncol for _ in range(nrow)]
distances[start[0]][start[1]] = 0
dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))

queue = deque([(start, 0)])
while queue:
(r, c), step = queue.popleft()
for dr, dc in dirs:
nr, nc, steps = r, c, step
while nrow > nr + dr >= 0 <= nc + dc < ncol and maze[nr + dr][nc + dc] != 1:
nr += dr
nc += dc
steps += 1
if steps < distances[nr][nc]:
queue.append(((nr, nc), steps))
distances[nr][nc] = steps

return -1 if distances[destination[0]][destination[1]] == MAX_DIST else distances[destination[0]][destination[1]]

pq = [(0, start)]
while pq:
step, (r, c) = heappop(pq)
if [r, c] == destination: return step

for dr, dc in dirs:
nr, nc, steps = r, c, step
while nrow > nr + dr >= 0 <= nc + dc < ncol and maze[nr + dr][nc + dc] != 1:
nr += dr
nc += dc
steps += 1
if steps < distances[nr][nc]:
distances[nr][nc] = steps
heappush(pq, (steps, (nr, nc)))

return -1


### 140. 809. Expressive Words

• String
• Medium
• O(N)

Compare RLE

class Solution:
def expressiveWords(self, S: str, words: List[str]) -> int:
total = 0

def rle(s):
if not s: return [], []
chars, counts, count = [], [], 0
for i, char in enumerate(s):
if not chars:
chars.append(char)
elif char != chars[-1]:
counts.append(count)
chars.append(char)
count = 0
count += 1
counts.append(count)
return chars, counts

s_chars, s_counts = rle(S)
for word in words:
if len(word) > len(S): continue
w_chars, w_counts = rle(word)
if len(s_chars) != len(w_chars): continue
for (s_char, w_char, s_count, w_count) in zip(s_chars, w_chars, s_counts, w_counts):
if s_char == w_char:
if s_count == w_count: continue
elif s_count < w_count: break
elif s_count >= 3: continue
else: break
else:
break
else:
total += 1


### 141. 729. My Calendar I

• SortedList
• Medium
• O(logN)

Keep a sorted list of interval end points. bisect_right start and bisect_left end should give same insertion point (otherwise it intersects with an existing interval). And the insertion point should be even number (otherwise it is encapsulated by an existing interval)

class MyCalendar(SortedList):
def book(self, start, end):
q1 = self.bisect_right(start)
q2 = self.bisect_left(end)
if q1 == q2 and q1 % 2 == 0:
return True
return False


### 143. 2030. Smallest K-Length Subsequence With Occurrences of a Letter

• Monotonic Stack / Greedy
• Hard
• O(N)

Scan from left to right, notice whenever we encounter a lexicographically smallest character, as long as we are sure there are enough letter to the right to fullfill the required repetition and we have enough letter to fullfill the window size. It is better off to ignore all the stuff so far and start from this one. This is also true for second / third and in general any subsequent postition. After one pass to fill this stack, go through the stack a second time to find the window. Grab characters as we see them, stop when we only had space for the required letter.

class Solution:
def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:
n = len(s)
n_reps = s.count(letter)

stack = []
n_left = n_reps - repetition
allowed_removal = n - k
for char in s:
while stack and stack[-1] > char and allowed_removal:
if stack[-1] == letter and n_left == 0: break
n_left -= int(stack[-1] == letter)
allowed_removal -= 1
stack.pop()
stack.append(char)

i = 0
result = []
for i, char in enumerate(stack):
if len(result) == k: break
if char != letter and len(result) + max(0, repetition) >= k: continue
result.append(char)
repetition -= int(char == letter)
return "".join(result)


### 144. 692. Top K Frequent Words

• Sorting / Priority / Quickselect
• Medium
• O(NlogN) Priority Queue or O(N) quickselect
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
count = Counter(words)
heap = [(-freq, word) for word, freq in count.items()]
heapq.heapify(heap)
return [heapq.heappop(heap)[1] for _ in range(k)]


### 145. 1864. Minimum Number of Swaps to Make the Binary String Alternating

• Array
• Medium
• O(N)

generate the two possible target strings. compare diff with both and take note of min.

class Solution:
def minSwaps(self, s: str) -> int:
def diff(s1, s2):
diffs = 0
for c1, c2 in zip(s1, s2):
if c1 != c2: diffs += 1
return diffs // 2

count_1, count_0 = s.count('1'), s.count('0')
if abs(count_1 - count_0) > 1: return -1
if count_1 + count_0 != len(s): return -1

cs_1 = ''.join(['0' if i & 1 else '1' for i in range(len(s))])
cs_2 = ''.join(['1' if i & 1 else '0' for i in range(len(s))])

if count_1 != count_0:
cs = cs_1 if count_1 > count_0 else cs_2
return diff(s, cs)
return min(diff(s, cs_1), diff(s, cs_2))


### 146. 336. Palindrome Pairs

• Trie
• Hard
• O(K^2 N)
class TrieNode(defaultdict):
def __init__(self):
self.word_idx = -1
self.list = []
self.default_factory = TrieNode

class Solution:
def solution_trie(self, words: List[str]) -> List[List[int]]:

def partial_palindrome(w, l):
r = len(w) - 1
while l < r:
if w[l] != w[r]: return False
l += 1; r -= 1
return True

# populating the trie
root = TrieNode()
for i, word in enumerate(words):
node = root
reversed_word = word[::-1]
for j, char in enumerate(reversed_word):
if partial_palindrome(reversed_word, j): node.list.append(i)
node = node[char]
node.word_idx = i

pairs = []
# find the pairs
for i, word in enumerate(words):
node = root
for j, char in enumerate(word):
# case 3: word[j] is longer than a possible word[i]
if node.word_idx != -1 and partial_palindrome(word, j): pairs.append([i, node.word_idx])
if char not in node: break
node = node[char]
else:
# case 1: word[i] == word[j][::-1]
if node.word_idx not in [-1, i]: pairs.append([i, node.word_idx])
# case 2: word[i] is abc|sos  word[j]  cba
for k in node.list: pairs.append([i, k])
return pairs

def solution_trie_lazy(self, words: List[str]) -> List[List[int]]:

def partial_palindrome(w, l):
r = len(w) - 1
while l < r:
if w[l] != w[r]: return False
l += 1; r -= 1
return True

def dfs_gather(node):
partial_palindrome_list = []
stack = [(child, [char]) for char, child in node.items()]
while stack:
node, seqs = stack.pop()
if node.word_idx != -1 and partial_palindrome(seqs, 0): partial_palindrome_list.append(node.word_idx)
stack.extend([(child, seqs + [char]) for char, child in node.items()])
return partial_palindrome_list

# populating the trie
root = TrieNode()
for i, word in enumerate(words):
node = root
for char in reversed(word): node = node[char]
node.word_idx = i

pairs = []
# find the pairs
for i, word in enumerate(words):
node = root
for j, char in enumerate(word):
# case 3: word[j] is longer than a possible word[i]
if node.word_idx != -1 and partial_palindrome(word, j): pairs.append([i, node.word_idx])
if char not in node: break
node = node[char]
else:
# case 1: word[i] == word[j][::-1]
if node.word_idx not in [-1, i]: pairs.append([i, node.word_idx])
# case 2: word[i] is abc|sos  word[j]  cba
node.list = dfs_gather(node)
for k in node.list: pairs.append([i, k])
return pairs

palindromePairs = solution_trie_lazy # solution_trie


### 147. 710. Random Pick with Blacklist

• Design / HashMap / Math
• Hard
• O(1) time O(M) space

Virtual Index.

# n = 7(exclusive) - 0,1,2,3,4,5,6  blacklist - [2,3,5]
# 7 - 3 = 4 <- blacl number below this will be mapped to white number >= this.
# we will random between 0 and 3 inclusive
# if we draw 2 will replace with 4
# if we draw 3 will replace with 6

class Solution:
def __init__(self, n: int, blacklist: List[int]):
self.m = dict()
self.n = n - len(blacklist)

blacklist = set(blacklist)

i = self.n
while i in blacklist: i += 1
for b in blacklist:
if b < self.n:
self.m[b] = i
i += 1
while i in blacklist: i += 1

def pick(self) -> int:
idx = random.randint(0, self.n-1)
return self.m.get(idx, idx)


### 148. 1376. Time Needed to Inform All Employees

• DFS
• Medium
• O(N)
class Solution:
def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
reports = defaultdict(list)
for e, m in enumerate(manager):
reports[m].append(e)

max_time = float('-inf')
while stack:
node, t = stack.pop()
max_time = max(max_time, t)
for report in reports[node]:
stack.append((report, t + informTime[node]))
return max_time


### 149. 1094. Car Pooling

• Sweep Line
• Medium
• O(NlogN)
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
for i, v in sorted(x for n, s, e in trips for x in [[s, n], [e, - n]]):
capacity -= v
if capacity < 0: return False
return True


• Priority Queue / Greedy / Math
• Medium
• O(NlogN) / O(N)
class PQItem:
def __init__(self, priority, value):
self.priority = priority
self.value = value

def __lt__(self, other): return self.priority > other.priority

class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
if n == 0: return len(tasks)

heapify(pq)
num_intervals = 0
while pq:
cooldown = n + 1
while cooldown and pq:
num_intervals += 1
item = heappop(pq)
cooldown -= 1

return num_intervals

def leastInterval(self, tasks: List[str], n: int) -> int:
min_itvs = (max_freq - 1) * (n + 1) + num_max_freq_tasks


### 151. 1531. String Compression II

• DP
• Hard
• O(2^N)
class Solution:
def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
@cache
def dp(i, last, last_count, removal):
if removal < 0: return len(s)
if i >= len(s): return 0
if s[i] == last:
incr = int(last_count in [1, 9, 99])
return incr + dp(i + 1, last, last_count + 1, removal)
else:
keep = 1 + dp(i + 1, s[i], 1, removal)
delete = dp(i + 1, last, last_count, removal - 1)
return min(keep, delete)

return dp(0, "", 0, k)


### 152. 353. Design Snake Game

• Array / Queue + HashMap
• Medium
• O()
class SnakeGame:
def __init__(self, width: int, height: int, food: List[List[int]]):
self.width, self.height = width, height
self.food, self.food_idx = food, 0
self.body = deque([(0, 0)])
self.body_lookup = {(0, 0)}
self.game_over = False

@staticmethod
def _next_loc(loc, d):
r, c = loc
if d == "U": return r-1, c
if d == "D": return r+1, c
if d == "L": return r, c-1
if d == "R": return r, c+1

def move(self, direction: str) -> int:
nr, nc = self._next_loc(self.body[-1], direction)
if nr < 0 or nr == self.height or nc < 0 or nc == self.width:
self.game_over = True
return -1

if self.food_idx < len(self.food) and [nr, nc] == self.food[self.food_idx]:
self.food_idx += 1
else:
old_tail = self.body.popleft()
self.body_lookup.remove(old_tail)

if (nr, nc) in self.body_lookup:
self.game_over = True
return -1

self.body.append((nr, nc))

return len(self.body) - 1


### 153. 708. Insert into a Sorted Circular Linked List

• Medium
• O(N)
class Solution:
def insert(self, head: 'Node', insertVal: int) -> 'Node':
nd = Node(insertVal)
nd.next = nd
return nd

if prev.val <= insertVal <= curr.val: break
if insertVal >= prev.val > curr.val: break
if insertVal <= curr.val < prev.val: break
prev, curr = curr, curr.next

prev.next = Node(insertVal, curr)


### 154. 524. Longest Word in Dictionary through Deleting

• Two Pointers
• Medium
• O(NX)
class Solution:
def findLongestWord(self, s: str, d: List[str]) -> str:

def is_subseq(w, s):
j = 0
for i, c in enumerate(s):
if c == w[j]: j += 1
if j == len(w): return True
return False

longest_word = ''
for w in d:
if is_subseq(w, s):
longest_word = min(longest_word, w, key=lambda x: (-len(x), x))

return longest_word


### 155. 1494. Parallel Courses II

• Hard
• O(N^4)
TopSort + Greedy PQ will fail this case
12
[[11,10],[6,3],[2,5],[9,2],[4,12],[8,7],[9,5],[6,2],[7,2],[7,4],[9,3],[11,1],[4,3]]
3

dp[m] := min semesters to reach state m.
dp[m | c] = min{dp[m | c], dp[m] + 1}, if we can reach m | c from m.
This allows us to get rid of enumerate n semesters.
Time complexity: O(2^n*2^n) <– This will be much smaller in practice.
and can be reduced to O(3^n).
Space complexity: O(2^n)

def bin_count(x):
total = 0
while x:
x = x & (x - 1)
total += 1

INT_MAX = 2 ** 32

class Solution:
def minNumberOfSemesters(self, n, dependencies, k):
deps = [0] * n  # bit mask for the prereqs for course i - 1
for p, d in dependencies: deps[d - 1] |= 1 << p - 1

total = 1 << n
dp = [INT_MAX] * total
dp[0] = 0 # base case

for state in range(total):
if dp[state] == INT_MAX: continue # state not reachable

# all couses currently can be take
for i in range(n): # course
not_taken = (state & (1 << i)) == 0
prereq_ok = (state & deps[i]) == deps[i]
if not_taken and prereq_ok: mask |= (1 << i)

# prunning, if can take all, take all
else:
# try all subsets of size K # this is bit magic!
while subset:
# if subset.bin_count() <= k:
if bin_count(subset) <= k:
dp[state | subset] = min(dp[state | subset], dp[state] + 1)
subset = (subset - 1) & mask
# if dp[-1] != INT_MAX: return dp[-1] # not working
return dp[-1]


### 156. 10. Regular Expression Matching

• DP
• Hard
• O(MN)
class Solution:
def isMatch(self, s: str, p: str) -> bool:
@cache
def dp(i, j):
if j == len(p): return i == len(s)
single_char_match = i < len(s) and p[j] in [s[i], '.']
if j + 1 < len(p) and p[j + 1] == '*':
return dp(i, j + 2) or (single_char_match and dp(i + 1, j))
return single_char_match and dp(i + 1, j + 1)
return dp(0, 0)

def isMatch(self, s, p):
dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
dp[-1][-1] = True
for i in reversed(range(len(s) + 1)):
for j in reversed(range(len(p))):
single_char_match = i < len(s) and p[j] in [s[i], '.']
if j + 1 < len(p) and p[j + 1] == '*':
dp[i][j] = dp[i][j+2] or (single_char_match and dp[i + 1][j])
else:
dp[i][j] = single_char_match and dp[i+1][j+1]
return dp[0][0]


### 157. 1166. Design File System

• Trie
• Medium
• O(N)
class TrieNode(defaultdict):
def __init__(self, val = None):
super().__init__(TrieNode)
self.val = val

class FileSystem:
def __init__(self): self.root = TrieNode()

def createPath(self, path: str, value: int) -> bool:
node = self.root
levels = path.split('/')
parents, child = levels[:-1], levels[-1]
for p in parents:
if p and p not in node: return False
node = node[p]
if child in node: return False
node = node[child]
node.val = value
return True

def get(self, path: str) -> int:
node = self.root
for p in path.split('/'):
if p not in node: return -1
node = node[p]
if node.val is None: return -1
return node.val


### 158. 1631. Path With Minimum Effort

• Priority Queue / Dijkstra / Binary Search
• Medium
• O(MNlog(MN))

Could do binary search though. O(MN) BFS can verify whether there is a path with a given min effort. Apply binary search on range of possible effort.

class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
nrow, ncol = len(heights), len(heights[0])
efforts = [[2**32] * ncol for _ in range(nrow)]
efforts[0][0] = 0
pq = [(0, 0, 0)]
while pq:
effort, r, c = heapq.heappop(pq)
if (r, c) == (nrow - 1, ncol - 1): return effort

for rr, cc in (r + 1, c), (r - 1, c), (r, c - 1), (r, c + 1):
if not (nrow > rr >= 0 <= cc < ncol): continue
next_effort = max(effort, abs(heights[rr][cc] - heights[r][c]))
if efforts[rr][cc] <= next_effort: continue
efforts[rr][cc] = next_effort
heapq.heappush(pq, (next_effort, rr, cc))


### 159. 815. Bus Routes

• BFS
• Hard
• O(MN)

BFS search, but trim a entire route per level.

class Solution:
def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
stop_to_route = defaultdict(set)
for i, route in enumerate(routes):
for stop in route:

n = 0
stop_visited = set()
route_visited = set()
queue = deque([source])
while queue:
new_queue = []
for _ in range(len(queue)):
stop = queue.popleft()
if stop == target: return n

for route_id in stop_to_route[stop]:
if route_id in route_visited: continue
for next_ in routes[route_id]:
if next_ in stop_visited: continue
queue.append(next_)
n += 1
return -1


### 160. 428. Serialize and Deserialize N-ary Tree

• Tree Traversal
• Medium
• O(N)

BFS layer by layer, use null to indicate end of children for that node.

class Codec:
def serialize(self, root: 'Node') -> str:
if not root: return ''
serialized = []
queue = deque([root, None])

while any(queue):
node = queue.popleft()
if not node:
serialized.append('null')
else:
serialized.append(node.val)
queue.extend(node.children + [None])
serialized = ','.join(map(str, serialized))
return serialized

def deserialize(self, data: str) -> 'Node':
if not data: return None
data = data.split(',')
root = Node(int(data[0]), [])
queue = deque([root])
for val in data[2:]:
node = Node(int(val), []) if val != 'null' else None
if node:
queue[0].children.append(node)
queue.append(node)
else:
queue.popleft()
return root


### 161. 1091. Shortest Path in Binary Matrix

• BFS
• Medium
• O(MN)
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
if grid[0][0]: return -1

n = len(grid)
queue = deque([[0, 0, 1]])
visited = set()
while queue:
r, c, l = queue.popleft()
if (r, c) in visited: continue
if (r, c) == (n-1, n-1): return l

for dr, dc in product([-1, 0, 1], repeat=2):
nr, nc = r + dr, c + dc
if n > nr >= 0 <= nc < n and grid[nr][nc] == 0:
queue.append((nr, nc, l + 1))
return -1


### 162. 947. Most Stones Removed with Same Row or Column

• Union Find
• Medium
• O(MN)
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
nrow, ncol = max(s[0] for s in stones) + 1, max(s[1] for s in stones) + 1
parent = list(range(nrow + ncol))

def find(i):
if i != parent[i]: parent[i] = find(parent[i])
return parent[i]

for r, c in stones:
r_comp_idx, c_comp_idx = find(r), find(nrow + c) # find
parent[r_comp_idx] = c_comp_idx                  # union

comp_sizes = Counter()
for r, c in stones:
comp_sizes[find(r)] += 1

return sum([v - 1 for v in comp_sizes.values() if v > 1])


### 163. 1996. The Number of Weak Characters in the Game

• Sorting
• Medium
• O(NlogN)

Sort attack in descending order, within the same attack power sort by increasing defence. Iterate over and keep track of running maximum defence, if we see a new defence lower than running maximum, it has to come from a character with less attack, thus weaker.

class Solution:
def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
max_def = dict()
for a, d in properties:
max_def[a] = max(max_def.get(a, 0), d)

sorted_attacks = sorted(max_def.keys())
max_defence = max_def[sorted_attacks[-1]]
suffix_max = dict()
for a in reversed(sorted_attacks[:-1]):
suffix_max[a] = max_defence
max_defence = max(max_defence, max_def[a])

total = 0
for a, d in properties:
total += suffix_max.get(a, 0) > d

def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
properties.sort(key=lambda x: (-x[0],x[1]))

ans = 0
curr_max = 0

for _, d in properties:
if d < curr_max:
ans += 1
else:
curr_max = d
return ans


### 164. 161. One Edit Distance

• Two Pointers
• Medium
• O(N)
class Solution:
def isOneEditDistance(self, s: str, t: str) -> bool:
ls, lt = len(s), len(t)
if abs(ls - lt) > 1: return False

def str_equal(idx1, idx2):
while idx1 < ls and idx2 < lt:
if s[idx1] != t[idx2]: return False
idx1 += 1; idx2 += 1
return True

for i in range(min(ls, lt)):
if s[i] != t[i]:
if ls == lt: return str_equal(i + 1, i + 1)
elif ls > lt: return str_equal(i + 1, i)
else: return str_equal(i, i + 1)

return ls != lt


### 165. 1074. Number of Submatrices That Sum to Target

• Prefix Sum
• Hard
• O(NM^2)
class Solution:
def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
nrow, ncol = len(matrix), len(matrix[0])

for r, c in product(range(nrow), range(1, ncol)):
matrix[r][c] += matrix[r][c-1]

total = 0
for y1, y2 in combinations_with_replacement(range(ncol), 2):
accumulation = {0: 1}
area = 0
for x in range(nrow):
area += matrix[x][y2]
if y1 > 0: area -= matrix[x][y1-1]
total += accumulation.get(area - target, 0)
accumulation[area] = accumulation.get(area, 0) + 1



### 166. 1227. Airplane Seat Assignment Probability

• Probability
• Medium
• O(1)
f(n) = 1/n                                 -> 1st person picks his own seat, all others including the nth person is going to get their own seats
+ 1/n * 0                              -> 1st person picks last one's seat, there's no chance the nth peroson is going to get his own seat
+ (n-2)/n * (                          -> 1st person picks one of seat from 2nd to (n-1)th
1/(n-2) * f(n-1) +                 -> 1st person picks 2nd seat, see explanation 1 below
1/(n-2) * f(n-2) +                 -> 1st person picks 3rd seat see explanation 2 below
......
1/(n-2) * f(2)                     -> 1st person pick (n-1)th's seat
)

somehow it is 1 if n == 1 and .5 for all n >= 2

class Solution:
def nthPersonGetsNthSeat(self, n: int) -> float:
if n <= 2: return 1 / n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 1 / 2
accum = 1
for i in range(3, n+1):
accum += dp[i-1]
dp[i] = accum / i
return dp[n]


### 167. 1807. Evaluate the Bracket Pairs of a String

• Stack
• Medium
• O(N)
class Solution:
def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
knowledge = {k:v for k, v in knowledge}
result = []
stack = []
for c in s:
if c == "(":
result.extend(stack)
stack = []
elif c == ")":
result.append(knowledge.get("".join(stack), "?"))
stack = []
else:
stack.append(c)
return "".join(result + stack)


### 168. 317. Shortest Distance from All Buildings

• BFS
• Hard
• O((MN)^2)
class Solution:
def shortestDistance(self, grid: List[List[int]]) -> int:
nrow, ncol = len(grid), len(grid[0])

# distances[r][c] -> distances from [r, c] to all reachable buildings.
distances = [[None] * ncol for _ in range(nrow)]

def valid_loc(r, c): return nrow > r >= 0 <= c < ncol

def get_neighbor(r, c): return (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)

def bfs(r, c):
visited = set()
queue = deque([(r, c, 0)])
while queue:
r, c, d = queue.popleft()
for nr, nc in get_neighbor(r, c):
if valid_loc(nr, nc) and grid[nr][nc] == 0 and (nr, nc) not in visited:
if not distances[nr][nc]: distances[nr][nc] = [d + 1]
else: distances[nr][nc].append(d + 1)
queue.append((nr, nc, d + 1))

num_buildings = 0
for r, c in product(range(nrow), range(ncol)):
if grid[r][c] == 1:
num_buildings += 1
bfs(r, c)

min_dist = float('inf')
for r, c in product(range(nrow), range(ncol)):
if grid[r][c] == 0:
if distances[r][c] and len(distances[r][c]) == num_buildings:
min_dist = min(min_dist, sum(distances[r][c]))
return min_dist if min_dist != float('inf') else -1


### 169. 1197. Minimum Knight Moves

• BFS / DFS + Memoization
• Medium
• O(X + Y)

BFS is slow, but very reasonable. DFS / DP can work but need to proof the recursive relationship. Do a abs transformation on the target location so that they remain in the upper triangle of the first quarant. To jump to a position (x, y), the minimal step is either from (|x-1|, |y-2|) or (|x-2|, |y-1|)

class Solution:
def minKnightMoves(self, x: int, y: int) -> int:
x, y = sorted(map(abs, (x, y)))
memo = {(0,0):0, (1,1):2, (1,0):3, (0,1):3}
def dfs(x, y):
if (x,y) not in memo:
memo[(x,y)] = min(dfs(abs(x-1),abs(y-2)), dfs(abs(x-2),abs(y-1))) + 1
return memo[(x,y)]
return dfs(x, y)


### 170. 549. Binary Tree Longest Consecutive Sequence II

• DFS
• Medium
• O(N)
class Solution:
def longestConsecutive(self, root: Optional[TreeNode]) -> int:
max_length = 1
stack = [(root, 0)]
inc_length = defaultdict(int)
dec_length = defaultdict(int)

while stack:
node, backtrack = stack.pop()
if not node: continue
if backtrack == 0: stack.extend([(node, 1), (node.left, 0), (node.right, 0)])
else:
left_inc = left_dec = 1
if node.left:
if node.val == node.left.val - 1: left_inc += inc_length[node.left]
if node.val == node.left.val + 1: left_dec += dec_length[node.left]

right_inc = right_dec = 1
if node.right:
if node.val == node.right.val - 1: right_inc += inc_length[node.right]
if node.val == node.right.val + 1: right_dec += dec_length[node.right]

max_length = max(max_length,  left_inc + right_dec - 1, left_dec + right_inc - 1)

inc_length[node] = max(left_inc, right_inc)
dec_length[node] = max(left_dec, right_dec)

return max_length


### 171. 759. Employee Free Time

• Priority Queue
• Hard
• O(NlogN)
class Solution:
def employeeFreeTime(self, schedules: '[[Interval]]') -> '[Interval]':
n = len(schedules)
pq = [(schedule[0].start, schedule[0].end, i, 0) for i, schedule in enumerate(schedules)]
heapq.heapify(pq)

prev_end = pq[0][0]
result = []
while pq:
this_start, this_end, this_emp_id, schedule_idx = heapq.heappop(pq)

if this_start > prev_end:
result.append(Interval(start=prev_end, end=this_start))
prev_end = this_end
else:
prev_end = max(prev_end, this_end)

schedule_idx += 1
if schedule_idx < len(schedules[this_emp_id]):
next_itv = schedules[this_emp_id][schedule_idx]
heapq.heappush(pq, (next_itv.start, next_itv.end, this_emp_id, schedule_idx))

return result


### 172. 1255. Maximum Score Words Formed by Letters

• Backtrack
• Hard
• O(2^N)

TODO: use counter instead of the state array?

class State:
def __init__(self, scores, seq=None):
self.state = [0] * len(scores)
self.scores = scores
self.score = 0
if seq:
for c in seq:
i = ord(c) - ord('a')
self.state[i] += 1
self.score += self.scores[i]

for i in range(len(self.state)):
self.state[i] += other.state[i]
self.score += other.score
return self

def __isub__(self, other):
for i in range(len(self.state)):
self.state[i] -= other.state[i]
self.score -= other.score
return self

def __le__(self, other):
return all(self.state[i] <= other.state[i] for i in range(len(self.state)))

class Solution:
def maxScoreWords(self, words: List[str], letters: List[str], scores: List[int]) -> int:
word_to_state = {word: State(scores, word) for word in words}
full_state = State(scores, letters)
null_state = State(scores)

self.max_score = 0

def backtrack(state, i):
if not state <= full_state: return
self.max_score = max(self.max_score, state.score)
for j, word in enumerate(words[i:], i+1):
state += word_to_state[word]
backtrack(state, j)
state -= word_to_state[word]

backtrack(null_state, 0)
return self.max_score


### 173. 210. Course Schedule II

• Topological Sort
• Medium
• O(V + E)
class Solution:
def findOrder(self, N: int, prerequisites: List[List[int]]) -> List[int]:
# graph processing
out_edges = [[] for _ in range(N)]
in_degrees = [0 for _ in range(N)]
for course, prereq in  prerequisites:
out_edges[prereq].append(course)
in_degrees[course] += 1

# bfs search for feasibilty as well as order
queue = [course for course, prereq in enumerate(in_degrees) if not prereq]
queue = deque(queue)
taken = []
while queue:
course = queue.popleft()
taken.append(course)
for next_course in out_edges[course]:
in_degrees[next_course] -= 1
if in_degrees[next_course] == 0: queue.append(next_course)
return taken if len(taken) == N else []

def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
adj_list = [[] for _ in range(numCourses)]
for c, p in prerequisites:

taken = set()
prereq = set()
order = deque()

def dfs_has_cycle(course):
if course in taken: return False
if course in prereq: return True

if dfs_has_cycle(next_course): return True
order.appendleft(course)
return False

for course in range(numCourses):
if dfs_has_cycle(course): return []
return order


### 174. 358. Rearrange String k Distance Apart

• Priority Queue
• Hard
• O(NlogN)

Greedy. Always use characters with most remaining copies. Use a queue to store recently used characters and only push them back to priority queue when we can.

class Solution:
def solution_1(self, s: str, k: int) -> str:
if k == 0: return s
pq = [(-counts, char) for char, counts in Counter(s).items()]
heapq.heapify(pq)
result = []
while pq:
if len(pq) < k and pq[0][0] < -1: return ""

temp = []
for _ in range(min(k, len(pq))):
neg_counts, char = heapq.heappop(pq)
result.append(char)
temp.append((neg_counts + 1, char))

for neg_counts, char in temp:
if neg_counts == 0: continue
heapq.heappush(pq, (neg_counts, char))

return "".join(result)

def solution_2(self, s: str, k: int) -> str:
if k == 0: return s
pq = [(-counts, char, None) for char, counts in Counter(s).items()]
heapq.heapify(pq)
dq = deque()
result = []
i = 0
while pq:
neg_counts, char, last_used_at = heapq.heappop(pq)
result.append(char)
neg_counts += 1
if neg_counts < 0: dq.append((neg_counts, char, i))

i += 1
if i >= k and dq and i >= dq[0][2] + k: heapq.heappush(pq, dq.popleft())

return "".join(result) if i == len(s) else ""

rearrangeString = solution_2


### 175. 1483. Kth Ancestor of a Tree Node

• Binary Lifting
• Hard
• O(LogN) query -> trade space for speed
# brute force - Memory Limit Exceeded. O(N^2) space
class TreeAncestor:
def __init__(self, n: int, parent: List[int]):
self.n = n
self.A = A = dict()

# graph
adj_list = [[] for _ in range(n)]
for c, p in enumerate(parent):
if p == -1: continue

# dfs
def dfs(ancestors, node):
A[node] = ancestors.copy()
ancestors.appendleft(node)
dfs(ancestors, child)
ancestors.popleft()

dfs(deque(), 0)

def getKthAncestor(self, node: int, k: int) -> int:
if len(self.A[node]) < k: return -1
return self.A[node][k - 1]

# for each node only store 1st, 2nd, 4th, 8th etc parent pointer
# walk up the tree following bits of k from most significant to least significant bit.
class TreeAncestor:
def __init__(self, n: int, parent: List[int]):
self.n = n
self.A = A = dict()

# graph
adj_list = [[] for _ in range(n)]
for c, p in enumerate(parent):
if p == -1: continue

# dfs
def dfs(ancestors, node):
A[node] = []   # log_2(D) pointers
i = 1
while i < len(ancestors):
A[node].append(ancestors[i])
i <<= 1

ancestors.appendleft(child)
dfs(ancestors, child)
ancestors.popleft()

dfs(deque([0]), 0)

def getKthAncestor(self, node: int, k: int) -> int:
bin_k = bin(k)[2:]
for i, bit in zip(reversed(range(len(bin_k))), bin_k):
if bit == "0": continue
if i >= len(self.A[node]): return -1
node = self.A[node][i]
return node


### 176. 542. 01 Matrix

• BFS
• Medium
• O(MN)
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
nrow, ncol = len(matrix), len(matrix[0])

def neighbors(r, c):
for rr, cc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= rr < nrow and 0 <= cc < ncol:
yield rr, cc

q = collections.deque([((r, c), 0)
for r in range(nrow)
for c in range(ncol)
if matrix[r][c] == 0])
seen = {x for x, _ in q}
ans = [[0] * ncol for _ in range(nrow)]
while q:
(r, c), dist = q.popleft()
ans[r][c] = dist
for nei in neighbors(r, c):
if nei not in seen:
q.append((nei, dist + 1))
return ans


### 177. 267. Palindrome Permutation II

• Backtrack
• Medium
• O(N!)
class Solution:
def generatePalindromes(self, s: str) -> List[str]:
kv = Counter(s)
mid = [k for k, v in kv.items() if v % 2]

if len(mid) > 1: return []

mid = '' if mid == [] else mid[0]
half = ''.join([k * (v // 2) for k, v in kv.items()])
half = [c for c in half]

def backtrack(candidate):
if len(candidate) == len(half):
cur = ''.join(candidate)
solution.append(cur + mid + cur[::-1])
return

for i in range(len(half)):
if visited[i] or (i > 0 and half[i] == half[i-1] and not visited[i-1]): continue
visited[i] = True
candidate.append(half[i])
backtrack(candidate)
visited[i] = False
candidate.pop()

solution = []
visited = [False] * len(half)
backtrack([])
return solution


### 178. 4. Median of Two Sorted Arrays

• Binary Search
• Hard
• O(logN)

first p1 numbers from nums1 and first p2 numbers from nums2 shoud make half of the total numbers. max of (nums1[p1-1], nums[p2-1]) should either be the median or one of the two numbers averaged to get the median. min of (nums1[p1], nums[p2]) may be one of the two numbers averaged to get the median. Above depends on odd or even total numbers. Special care when p1, p2 p1-1, p2-1 are boundries.

class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if len(nums2) < len(nums1): nums1, nums2 = nums2, nums1

l1, l2 = len(nums1), len(nums2)
half_size = (l1 + l2 + 1) // 2
is_even = not ((l1 + l2) % 2)

l, h = 0, len(nums1)
while l <= h:
p1 = (l + h) // 2
p2 = half_size - p1

max_left_1 = float("-inf") if p1 == 0 else nums1[p1 - 1]
max_left_2 = float("-inf") if p2 == 0 else nums2[p2 - 1]

min_right_1 = float("inf") if p1 == l1 else nums1[p1]
min_right_2 = float("inf") if p2 == l2 else nums2[p2]

max_left, min_right = max(max_left_1, max_left_2), min(min_right_1, min_right_2)

if max_left <= min_right: return (max_left + min_right) / 2 if is_even else max_left
elif max_left_1 > min_right_2: h = p1 - 1
elif max_left_2 > min_right_1: l = p1 + 1


### 179. 1406. Stone Game III

• DP
• Hard
• O(NK)

DP[i] represent the maximum difference(alice’s score - bob’s score) if game starts with values[i:] and it is Alice’s term. DP[i] = max(sum(val[i:i+k]) - DP[i+k] for k in 1,2,3)

class Solution:
def stoneGameIII(self, stoneValue: List[int]) -> str:
n = len(stoneValue)
INF = 2**32

@cache
def dp(i):
if i == n: return 0
diff = -INF
score = 0
for j in range(i, min(i + 3, n)):
score += stoneValue[j]
diff = max(val, score - dp(j + 1))
return diff

diff = dp(0)
if diff == 0: return "Tie"
if diff > 0: return "Alice"
return "Bob"


### 180. 222. Count Complete Tree Nodes

• Binary Tree / Complete Binary Tree
• Medium
• O((logN) ^ 2)
class Solution:
def countNodes(self, root: TreeNode) -> int:
def depth(node):
d = 0
while node:
d += 1
node = node.left
return d

max_depth = depth(root)
node, num_nodes = root, 0
d = max_depth
while node:
if depth(node.right) == d - 1:
num_nodes += 2 ** (d - 1)
node = node.right
else:
num_nodes += 2 ** (d - 2)
node = node.left
d -= 1

return num_nodes


### 181. 753. Cracking the Safe

• DFS
• Hard
• O(N2^K)

Find the shortest input password such that each possible n-length combination of digits [0..k-1] occurs exactly once as a substring. How do we proof it is the shortest?

class Solution:
def crackSafe(self, n: int, k: int) -> str:
total = k ** n

def dfs(candidate, tried):
if len(tried) == total: return candidate
for i in range(k):
state = candidate[-(n-1):] + str(i) if n != 1 else str(i)
if state not in tried:
res = dfs(candidate + str(i), tried)
if res: return res
tried.remove(state)

return dfs("0" * n, set(["0" * n]))


### 182. 834. Sum of Distances in Tree

• Tree / DFS / Postorder -> Preorder
• Hard
• O(N)

If we pick a node as root. f(node) = sum of distances in tree rooted at node. s(node) = number of nodes in tree rooted at node. s(node) = sum(s(child)) + 1 f(node) = sum(f(child) + s(child)) Can solve for this selected root in O(N) time. If we apply this repeatedly will be O(N^2) time. Instead try figure out relationship to reuse the calculated quantities.

Consider node a and node a’s parent p(a). If we figured out f(p(a)). Can we calculate f(a)?

f(a) = f(p(a)) - s(a)  + (n - s(a))
^           ^
|           |
|           for the nodes not in a's subtree but in p(a)'s subtree,
|           a is 1 distance greater than p(a) to them
for nodes in a's subtree, a is 1 distance closer to them than p(a)


Thus two dfs, first time to get s(x) and f(0). Then from f(0) dfs to figure out all f(x)

class Solution:
def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:

for a, b in edges:

subtree_sum = [0] * n
subtree_size = [1] * n

stack = [(0, None, 0)]
while stack:
node, parent, post = stack.pop()
if post == 0:
stack.append((node, parent, 1))
if child == parent: continue
stack.append((child, node, 0))
else:
subtree_size[node] = 1 + sum(
subtree_size[child]
if child != parent
)
subtree_sum[node] = sum(
subtree_sum[child] + subtree_size[child]
if child != parent
)

stack = [(0, None)]
while stack:
node, parent = stack.pop()
if child == parent: continue
subtree_sum[child] = subtree_sum[node] - subtree_size[child] + n - subtree_size[child]
stack.append((child, node))

return subtree_sum


### 183. 380. Insert Delete GetRandom O(1)

• Design / HashMap + List
• Medium
• O(1)
class RandomizedSet:
def __init__(self):
self.m = dict()
self.l = list()

def insert(self, val: int) -> bool:
if val in self.m: return False
self.m[val] = len(self.l)
self.l.append(val)
return True

def remove(self, val: int) -> bool:
if val not in self.m: return False
l, m = self.l, self.m
l[m[val]] = l[-1]
m[l[-1]] = m[val]
l.pop()
m.pop(val)
return True

def getRandom(self) -> int:
return self.l[random.randint(0, len(self.l) - 1)]


### 184. 847. Shortest Path Visiting All Nodes

• Hard
• O(2 ^ N * N^2)
class Solution:
def shortestPathLength(self, graph: List[List[int]]) -> int:
if len(graph) == 1: return 0

n = len(graph)
ending_mask = (1 << n) - 1
queue = deque([(node, 1 << node) for node in range(n)])
seen = set(queue)

steps = 0
while queue:
for i in range(len(queue)):
for neighbor in graph[node]:
return 1 + steps

if (neighbor, next_mask) not in seen:

steps += 1


### 185. 400. Nth Digit

• Math
• Medium
• O(logN)
class Solution:
def findNthDigit(self, n: int) -> int:
n_digits, start = 1, 1
while n > n_digits * (start * 9):
n -= n_digits * (start * 9)
n_digits += 1
start *= 10

diff, digit = divmod(n - 1, n_digits)
number = start + diff
return int(str(number)[digit])


### 186. 362. Design Hit Counter

• Binary Search?
• Medium
• O(logN) for search, O(1) insert
class HitCounter:
def __init__(self):
self.container = []

def hit(self, timestamp: int) -> None:
self.container.append(timestamp)

def getHits(self, timestamp: int) -> int:
i = bisect_right(self.container, timestamp - 300)
j = bisect_right(self.container, timestamp)
return j - i


• Array
• Medium
• O(N)
class Solution:
def removeComments(self, source: List[str]) -> List[str]:
res, buffer, block_comment_open = [], [], False
for line in source:
i = 0
while i < len(line):
char = line[i]
if   line[i:i+2] == "//" and not block_comment_open:
i = len(line)
elif line[i:i+2] == "/*" and not block_comment_open:
block_comment_open = True; i += 2
elif line[i:i+2] == "*/" and block_comment_open:
block_comment_open = False; i += 2
elif not block_comment_open:
buffer.append(char); i += 1
else:
i += 1
if buffer and not block_comment_open:
res.append("".join(buffer))
buffer = []
return res


### 188. 130. Surrounded Regions

• DFS
• Medium
• O(MN)
class Solution:
def solve(self, board: List[List[str]]) -> None:
if not board: return board
nrow, ncol = len(board), len(board[0])
safe = set()

def mark_safe(r, c):
stack = [(r,c)]
while stack:
r, c = stack.pop()
if (r, c) in safe: continue
for rr, cc in [(r-1,c), (r+1,c), (r,c-1), (r,c+1)]:
if 0 <= rr < nrow and 0 <= cc < ncol and board[rr][cc] == 'O':
stack.append((rr, cc))

# marking
for r, c in product(range(nrow), [0, ncol-1]):
if board[r][c] == 'O' and (r, c) not in safe: mark_safe(r, c)

for r, c in product([0, nrow - 1], range(1, ncol-1)):
if board[r][c] == 'O' and (r, c) not in safe: mark_safe(r, c)
# flipping
for r, c in product(range(nrow), range(ncol)):
if board[r][c] == 'O' and (r, c) not in safe: board[r][c] = 'X'


### 189. 1055. Shortest Way to Form String

• HashMap / Binary Search
• Medium
• O(M + NLogM)

Bruteforce is MN. Save char to list of sorted indices, then we can binary search.

class Solution:
def shortestWay(self, source: str, target: str) -> int:
char_locs = dict()
for i, char in enumerate(source):
char_locs.setdefault(char, []).append(i)

i, num_rounds = 0, 1
for char in target:
if char not in char_locs:  return -1
locs = char_locs[char]
j = bisect.bisect_left(locs, i)
if j == len(locs):
num_rounds += 1
i = locs[0] + 1
else:
i = locs[j] + 1

return num_rounds


### 190. 1368. Minimum Cost to Make at Least One Valid Path in a Grid

• Deque / BFS / DFS
• Hard
• O(MN)

0-1 BFS with relaxation. Initialize costs for all loc as INF. Use a deque, vising nodes’ neighbors. updating the cost to visit for neighbor locations. if cost not increasing, put (cost, nr, nc) to left to continue touring, otherwise put (cost + 1, nr, nc) to right.

INF = 2 ** 32

class Solution:
def minCost(self, grid: List[List[int]]) -> int:
nrow, ncol = len(grid), len(grid[0])

def moves(r, c):
for nr, nc, d in ((r,c+1,1),(r,c-1,2),(r+1,c,3),(r-1,c,4)):
if nrow > nr >= 0 <= nc < ncol:
yield nr, nc, int(d != grid[r][c])

costs = [[INF] * ncol for _ in range(nrow)]
costs[0][0] = 0
queue = deque([(0, 0, 0)])
while queue:
cost, r, c = queue.popleft()
if (r, c) == (nrow - 1, ncol - 1): return cost
if cost > costs[r][c]: continue

for nr, nc, step_cost in moves(r, c):
if cost + step_cost < costs[nr][nc]:
costs[nr][nc] = cost + step_cost
if step_cost: queue.append((cost + 1, nr, nc))
else:         queue.appendleft((cost, nr, nc))
return -1


### 191. 894. All Possible Full Binary Trees

• Backtrack
• Hard
• O(2^N * N)
class Solution:
def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
if n % 2 == 0: return []

# lenth of encoding to minimal number of nodes # for pruning
mapping = {2 ** i - 1: 2 * i - 1 for i in range(n)}

def backtrack(candidate, n_nodes):
if n_nodes == n: return roots.append(deserialize(candidate))

if n_nodes < mapping.get(len(candidate), 0): return

for choice in [(0, 0), (None, None)]:
if choice == (0, 0) and candidate[len(candidate) // 2] is None: continue # no parent node attachable

candidate.extend(choice)
backtrack(candidate, n_nodes + 2 * (choice == (0, 0)))
candidate.pop()
candidate.pop()

def deserialize(serialization):
root = TreeNode()
tree = [root]
for i, m in enumerate(serialization[1:], 1):
node = TreeNode() if m == 0 else None
par, right = divmod(i - 1, 2)
if node:
if right: tree[par].right = node
else:     tree[par].left  = node
tree.append(node)
return root

roots = []
backtrack([0], 1)
return roots


### 192. 490. The Maze

• BFS
• Medium
• O(MN)
class Solution:
def hasPath(self, maze, start, destination):
queue = deque([start])
nrow, ncol = len(maze), len(maze[0])
dirs = ((0,-1),(0,1),(-1,0),(1,0))
while queue:
r, c = queue.popleft()
if [r, c] == destination: return True
for dr, dc in dirs:
nr, nc = r, c
while 0 <= nr + dr < nrow and 0 <= nc + dc < ncol and `