366. Find Leaves of Binary Tree
366. Find Leaves of Binary Tree
 Tree
 Medium
 O(N)
Categorize nodes by height, postorder traversal as node’s height = max(children’s height) + 1.
1293. Shortest Path in a Grid with Obstacles Elimination
 Graph 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.
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, use kadane from both directions.
843. Guess the Word
 Random / Math
 Hard
 Does not apply
Random guess > match guess with secret > filter words have a different match with guess > try again. Collect info to help filter?
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))
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.
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) on a caveat, when Count(x//2) = 0, or we work on this from smallest x to largest.
359. Logger Rate Limiter
 Design / Hashmap
 Medium
 O(1) or O(Q)
Memory not concern: Hash messages to timestamps. Limited Queue memory size > deque + set
833. Find And Replace in String
 Sweep line / Two Pointers
 Medium
 O(N + KlogK)
Sweep line process replacements from left to right.
1048. Longest String Chain
 DP
 Medium
 O(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.
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.
792. Number of Matching Subsequences
 Greedy / HashMap
 Medium
 O(N+MK)
Hash first character to next_iterator. Go over S, pop matching iterators, get next, and hash back.
690. Employee Importance
 Tree
 Medium
 O(N)
Traverse the tree, add up node property values.
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
954. Array of Doubled Pairs
 Math
 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.
2034. Stock Price Fluctuation
 Sorted Containers (AVL Tree)
 Medium
 O(logK) for all ops
time > price for current price lookup: sorted by key  time; price > timestamps for min max price lookup: sorted by key  price
1277. Count Square Submatrices with All Ones
 DP
 Medium
 O(N^2)
f(i, j) is length of desired matrics with bottom right at i,j. Original problem is sum(f(i,j) for i for j). f(i, j) = min(f[i1,j], f(i, j1), f(i1,j1)) + 1 or 0.
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.
384. Shuffle an Array
 Math
 Medium
 O(N)
Iterate over i in range(n), random sample i <= j < n, swap A[i], A[j].
1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
 Backtracking
 Hard
 O((MN)^2)
Not sure a better solution exists? Brute force backtracking is accepted in OJ.
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.
1834. SingleThreaded CPU
 Priority Queue / Sweep line
 Medium
 O(N*logQ)
Follow the timeline. Adding tasks if start_time <= current time to priority queue with priority (processing_time, start_time).
631. Design Excel Sum Formula
 Design?
 Hard
 O(MN)
Code the static version with is straight forward just tedious. Is it actually about this?
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(rl+1). Move to l+1 and start again.
1877. Minimize Maximum Pair Sum in Array
 Sort + Greedy
 Medium
 O(NlogN + N)
Sort then two pinter finding max. proof four numbers. al <= ai <= aj <= ar max(al+ar, ai+aj) is always <= max(al+ai, aj+ar).
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?
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(ddiff) + 1 or 1
735. Asteroid Collision
 Stack / Sweep line
 Medium
 O(N)
Encounter a positive one append; Encounter a negative one > handle collision if needed, pop/append per result.
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.
664. Strange Printer
 DP
 Hard
 O(N^2)
f(i,j) = # ops to cover [i to j), solution to original problem is f(i, n). relation f(i,j) = min(f(i+1,j) +1, f(i+1, k) + f(k+1, j) for k between i and j)
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.
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.
981. Time Based KeyValue Store
 Design / Binary Search
 Medium
 O(logN)
Map key to SortedDict with time be key. So query can be done by binary search on keytime.
940. Distinct Subsequences II
 DP
 Hard
 O(N)
Very tricky relation: f(i) = 2 * f(i1)  f(last_loc(char_at(i))
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].
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 crashes B before E can catch up with A. Then from E’s perspective, A is equivalent to B.
1987. Number of Unique Good Subsequences
 DP
 Hard
 O(N)
Leave 0 to the last. expansion f(i, k) be # of good subsequences end at i with value k. f(i, k) = sum(f(i1, k) + b[i] for all k) very tricky
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.
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.
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)
465. Optimal Account Balancing
 DFS
 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.
745. Prefix and Suffix Search
 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.
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.
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.
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
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.
528. Random Pick with Weight
 Math / Binary Search
 Medium
 O(N) init O(logN) search
Calculate CDF, do binary search on it.
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.
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.
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.
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.
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.
305. Number of Islands II
 Union Find
 Hard
 O(MN)
Dynamic connectivity > Union Find.
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.
1368. Minimum Cost to Make at Least One Valid Path in a Grid
 Deque / BFS / DFS
 Hard
 O(MN)
01 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.
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.
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.
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.
803. Bricks Falling When Hit
 Union Find
 Hard
 O(MN)
Reverse the order and do unionfind. Use a sink/hook for the ceiling.
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.
1680. Concatenation of Consecutive Binary Numbers
 Bit
 Medium
 O(N)
Iterate over n, accum = (accum « n.bit_lengt()  n) % m. 
990. Satisfiability of Equality Equations
 Union Find
 Medium
 O(N)
Create connected components with equality. Then check all the inequality for violation.
834. Sum of Distances in Tree
 Tree / DFS
 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)
837. New 21 Game
 DP / Math / Sliding Window
 Medium
 O(N)
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, iw), min(i, k)) } use a sliding window for this sum.
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.
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.
200. Number of Islands
 DFS / BFS
 Medium
 O(MN)
Count the number of connected components.
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.
593. Valid Square
 Math
 Medium
 O(1)
Calculate pairwise distances. Square will only have two lengths, side or diagonal.
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.
1618. Maximum Font to Fit a Sentence in a Screen
 Binary
 Medium
 O(NlogF)
Given a font size, it take O(N) time to verify whether it is possible. Apply binary search on font sizes to figure out maximum.
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.
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.
857. Minimum Cost to Hire K Workers
 Greedy / Priority Queue
 Hard
 O(NlogN)
If we form a team, everyone will be paid at max(wage_i/quality_i for all i) within the team. Thus sort workers in increasing order of this ratio. Introduce worker to team means increasing ratio of the team. Be greedy and getting rid of worker with higest quality to see if it counters the rate increase and produce a lower overall team cost.
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.
2092. Find All People With Secret
 Graph
 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)
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(i1) + 10 ** i 0 to 9 + all numbers of length(i1) + 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
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.
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.
835. Image Overlap
 Sliding Window / HashMap
 Medium
 O(N^4)
Can count (x2x1, y2y1) 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.
329. Longest Increasing Path in a Matrix
 Topological Sort / BFS
 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.
2096. StepByStep 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.
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.
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.
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)
1240. Tiling a Rectangle with the Fewest Squares
 Backtracking
 Hard
 O(MN*N^M) where we sort N, M such that M < N
 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.
 Do backtrack
class Solution:
def tilingRectangle(self, n: int, m: int) > int:
if n > m: return self.tilingRectangle(m, n)
self.total = n * m
h = [0] * n
def backtrack(curr):
if curr >= self.total: return
min_height = min(h)
if min_height == m: self.total = curr; return
l = r = h.index(min_height)
while r < n and h[r] == h[l] and (r  l + 1 + min_height) <= m: r += 1
for j in range(r1, l1, 1):
for k in range(l, j+1): h[k] += j  l + 1
backtrack(curr + 1)
for k in range(l, j+1): h[k] = j  l + 1
backtrack(0)
return self.total
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.
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 + es]"""
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[res: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)
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]
def __iadd__(self, other):
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
2030. Smallest KLength 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.
[1642]
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
reachable.add(node)
for nr, nc in [(r  1, c), (r + 1, c), (r, c  1), (r, c + 1)]:
if (nr, nc) in reachable: continue
if 0 <= nr < nrow and 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
[732]
[542]
[729]
[1254]
[715]
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])
[920]
[1376]
[632]
[939]
[1166]
[794]
[1706]
[788]
[149]
[1138]
[380]
[846]
[850]
[801]
[1477]
[1]
[2018]
[1110]
[564]
[720]
[307]
[1263]
[1377]
[1102]
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.
[1066]
[1088]
[1531]
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
1345. Jump Game IV
 BFS
 Hard
 O(N)
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).
[996]
[1553]
[1864]
[300]
[1230]
[403]
[62]
[1494]
[708]
[951]
[695]
[731]
[588]
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.
[1275]
[4]
[1162]
[889]
[363]
[1888]
[1227]
[1091]
[317]
[1514]
[1882]
[10]
[1807]
[2115]
[549]
[721]
[85]
[1007]
[847]
[1153]
[222]
[787]
[1490]
[336]
[621]
[261]
[1855]
[37]
[642]
[1055]
[1406]
[1547]
[676]
[726]
[56]
[1624]
[34]
[1740]
[767]
[616]
[7]
[1631]
[894]
[560]
[433]
[400]
[710]
[316]
[886]
[315]
[91]
[360]
[1438]
[324]
[1024]
[298]
[919]
[1270]
[280]
[1325]
[505]
[353]
[1042]
[64]
[780]
[93]
1044. Longest Duplicate Substring
 Rolling Hash / Binary Search
 Hard
 O(NlogN)
class Solution:
def longestDupSubstring(self, S: str) > str:
D = [ord(c)  ord('a') for c in S]
P = 26
MOD = 10 ** 9 + 7
def rolling_hash(L):
# initial window
h = 0
for c in D[:L]: h = (h * P + c) % MOD
seen = defaultdict(list)
seen[h].append(0)
PP = P ** L % MOD
# sliding window
for r, c in enumerate(D[L:], L):
l = r  L + 1
# update hash
# shift left emit the old left adding the new right
h = (h * P  D[r  L] * PP + c) % MOD
# collision detection
if h in seen:
if any(S[ll:ll+L] == S[l:l+L] for ll in seen[h]): return l
seen[h].append(l)
return False
# use binary search to find the max length of duplicated windows
l, h = 0, len(S)
while l < h:
m = (l + h) >> 1
if rolling_hash(m) != False:
l = m + 1
else:
h = m
start = rolling_hash(l1)
return S[start: start + l  1]
[1996]
[41]
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.
[161]
[130]
[759]
[71]
[399]
[525]
[236]
[218]
[773]
[809]
[174]
[852]
[582]
[210]
[362]
[1244]
[460]
[677]
[1525]
[719]
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)
[437]
[1252]
[968]
[1770]
[334]
[1092]
239. Sliding Window Maximum
 Sliding Window / Monotonic Deque
 Hard
 O(N)
Use a deque to keep track of the indices of strickly decreasing items in the window. Once a new element enter the window from the right, anything smaller than it becomes irrelavant to window maximum. Keep track of indices instead of actual value, thus we can check using i  k to see if leftmost element should be poped to matain window valid.
class Solution:
def solution_pq(self, nums: List[int], k: int) > List[int]:
result, pq = [], []
for r, num in enumerate(nums):
heapq.heappush(pq, (num, r))
while pq and pq[0][1] <= r  k: heapq.heappop(pq)
if r >= k  1: result.append(pq[0][0])
return result
def solution_mono_queue(self, nums: List[int], k: int) > List[int]:
result, dq = [], deque()
for i, n in enumerate(nums):
while deque and nums[dq[~0]] < n: dq.pop()
dq.append(i)
if dq[0] == i  k: dq.popleft()
if i >= k  1: result.append(nums[dq[0]])
return result
[1049]
[1136]
[313]
[983]
[1352]
[43]
1235. Maximum Profit in Job Scheduling
 DP + Binary Search / Priority Queue
 Hard
 O(NlogN)
map distinct event end time to integer 1 to n. dp[i] is the maximum profit including event ended on i_to_time[i].
dp[i] = max(dp[j] + profit_of_event_i) where j is the indices in i_to_time such that i_to_time[j] is the largest time before this event ended on i started.
dp here is a monotonic stack, with key be profit! We can apply binary_search(dp, start_time)
INF = 2 ** 32
class Solution:
def solution_dp(self, startTime, endTime, profit):
jobs = sorted([(e,s,p) for s, e, p in zip(startTime, endTime, profit)])
dp = [[0, 0]] # end time and max_profit
for e, s, p in jobs:
prev = bisect.bisect_right(dp, [s, INF])  1
if dp[prev][1] + p > dp[1][1]:
dp.append([e, dp[prev][1] + p])
return dp[1][1]
def solution_pq(self, startTime, endTime, profit):
jobs = sorted([(s,e,p) for s, e, p in zip(startTime, endTime, profit)])
pq = []
max_profit = 0
for s, e, p in jobs:
while pq and s >= pq[0][0]:
max_profit = max(max_profit, pq[0][1])
heapq.heappop(pq)
heapq.heappush(pq, (e, p + max_profit))
return max([q[1] for q in pq], default=max_profit)
jobScheduling = solution_dp
[1859]
[2]
[1641]
[856]
[18]
[1971]
[1101]
[368]
[877]
[23]
[947]
[1436]
[1730]
[17]
[29]
[349]
[205]
[337]
[909]
[662]
[246]
286. Walls and Gates
 BFS / DFS
 Medium
 O(MN)
Instead find closest gate to each room, do the opposite, from gate visit and mark room.
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) > None:
INF = 2147483647
nrow, ncol = len(rooms), len(rooms[0])
queue = deque([[r, c, 0] for r in range(nrow) for c in range(ncol) if rooms[r][c] == 0])
while queue:
r, c, d = queue.popleft()
for nr, nc in ((r+1,c),(r1,c),(r,c+1),(r,c1)):
if not (0 <= nr < nrow and 0 <= nc < ncol and rooms[nr][nc] > d + 1): continue
rooms[nr][nc] = d + 1
queue.append((nr, nc, d + 1))
849. Maximize Distance to Closest Person
 Two Pointers
 Medium
 O(N)
Find the maximum distance among(neightboring 1, left boundry and left most 1, right boundry and right most 1)
class Solution:
def maxDistToClosest(self, seats: List[int]) > int:
max_dist, last, n = 0, 1, len(seats)
for curr, seat in enumerate(seats):
if not seat: continue
dist = curr if last < 0 else (curr  last) / 2
max_dist = max(max_dist, dist)
last = curr
max_dist = max(max_dist, n  last  1)
return int(max_dist)
[345]
[259]
[127]
[173]
115. Distinct Subsequences
 DP
 Hard
 O(MN)
class Solution:
def numDistinct(self, s: str, t: str) > int:
dp = [[0] * (len(s) + 1) for _ in range(len(t) + 1)]
dp[0] = [1] * (len(s) + 1)
for i in range(1, len(t) + 1):
for j in range(i, len(s) + 1):
dp[i][j] = dp[i][j1] + int(bool(t[i1] == s[j1])) * dp[i1][j1]
return dp[1][1]
[416]
[207]
[934]
[128]
[1910]
[103]
[1636]
[295]
[66]
[1446]
[53]
[377]
[250]
[925]
[338]
[836]
[1472]
[25]
[278]
[124]
[692]
134. Gas Station
 Greedy
 Medium
 O(N)
Iterate over the stations, keep track of fuels. If ever fuels go below 0, it means any station between start and current will not be a valid starting station. To tell if it is possible, check the overall gain > loss.
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) > int:
total, tank, candidate = 0, 0, 0
for i, (gain, loss) in enumerate(zip(gas, cost)):
total += gain  loss
tank += gain  loss
if tank < 0: # reset
tank = 0
candidate = i + 1
if total < 0: # not possible
return 1
return candidate
[198]
[387]
[1335]
[57]
[532]
[815]
42. Trapping Rain Water
 Two Pointers / Sweep Line
 Hard
 O(N)
Scan simutenausly form both side to the center, maintain a horizontal level, such that any pit below that level line will be fill. The level will be updated with level = max(level, min(h[l], h[r])), thus it never goes down, and only goes up if both side is at least that high, guarantee the above. Always move the shorter side towards center.
class Solution:
def trap(self, heights: List[int]) > int:
accum = level = 0
l, r = 0, len(heights)  1
while l <= r :
level = max(min(heights[l], heights[r]), level)
if heights[l] < heights[r]:
accum += level  heights[l]
l += 1
else:
accum += level  heights[r]
r = 1
return accum
[658]
[241]
[77]
[543]
[965]
[221]
[260]
[79]
[135]
[673]
[684]
[1570]
[15]
[228]
[1650]
[733]
[459]
[78]
[12]
72. Edit Distance
 DP
 Hard
 O(MN)
f(i, j) = edit distance s[:i] and t[:j].
1. f(i1, j) + 1 delete
f(i, j) = 2. f(i, j1) + 1 insert
3. f(i1,j1) s[i] == t[j] do nothing
4. f(i1,j1) + 1 s[i] != t[j] replace s[i]
class Solution:
def top_down(self, word1: str, word2: str) > int:
n, m = len(word1), len(word2)
@cache
def f(i, j):
if i == 0: return j
if j == 0: return i
return min(
f(i,j1) + 1,
f(i1,j) + 1,
f(i1,j1)+int(word1[i1] != word2[j1])
)
return f(n, m)
def bottom_up(self, word1, word2):
n1, n2 = len(word1), len(word2)
dp = list(range(n2+1))
for r, char1 in enumerate(word1, 1):
ndp = [r] + [0] * n2
for c, char2 in enumerate(word2, 1):
ndp[c] = min(
dp[c] + 1,
ndp[c1] + 1,
dp[c1] + int(char1 != char2)
)
dp = ndp
return dp[1]
minDistance = bottom_up
[348]
[11]
[986]
[282]
[226]
[92]
[2089]
[220]
[797]
[84]
[322]
[155]
[70]
[3]
[461]
[827]
[50]
[332]
[114]
[54]
[208]
[1209]
[188]
[785]
[766]
[1539]
[98]
[415]
[146]
[408]
287. Find the Duplicate Number
 Two Pointers
 Medium

O(N)
 Floyd’s algorithm for cycle detection.
class Solution:
def findDuplicate(self, nums: List[int]) > int:
slow, fast = nums[0], nums[0]
while True:
slow, fast = nums[slow], nums[nums[fast]]
if slow == fast: break
slow = nums[0]
while slow != fast:
slow, fast = nums[slow], nums[fast]
return slow
[503]
[162]
[540]
[22]
[99]
[743]
[209]
[110]
[498]
76. Minimum Window Substring
 Sliding Window / HashMap
 Hard
 O(N)
Brute force HashMap will be O(MN). Use a window to keep track of unmatched char frequencies in the window. Use a single counter to indicate whether the window is valid or not.
INF = 2 ** 32
class CharCounter(Counter):
def __ge__(self, other):
for k in other:
if self.get(k, 0) < other.get(k):
return False
return True
class Solution:
def minWindow(self, s: str, t: str) > str:
target = CharCounter(t)
l = 0
min_size, min_l, min_r = INF, None, None
window = CharCounter()
for r, c in enumerate(s):
window.update(c)
while window >= target:
if r  l + 1 < min_size:
min_size, min_l, min_r = r  l + 1, l, r
window.subtract(s[l])
l += 1
return "" if min_l is None else s[min_l:min_r+ 1]
class Solution:
def minWindow(self, s: str, t: str) > str:
min_size, min_l, min_r = INF, None, None
target = Counter(t)
to_match = len(target)
l = 0
for r, c in enumerate(s):
if c not in target: continue
target[c] = 1
if target[c] == 0: to_match = 1
while to_match == 0:
if s[l] in target:
if target[s[l]] == 0: break
target[s[l]] += 1
l += 1
if to_match == 0 and r  l + 1 < min_size:
min_size, min_l, min_r = r  l + 1, l, r
return "" if min_l is None else s[min_l:min_r+ 1]
[104]
44. Wildcard Matching
 Backtrack
 Hard
 O(MN)
Greedy match, when encounter *, keep track of its location in p and use it to match only one char in s. Continue matching, when match fails, try to backtrack to most recent star in p, use it to match this char in s. Then resume from there.
class Solution:
def isMatch(self, s: str, p: str) > bool:
pi = si = 0
p_star = s_star = 1
while si < len(s):
if pi < len(p) and p[pi] in ['?', s[si]]: # match single
pi += 1; si += 1
elif pi < len(p) and p[pi] == '*': # use star and continue
p_star = pi; s_star = si
pi += 1
elif p_star == 1: # not match, no star to backtrack to
return False
else: # not match, backtrack to most recent *
pi = p_star + 1
si = s_star + 1
s_star = si
return all(x == '*' for x in p[pi:])
[1929]
[16]
[1011]
[46]
1004. Max Consecutive Ones III
 Sliding Window
 Medium
 O(N)
Slide window through the arry, keep track of window size with at most k 0s in the window.
class Solution:
def longestOnes(self, nums: List[int], k: int) > int:
max_length = count = 0
l = 0
for r, num in enumerate(nums):
count += int(num == 0)
while count == k + 1:
count = int(nums[l] == 0)
l += 1
max_length = max(max_length, r  l + 1)
return max_length
[450]
[252]
[215]
[21]
[8]
[100]
[140]
[133]
[14]
[1143]
[217]
[5]
[442]
[905]
[414]
[739]
[392]
[26]
[1512]
[1094]
[973]
[32]
[212]
[27]
[167]
[647]
[1047]
[347]
[312]
[844]
[438]
[219]
[152]
[350]
[48]
[176]
[121]
[69]
227. Basic Calculator II
 Stack
 Medium
 O(N)
Two types of operators, */ has precedence over + thus we are actually evaluating */ first in one pass, then evaluate + in a second pass. First pass: when operator is +, put +operand on stack. When operator is */, replace stack[1] with stac[1] */ operand. Second pass: sum the stack.
class Solution:
def calculate(self, s: str) > int:
operators = set("+*/")
operand, operator = 0, "+"
stack = []
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))
for c in s:
if c.isdigit():
operand = operand * 10 + int(c)
if c in operators:
operation()
operand, operator = 0, c
operation()
return sum(stack)