366. Find Leaves of Binary Tree
1. 366. Find Leaves of Binary Tree
- 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 = {None: -1}
levels = defaultdict(list)
tour = [(root, 0)]
while tour:
node, post = tour.pop()
if node is None: continue
if post:
heights[node] = max(heights[node.left], heights[node.right]) + 1
levels[height].append(node.val)
else:
tour.extend([(node, 1), (node.left, 0), (node.right, 0)])
return levels.values()
2. 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. 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.
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))
seen.add(state)
return -1
3. 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.
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])
4. 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].append([self.snap_id, val])
else:
self.data[index][-1][1] = 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
return self.data[index][loc][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) on a caveat, when Count(x//2) = 0, or we work on this from smallest x to largest.
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 freq_counts[x] > freq_counts[2 * x]: return []
freq_counts[2 * x] -= freq_counts[x] if x else freq_counts[x] // 2
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.
class Solution:
def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
# def dfs(node):
# if node in (None, p, q): return node
# l, r = dfs(node.left), dfs(node.right)
# return node if l and r else l or r
# return dfs(root)
nodes = [None, None, None]
found = dict() # how many target nodes found in the subtree rooted at node?
parents = {root: root}
# find two nodes and LCA
stack = [(root, 0)]
while nodes[0] is None:
node, post = stack.pop()
if post == 0:
stack.append((node, 1))
for child in (node.left, node.right):
if child is None: continue
parents[child] = node
stack.append((child, 0))
continue
f = 0
if node.val == startValue:
found[node] = 1
nodes[1] = node
f += 1
if node.val == destValue:
found[node] = 1
nodes[2] = node
f += 1
f += found.get(node.left, 0) + found.get(node.right, 0)
if f >= 2: nodes[0] = node
if f >= 1: found[node] = 1
lca_node, start_node, dest_node = nodes
# form paths
path_to_lca = []
node = start_node
while node != nodes[0]:
path_to_lca.append("U")
node = parents[node]
path_to_dest = deque([])
node = dest_node
while node != nodes[0]:
if parents[node].left == node:
path_to_dest.appendleft("L")
else:
path_to_dest.appendleft("R")
node = parents[node]
return "".join(path_to_lca) + "".join(path_to_dest)
7. 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]))
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 + " " * (maxWidth - len(line))
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
8. 833. Find And Replace in String
- Sweep line / Two Pointers
- Medium
- O(N + KlogK)
Sweep line process replacements from left to right.
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)
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 in range(1, nrow):
for c in range(1, ncol):
if grid[r][c] == 1: return False
return True
10. 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?
class Solution:
def getMatch(self,word1, word2):
count = 0
for x,y in zip(word1,word2):
if x == y:
count +=1
return count
def findSecretWord(self, wordlist: List[str], master: 'Master') -> None:
i = 0
matches = 0
while i <10 and matches !=6:
index = random.randint(0,len(wordlist)-1)
word = wordlist[index]
matches = master.guess(word)
candidates = []
for w in wordlist:
if matches == self.getMatch(word,w):
candidates.append(w)
wordlist = candidates
i += 1
return word
11. 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
from sortedcontainers import SortedDict
class StockPrice:
def __init__(self):
self.time_to_prices = SortedDict() # time -> price lookup sorted by key - time
self.rec = SortedDict() # min max price lookup sorted by key - price
def update(self, timestamp: int, price: int) -> None:
if timestamp in self.time_to_prices:
prev_price = self.time_to_prices[timestamp]
self.rec[prev_price].remove(timestamp)
if len(self.rec[prev_price]) == 0: self.rec.pop(prev_price)
self.rec.setdefault(price, set()).add(timestamp)
self.time_to_prices[timestamp] = price
def current(self) -> int:
return self.time_to_prices.peekitem(-1)[1]
def maximum(self) -> int:
return self.rec.peekitem(-1)[0]
def minimum(self) -> int:
return self.rec.peekitem(0)[0]
12. 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.
class Solution:
def numMatchingSubseq(self, S, words):
m = defaultdict(list)
for i, word in enumerate(words):
m[word[0]].append((i, 1))
total = 0
for c in S:
ws = m.pop(c, [])
for i, j in ws:
if j == len(words[i]):
total += 1
else:
m[words[i][j]].append((i, j + 1))
return total
13. 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]
14. 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
15. 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.
16. 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.
17. 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.
18. 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]:
adj = defaultdict(set)
indegrees = dict()
for recipe, ingredents in zip(recipes, ingredients):
for ingredent in ingredents:
adj[ingredent].add(recipe)
indegrees[recipe] = len(ingredents)
feasible = []
queue = deque(supplies)
while queue:
ingredent = queue.popleft()
for recipe in adj[ingredent]:
indegrees[recipe] -= 1
if indegrees[recipe] == 0:
feasible.append(recipe)
queue.append(recipe)
return feasible
19. 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
class Logger:
def __init__(T, per=10):
T.messages = set()
T.queue = deque()
T.per = per
def shouldPrintMessage(T, timestamp: int, message: str) -> bool:
while T.queue and timestamp - T.queue[0][1] >= T.per:
msg = T.queue[0][0]
T.queue.popleft()
T.messages.remove(msg)
if message not in T.messages:
T.messages.add(message)
T.queue.append((message, timestamp))
return True
return False
20. 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.
21. 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, startidx = 0, 0
total_len = sum([len(s) for s in sentence]) + len(sentence)
while r < rows:
c = 0
if startidx not in memo:
finish = 0 # repeat time
nowidx = startidx # remain startidx for the key of dp table
# input as many as possible sentence if there is enough space in this row
if cols / total_len > 1:
finish += cols // total_len
c += total_len * finish
# input word by word into this row
while cols - c - len(sentence[nowidx]) >= 0:
c += len(sentence[nowidx]) + 1
nowidx += 1
if nowidx == len(sentence):
nowidx = 0
finish += 1
# fill up dp table
memo[startidx] = [nowidx, finish]
startidx, finish = memo[startidx]
ans += finish
r += 1
return ans
22. 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
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 zip(times, times[1:]):
min_diff = min(min_diff, t2 - t1)
return min_diff
24. 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 = []
adj_list = defaultdict(list)
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
adj_list[r, c].append((nr, nc))
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
for nei in adj_list[loc]:
stack.append((nei, path_length + 1))
return max_path_length
25. 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 = defaultdict(int)
for i, d in enumerate(arr):
last_d = d - difference
if last_d in dp:
dp[d] = dp[last_d] + 1
else:
dp[d] = 1
return max(dp.values())
26. 1834. Single-Threaded 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).
27. 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?
28. 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.
29. 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 in range(1, nrow+1):
for c in 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)
30. 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.
31. 384. Shuffle an Array
- Math
- Medium
- O(N)
Iterate over i in range(n), random sample i <= j < n, swap A[i], A[j]. This is call Fisher-Yates Shuffle
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
32. 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)
return total
33. 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(r-1, l-1, -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
34. 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)
35. 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
36. 631. Design Excel Sum Formula
- Design?
- Hard
- O(MN)
Code the static version with is straight forward just tedious. Is it actually about this?
37. 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)
38. 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)
39. 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
40. 528. Random Pick with Weight
- Math / Binary Search
- Medium
- O(N) init O(logN) search
Calculate CDF, do binary search on it.
from bisect import bisect_left
from random import randint
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(w)
def pickIndex(self) -> int:
return bisect_left(self.cdf, randint(1, self.cdf[-1]), 0, self.n - 1)
41. 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
42. 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
43. 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)
44. 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))
45. 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(i-1, k) + b[i] for all k) very tricky
46. 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)
47. 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].
48. 794. Valid Tic-Tac-Toe State
- Array
- Medium
- O(MN)
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]
49. [1632]
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.
51. 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_read = 0
def read(self, buf, n):
num_read = 0
while num_read < n:
if self.curr_used < self.curr_read:
buf[num_read] = self.buf4[self.curr_used]
num_read += 1
self.curr_used += 1
else:
self.curr_read = read4(self.buf4)
self.curr_used = 0
if self.curr_read == 0: break
return num_read
52. 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
53. 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
54. 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]))
55. 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])
56. 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.
57. 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]
58. 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
59. [1882]
60. 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.
61. 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
62. 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()
visited.add((x, y))
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)
63. 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 # moust 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
if mouse == food: return True
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] == "#":
break # can't jump any further
if turn & 1: # cat move
if not dfs((nr, nc), mouse, turn + 1): # and cat can win
return False
else: # mouse move
if dfs(cat, (nr, nc), turn + 1): # and mouse can win
return True
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)
64. 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).
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
65. 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.
66. 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.
67. 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.
68. 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)
69. 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.
70. 715. Range Module
- Sorted Dictionary / TreeMap
- Hard
- O(NlogN)
Map left to right. Keep sorted order of key.
from sortedcontainers import SortedDict
class RangeModule(SortedDict):
def addRange(self, left, right):
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
71. 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
72. 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
73. 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
74. 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
75. 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.
76. 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)
77. [564]
78. 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
79. 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.add_sentence(sentence, time)
self.stream = []
self.curr = self.root
def add_sentence(self, sentence, freq=1):
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]
node.sentence_ids.add(idx)
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.add_sentence(sentence)
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
80. 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, i-w), min(i, k)) } use a sliding window for this sum.
81. 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)
82. 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
83. 1948. Delete Duplicate Folders in System
- Trie / DFS / Backtrack
- Hard
- O(MN)
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
84. 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
visited.add((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 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
85. 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.
86. 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.
87. 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
path.add(node)
for nxt_node in out_edges[node]:
if dfs(nxt_node): return True
visited.add(node)
path.discard(node)
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
88. 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
89. [1477]
90. 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
visited.add((r, c))
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)
return total
91. 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)
stack = [(headID, 0)]
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
92. 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.
from sortedcontainers import SortedList
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
93. 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
94. 975. Odd Even Jump
- Sorting / Stack / DP
- Hard
- O(NlogN)
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)
# back tracking
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]]
return sum(odd) # game start with odd turn
95. 1244. Design A Leaderboard
- HashMap + SortedList
- Medium
- O(logN) for all operations
from sortedcontainers import SortedList
class Leaderboard:
def __init__(self):
self.player_score = dict()
self.scores = SortedList()
def addScore(self, playerId, score):
if playerId in self.player_score:
score += self.player_score[playerId]
self.scores.remove(self.player_score[playerId])
self.player_score[playerId] = score
self.scores.add(score)
def top(self, K):
return sum(self.scores[-K:])
def reset(self, playerId):
self.scores.remove(self.player_score[playerId])
self.player_score.pop(playerId)
96. 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])
97. [307]
98. 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]
99. 846. Hand of Straights
- HashMap + Doubly Linked List
- Medium
- O(NlogM)
class Solution:
def isNStraightHand(self, hand: List[int], k: int) -> bool:
if len(hand) % k: return False
if len(hand) < k: return False
card_freq = SortedDict()
for card in hand: card_freq[card] = card_freq.get(card, 0) + 1
while card_freq:
if len(card_freq) < k: return False
first, freq = card_freq.peekitem(0)
last, _ = card = card_freq.peekitem(k - 1)
if first != last - k + 1: return False
for card in range(first, last + 1):
# first_k = list(card_freq.islice(0, k))
# if first_k[~0] != first_k[0] + k - 1: return False
# freq = card_freq[first_k[0]]
# for card in first_k:
card_freq[card] -= freq
if card_freq[card] < 0: return False
if card_freq[card] == 0: del card_freq[card]
return True
100. 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 dy in range(n):
for dx in 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 in range(n):
for c1 in range(n):
if A[r1][c1] == 0: continue
for r2 in range(n):
for c2 in range(n):
if B[r2][c2] == 0: continue
shifts[r2-r1,c2-c1] += 1
return max(shifts.values(), default = 0)
101. 1275. Find Winner on a Tic Tac Toe Game
- Array / Design
- Easy
- O(MN)
class Player(object):
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'
102. 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)
103. 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 = occupied[0]
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
104. 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):
num = str(n)
total = 0
num_ones = 0
base = 1
remainder = 0
for i, d in enumerate(map(int, reversed(num))):
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
return total
105. 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
106. 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.
107. 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.
108. 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.
109. 588. Design In-Memory File System
- 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
110. 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.
111. 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
112. 2135. Count Words Obtained After Adding a Letter
- Hash / Bit Mask
- 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:
# sources.add(hash_word(word))
# 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('abcdefghijklmnopqrstuvwxyz')
sources = set()
for word in startWords:
for char in letters.difference(word):
sources.add(hash_word(chain(word, [char])))
for target in targetWords:
if hash_word(target) in sources:
count += 1
continue
return count
113. 886. Possible Bipartition
- BFS / DFS
- Medium
- O(V + E)
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
assignments = dict()
adj_list = defaultdict(list)
for a, b in dislikes:
adj_list[a].append(b)
adj_list[b].append(a)
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()
for b in adj_list[a]:
if b not in assignments:
assignments[b] = 1 ^ assignments[a]
dq.append(b)
if assignments[b] == assignments[a]: return False
return True
114. 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
115. 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
s.add(v)
return res + (s.issubset(s2) and not s.issubset(s1))
116. 62. Unique Paths
- DP
- Medium
- O(MN)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [1] * n
for row in range(1, m):
for col in range(1, n):
dp[col] = dp[col] + dp[col-1]
return dp[-1]
117. 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
118. [1263]
119. 1110. Delete Nodes And Return Forest
- Tree 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
120. [1642]
121. 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()
122. 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:
visited.add((nr, nc))
heappush(pq, PQItem(min(path_min, grid[nr][nc]), (nr, nc)))
123. 1088. Confusing Number II
- Backtrack
- 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)
124. 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
125. 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.
126. [149]
127. [1230]
128. 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.
129. 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 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
130. 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:
# total = 0
# for v in Counter(s).values():
# total += v * (v + 1) // 2
# return total
return sum(map(lambda v: v*v + v >> 1, Counter(s).values()))
131. 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)
132. 1377. Frog Position After T Seconds
- DFS / Bit Mask
- Hard
- O(N)
class Solution:
def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
adj_lists = defaultdict(list)
for fn, tn in edges:
adj_lists[fn].append(tn)
adj_lists[tn].append(fn)
stack = [(1, 1, 0, 1 << 1)]
while stack:
node, p, ct, visited = stack.pop()
if node == target and ct == t: return p
if ct > t: continue
jump = [nd for nd in adj_lists[node] if (1 << nd) & visited == 0] # unvisited nodes
n_op = len(jump)
for nei in jump: stack.append((nei, p / n_op, ct + 1, visited | (1 << nei)))
if node == target and n_op == 0: return p
return 0
133. 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
134. 1864. Minimum Number of Swaps to Make the Binary String Alternating
- Array
- Medium
- O(N)
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))
135. 56. Merge Intervals
- Sorting / Two Pointers / Sweep Line
- Medium
- O(N)
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
merged_intervals = []
l, r = intervals[0]
for nl, nr in intervals[1:]:
if nl > r:
merged_intervals.append((l, r))
l, r = nl, nr
elif nr > r:
r = nr
merged_intervals.append((l, r))
return merged_intervals
136. [692]
137. 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.
138. 1494. Parallel Courses II
- DP + Bit Mask
- 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
return total
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
mask = 0
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)
# if mask.bit_count() <= k:
if bin_count(mask) <= k:
# prunning, if can take all, take all
dp[state | mask] = min(dp[state | mask], dp[state] + 1)
else:
# try all subsets of size K # this is bit magic!
subset = mask
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]
139. [505]
140. 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
141. 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_lookup.add((nr, nc))
self.body.append((nr, nc))
return len(self.body) - 1
142. 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
visited.add((r, c))
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
143. [815]
144. 568. Maximum Vacation Days
- DP
- Hard
- O(N^2* K)
class Solution:
def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:
n, k = len(days), len(days[0])
dp = [[float('-inf')] * n for _ in range(k+1)]
dp[0][0] = 0
for t, i in product(range(k), range(n)):
for j, adj in enumerate(flights[i]):
if adj or i == j:
dp[t+1][j] = max(dp[t+1][j], dp[t][i] + days[j][t])
return max(dp[-1])
145. 708. Insert into a Sorted Circular Linked List
- Linked List
- Medium
- O(N)
class Solution:
def insert(self, head: 'Node', insertVal: int) -> 'Node':
if not head:
nd = Node(insertVal)
nd.next = nd
return nd
prev, curr = head, head.next
while curr != head:
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)
return head
146. [336]
147. 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
148. [850]
149. 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]
150. 1066. Campus Bikes II
- Bit Mask / DP
- Medium
- O(N*2^N)
class Solution:
def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
dist = [[0] * len(bikes) for _ in range(len(workers))]
for i, p1 in enumerate(workers):
for j, p2 in enumerate(bikes):
dist[i][j] = abs(p2[0] - p1[0]) + abs(p2[1] - p1[1])
INF = 2 ** 32
dp = [[INF] * (1 << len(bikes)) for _ in range(len(workers) + 1)]
dp[0][0] = 0
for i in range(len(workers)):
for j in range(len(bikes)):
for bit in range((1<<len(bikes))):
if bit & 1 << j: continue
mask = bit | 1 << j
dp[i+1][mask] = min(
dp[i+1][mask],
dp[i][bit] + dist[i][j]
)
return min(dp[-1])
151. 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:
self.add(start)
self.add(end)
return True
return False
152. 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
153. 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
154. 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)]
155. 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):
count = 0
for r in range(len(board)):
for c in range(len(board[r])):
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
156. 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)
157. [1888]
158. [317]
159. [809]
160. 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
161. 847. Shortest Path Visiting All Nodes
- BFS / Bit Mask
- 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 = [(node, 1 << node) for node in range(n)]
seen = set(queue)
steps = 0
while queue:
next_queue = []
for i in range(len(queue)):
node, mask = queue[i]
for neighbor in graph[node]:
next_mask = mask | (1 << neighbor)
if next_mask == ending_mask:
return 1 + steps
if (neighbor, next_mask) not in seen:
seen.add((neighbor, next_mask))
next_queue.append((neighbor, next_mask))
steps += 1
queue = next_queue
162. [1531]
163. 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:
tried.add(state)
res = dfs(candidate + str(i), tried)
if res: return res
tried.remove(state)
return dfs("0" * n, set(["0" * n]))
164. 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:
adj_list[p].append(c)
taken = set()
prereq = set()
order = deque()
def dfs_has_cycle(course):
if course in taken: return False
if course in prereq: return True
prereq.add(course)
for next_course in adj_list[course]:
if dfs_has_cycle(next_course): return True
taken.add(course)
prereq.discard(course)
order.appendleft(course)
return False
for course in range(numCourses):
if dfs_has_cycle(course): return []
return order
165. 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
166. 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 = {None: 0}
dec_length = {None: 0}
while stack:
node, post = stack.pop()
if post == 0:
stack.append((node, 1))
for child in node.left, node.right:
if child is None: continue
stack.append((child, 0))
else:
left_inc = 1 + inc_length.get(node.left, 0) * (node.left is not None and node.val == node.left.val - 1)
left_dec = 1 + dec_length.get(node.left, 0) * (node.left is not None and node.val == node.left.val + 1)
right_inc = 1 + inc_length.get(node.right, 0) * (node.right is not None and node.val == node.right.val - 1)
right_dec = 1 + dec_length.get(node.right, 0) * (node.right is not None and node.val == node.right.val + 1)
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
167. 1094. Car Pooling
- Sorting / Sweep
- 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
168. 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]
169. 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)
170. [621]
171. 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]:
adj_list = defaultdict(set)
for a, b in edges:
adj_list[a].add(b)
adj_list[b].add(a)
subtree_sum = [0] * n
subtree_size = [1] * n
# post order to compute subtree size and subtree sum
stack = [(0, None, 0)]
while stack:
node, parent, post = stack.pop()
if post == 0:
stack.append((node, parent, 1))
for child in adj_list[node]:
if child == parent: continue
stack.append((child, node, 0))
continue
subtree_size[node] = sum(subtree_size[child] for child in adj_list[node] if child != parent) + 1
subtree_sum[node] = sum(subtree_sum[child] + subtree_size[child] for child in adj_list[node] if child != parent)
def dfs2(node = 0, parent = None):
for child in graph[node]:
if child != parent:
ans[child] = ans[node] - count[child] + N - count[child]
dfs2(child, node)
# pre order to compute dist sum, here we are reusing the subtree_sum, array, it works because it is preorder
stack = [(0, None)]
while stack:
node, parent = stack.pop()
for child in adj_list[node]:
if child == parent: continue
subtree_sum[child] = subtree_sum[node] - subtree_size[child] + n - subtree_size[child]
stack.append((child, node))
return subtree_sum
172. 1197. Minimum Knight Moves
- DFS + Memoization
- Medium
- O(X + Y)
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)
173. 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
174. 940. Distinct Subsequences II
- DP
- Hard
- O(N)
f(i) = number of distinct non-empty subsequences ending at s[i]
Relation: f(i) = 2 * f(i-1) - f(last_loc(char_at(i))
|every subsequence before without s[i] |every subsequence before ended at s[j] where s[j] is same as s[i]
|every subsequence before with s[i] |
| |-deduplicate
|-neccessary addtion
class Solution:
def distinctSubseqII(self, s: str) -> int:
dp = [1]
last_seen = dict()
for i, char in enumerate(s):
dp.append(dp[-1] * 2)
if char in last_seen:
dp[-1] -= dp[last_seen[char]]
last_seen[char] = i
return (dp[-1] - 1) % (10 ** 9 + 7)
175. [222]
176. [542]
177. 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
178. 261. Graph Valid Tree
- DFS
- Medium
- O(N)
Should be a connected graph with all nodes in a single component and without any circle.
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
adj_lists = [set() for _ in range(n)]
for a, b in edges:
adj_lists[a].add(b)
adj_lists[b].add(a)
stack = [0]
visited = set()
while stack:
node = stack.pop()
if node in visited: return False
visited.add(node)
for nei in adj_lists[node]:
adj_lists[nei].discard(node)
stack.append(nei)
return len(visited) == n
179. [1483]
180. 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
181. 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
182. 1706. Where Will the Ball Fall
- Array
- Medium
- O(MN)
class Solution:
def findBall(self, grid: List[List[int]]) -> List[int]:
nrow, ncol = len(grid), len(grid[0])
def movedown(c):
for r in range(nrow):
nc = c + grid[r][c]
if nc < 0 or nc >= ncol or grid[r][c] != grid[r][nc]: return -1
c = nc
return c
result = [movedown(c) for c in range(ncol)]
return result
183. 1514. Path with Maximum Probability
- Priority Queue
- Medium
- O(V+E)
class Solution:
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
adj_list = defaultdict(list)
for (f, t), p in zip(edges, succProb):
adj_list[f].append((t, p))
adj_list[t].append((f, p))
visited = [False for _ in range(n)]
max_heap = [(-1, start)] # heap item <-1 * prob, node>
# search
while max_heap:
prob, node = heappop(max_heap)
if node == end: return -prob
visited[node] = True
for nex_node, add_prob in adj_list[node]:
if visited[nex_node]: continue
heappush(max_heap, (prob * add_prob, nex_node))
return 0
184. 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),(r-1,c),(r,c+1),(r,c-1)):
if not (nrow > nr >= 0 <= nc < ncol and rooms[nr][nc] > d + 1): continue
rooms[nr][nc] = d + 1
queue.append((nr, nc, d + 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. [767]
187. 298. Binary Tree Longest Consecutive Sequence
- DFS
- Medium
- O(N)
class Solution:
def longestConsecutive(self, root: Optional[TreeNode]) -> int:
max_length = 1
stack = [(root, 1)]
while stack:
node, length = stack.pop()
for child in node.left, node.right:
if not child: continue
new_length = 1 + length * (node.val + 1 == child.val)
stack.append((child, new_length))
max_length = max(max_length, new_length)
return max_length
188. [490]
189. [662]
190. [1673]
191. [947]
192. 64. Minimum Path Sum
- DP
- Medium
- O(MN)
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = grid[0].copy()
for i in range(1, n):
dp[i] += dp[i-1]
for r in range(1, m):
n_dp = dp.copy()
n_dp[0] += grid[r][0]
for c in range(1, n):
n_dp[c] = min(dp[c], n_dp[c-1]) + grid[r][c]
dp = n_dp
return dp[-1]
for r in range(m):
for c in range(n):
if r == 0:
dp[r][c] = sum([grid[0][cc] for cc in range(c + 1)])
elif c == 0:
dp[r][c] = sum([grid[rr][0] for rr in range(r + 1)])
else:
dp[r][c] = min(dp[r - 1][c] + grid[r][c], dp[r][c - 1] + grid[r][c])
return dp[m - 1][n - 1]
193. 695. Max Area of Island
- DFS / BFS / Union Find
- Medium
- O(MN)
Find the size of the largest connected components
class Solution:
def maxAreaOfIsland(self, grid):
nrow, ncol = len(grid), len(grid[0])
def dfs(r, c):
stack = [(r, c)]
size = 0
while stack:
r, c = stack.pop()
if (r, c) in visited: continue
size += 1
visited.add((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 grid[nr][nc] == 1:
stack.append((nr, nc))
return size
max_size = 0
visited = set()
for r in range(nrow):
for c in range(ncol):
if (r, c) in visited or grid[r][c] == 0: continue
max_size = max(max_size, dfs(r, c))
return max_size
194. 919. Complete Binary Tree Inserter
- BFS / Queue
- Medium
- O(N)
class CBTInserter:
def __init__(self, root: Optional[TreeNode]):
self.root = root
self.queue = queue = deque([root])
while queue[0].left and queue[0].right:
node = queue.popleft()
queue.extend([node.left, node.right])
if queue[0].left:
queue.append(queue[0].left)
def insert(self, val: int) -> int:
queue = self.queue
node = TreeNode(val)
p_val = queue[0].val
if queue[0].left is None:
queue[0].left = node
else:
queue[0].right = node
queue.popleft()
queue.append(node)
return p_val
def get_root(self) -> Optional[TreeNode]:
return self.root
195. 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.
196. [1024]
197. 894. All Possible Full Binary Trees
- Backtracking
- 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
198. 720. Longest Word in Dictionary
- Trie
- Medium
- O(NW)
class Trie:
class TrieNode(defaultdict):
def __init__(self):
super().__init__(Trie.TrieNode)
self.eow = False
def __init__(self):
self.root = Trie.TrieNode()
self.root.eow = True
def insert(self, word):
node = self.root
for char in word: node = node[char]
node.eow = True
class Solution:
def longestWord(self, words: List[str]) -> str:
trie = Trie()
for word in words: trie.insert(word)
candidate, l = [], 0
tour = collections.deque([(trie.root, [''])])
while tour:
node, path = tour.pop()
if not node.eow: continue
if len(path) >= l:
candidate = path
l = len(path)
for char in string.ascii_lowercase:
if char in node:
tour.append((node[char], path + [char]))
return ''.join(candidate)
199. [403]
200. [710]
201. 721. Accounts Merge
- DFS / UnionFind
- Medium
- O(NlogN)
Find connected components. Sorted component to the name.
class UnionFind(object):
def __init__(self, n):
self.ids = list(range(n))
def find(self, i):
while i != self.ids[i]:
self.ids[i] = self.ids[self.ids[i]]
i = self.ids[i]
return i
def union(self, p, q):
p, q = self.find(p), self.find(q)
self.ids[p] = self.ids[q]
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
# email to name mapping
email_to_name = dict()
for account in accounts:
name = account[0]
for email in account[1:]:
email_to_name[email] = name
# get email to int id mapping
email_to_ids = {email: idx for idx, email in enumerate(email_to_name.keys())}
n = len(email_to_ids)
# union the nodes
uf = UnionFind(n)
for account in accounts:
for email in account[2:]:
uf.union(email_to_ids[account[1]], email_to_ids[email])
# gather the connected components
clusters = defaultdict(list)
for email in email_to_name:
clusters[uf.find(email_to_ids[email])].append(email)
# construct merged accounts
result = []
for emails in clusters.values():
result.append([email_to_name[emails[0]]] + sorted(emails))
return result
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
email_to_name = dict()
adj_list = dict()
for account in accounts:
name = account[0]
e1 = account[1]
adj_list.setdefault(e1, set())
email_to_name[e1] = name
for e2 in account[2:]:
adj_list[e1].add(e2)
adj_list.setdefault(e2, set()).add(e1)
email_to_name[e2] = name
componenets = dict()
visited = set()
for email in adj_list:
if email in visited: continue
stack = [email]
component = set()
while stack:
e1 = stack.pop()
component.add(e1)
for e2 in adj_list[e1]:
if e2 in component: continue
stack.append(e2)
componenets[e1] = sorted(component)
visited.update(component)
results = []
for email, sorted_emails in componenets.items():
result = [email_to_name[email]] + sorted_emails
results.append(result)
return results
202. 1631. Path With Minimum Effort
- Priority Queue
- 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**31] * 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:
efforts[rr][cc] = next_effort
heapq.heappush(pq, (next_effort, rr, cc))
203. 324. Wiggle Sort II
- Sorting
- Medium
- O(N)
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
n = len(nums)
m = (n + 1) // 2
mid = nlargest(m, nums)[~0] # use quickselect for linear time median finding
to_idx = lambda i: (1 + 2 * i) % (n | 1)
def swap(i, j): nums[i], nums[j] = nums[j], nums[i]
# no virtual index
r, l = n - 1 if n & 1 else n - 2, 1
k = 0
while k < n:
if nums[k] < mid and (k < r or k & 1): # even positions
swap(k, r)
r -= 2
elif nums[k] > mid and (l < k or not(k & 1)):
swap(k, l)
l += 2
else:
k += 1
# # virtual index
# i, j, k = 0, n-1, 0
# while k <= j:
# print(i, k, j, to_idx(i), to_idx(k), to_idx(j))
# if nums[to_idx(k)] > mid:
# swap(to_idx(k), to_idx(i))
# i+=1
# k+=1
# elif nums[to_idx(k)] < mid:
# swap(to_idx(k), to_idx(j))
# j-=1
# else:
# k+=1
204. 1325. Delete Leaves With a Given Value
- Postorder traversal
- Medium
- O(N)
Do postorder travgersal because if we delete a leaf node, it’s parent can become a leaf node itself. Build the parent pointers incase we need to delete node from its parent.
class Solution:
def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
sentinel = TreeNode(val=None, left=root)
parents = dict()
stack = [(sentinel, 0)]
while stack:
node, post = stack.pop()
if post:
if not (node.left or node.right) and node.val == target:
parent = parents[node]
if parent.left == node: parent.left = None
if parent.right == node: parent.right = None
else:
stack.append((node, 1))
for child in node.left, node.right:
if not child: continue
parents[child] = node
stack.append((child, 0))
return sentinel.left
205. 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"
206. 951. Flip Equivalent Binary Trees
- DFS
- Medium
- O(N)
class Solution:
def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
if root1 is None and root2 is None: return True
if root1 is None or root2 is None: return False
if root1.val != root2.val: return False
return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or \
(self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))
def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
def canonical_preorder(root):
stack = [root]
order = []
while stack:
node = stack.pop()
if node is None:
order.append(None)
continue
order.append(node.val)
L = -1 if node.left is None else node.left.val
R = -1 if node.right is None else node.right.val
if L < R: stack.extend([node.left, node.right])
else: stack.extend([node.right, node.left])
return order
o1, o2 = map(canonical_preorder, (root1, root2))
return o1 == o2
207. 315. Count of Smaller Numbers After Self
- Sorting
- Hard
- O(NlogN)
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
A = SortedList()
result = deque()
for num in reversed(nums):
result.appendleft(A.bisect_left(num))
A.add(num)
return result
208. 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(l-1)
return S[start: start + l - 1]
209. [236]
210. 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
211. 34. Find First and Last Position of Element in Sorted Array
- Binary Search
- Medium
- O(logN)
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binary_search_left(arr, t):
l, h = 0, len(arr)
while l < h:
m = (h + l) // 2
if arr[m] < t: l = m + 1
else: h = m
return l
def binary_search_right(arr, t):
l, h = 0, len(arr)
while l < h:
m = (h + l) // 2
if arr[m] <= t: l = m + 1
else: h = m
return l - 1
l, r = binary_search_left(nums, target), binary_search_right(nums, target)
return [l, r] if r >= l else [-1, -1]
212. [1042]
213. 250. Count Univalue Subtrees
- DFS
- Medium
- O(N)
class Solution:
def countUnivalSubtrees(self, root: TreeNode) -> int:
self.count = 0
def dfs(node):
is_uni = True
for child in [node.left, node.right]:
if not child: continue
is_uni &= dfs(child) and child.val == node.val
self.count += is_uni
return is_uni
if root: dfs(root)
return self.count
214. 221. Maximal Square
- DP
- Medium
- O(MN)
dp(i, j) is the length of the side with bottom right corner at M[r, c] dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
nrow, ncol = len(matrix), len(matrix[0])
dp = [[0] * (ncol + 1) for _ in range(nrow + 1)]
maximum = 0
for r in range(1, nrow + 1):
for c in range(1, ncol + 1):
if matrix[r-1][c-1] == '1':
dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1
maximum = max(maximum, dp[r][c])
return maximum ** 2
215. 218. The Skyline Problem
- Priority Queue
- Hard
- O(NlogN)
class Maxpq:
def __init__(self):
self.container = []
def front(self):
if not self.container: return 0, 2**32
t = self.container[0]
return (-t[0], t[1])
def push(self, t):
heapq.heappush(self.container, (-t[0], t[1]))
def pop(self):
heapq.heappop(self.container)
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
events = []
closing_events = set()
for l, r, h in buildings:
events.append((l, h, r))
closing_events.add((r, 0, 0))
events += list(closing_events)
events.sort(key=lambda x: [x[0], -x[1]])
skyline, pq = [], Maxpq()
for x, h, r in events:
# make sure tallest building is still valid
while x >= pq.front()[1]: pq.pop()
if h: pq.push((h, r))
if not skyline or skyline[-1][1] != pq.front()[0]:
skyline.append([x, pq.front()[0]])
return skyline
216. 1504. Count Submatrices With All Ones
- Stack
- Medium
- O(MN)
Histogram.
class Solution:
def numSubmat(self, mat: List[List[int]]) -> int:
nrow, ncol = len(mat), len(mat[0])
for r in range(1, nrow):
for c in range(ncol):
if mat[r][c]: mat[r][c] += mat[r-1][c]
ans = 0
for row in mat:
stack = []
cnt = 0
for c in range(ncol):
while stack and row[stack[-1]] > row[c]:
j = stack.pop()
k = stack[-1] if stack else -1
cnt -= (row[j] - row[c]) * (j - k)
cnt += row[c]
ans += cnt
stack.append(c)
return ans
217. 71. Simplify Path
- Stack
- Medium
- O(N)
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
for p in path.split("/"):
if p == "..":
if stack:
stack.pop()
elif p and p != '.':
stack.append(p)
return '/' + '/'.join(stack)
218. 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).
219. 130. Surrounded Regions
- DFS
- Medium
- O(MN)
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
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
safe.add((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 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'
220. 1570. Dot Product of Two Sparse Vectors
- Design
- Medium
- O(N) Construct, O(L) compute
Use key, value pair for sparse vector.
class SparseVector:
def __init__(self, nums: List[int]):
self.indices = []
self.values = []
for idx, num in enumerate(nums):
if num == 0: continue
self.indices.append(idx)
self.values.append(num)
def __len__(self): return len(self.indices)
# Return the dotProduct of two sparse vectors
def dotProduct(self, vec: SparseVector) -> int:
product = 0
l1, l2 = 0, 0
while l1 < len(self) and l2 < len(vec):
if self.indices[l1] == vec.indices[l2]:
product += self.values[l1] * vec.values[l2]
l1 += 1
l2 += 1
elif self.indices[l1] < vec.indices[l2]:
l1 += 1
elif self.indices[l1] > vec.indices[l2]:
l2 += 1
return product
221. 360. Sort Transformed Array
- Binary Search / Array / Math
- Medium
- O(N)
class Solution:
def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
if not nums: return
def f(x): return a * x ** 2 + b * x + c
n = len(nums)
if a == 0:
if b > 0: return [f(x) for x in nums]
if b < 0: return [f(x) for x in reversed(nums)]
else: return [c] * n
# find mid point
p = - b / (2 * a)
l, h = 0, n - 1
while l < h:
mid = (l + h) // 2
if nums[mid] > p: h = mid
else: l = mid + 1
loc = l
output = deque()
if a > 0: l1, l2 = nums[:loc][::-1], nums[loc:]
else: l1, l2 = nums[:loc], nums[loc:][::-1]
l1 = deque([f(x) for x in l1])
l2 = deque([f(x) for x in l2])
while l1 and l2:
if l1[0] < l2[0]: output.append(l1.popleft())
else: output.append(l2.popleft())
return output + l1 + l2
222. 1352. Product of the Last K Numbers
- Prefix Sum
- Medium
- O(1)
class ProductOfNumbers:
def __init__(self):
self.prefix_prods = [1]
def add(self, num: int) -> None:
if num == 0: self.prefix_prods = [1]
else: self.prefix_prods.append(self.prefix_prods[-1] * num)
def getProduct(self, k):
if k >= len(self.prefix_prods): return 0
return self.prefix_prods[-1] // self.prefix_prods[~k]
223. 427. Construct Quad Tree
- Recurssion
- Medium
- O(N^2)
class Solution:
def construct(self, grid: List[List[int]]) -> 'Node':
def build(r1, c1, r2, c2, g):
if r1 > r2 or c1 > c2: return None
isLeaf = all(g[i][j] == g[r1][c1] for i in range(r1, r2+1) for j in range(c1, c2+1))
if isLeaf: return Node(g[r1][c1], True, None, None, None, None)
rowMid, colMid = (r1 + r2) // 2, (c1 + c2) // 2
return Node(
False,
False,
build(r1, c1, rowMid, colMid, g), # top left
build(r1, colMid + 1, rowMid, c2, g), # top right
build(rowMid + 1, c1, r2, colMid, g), # bottom left
build(rowMid + 1, colMid + 1, r2, c2, g) # bottom right
)
return build(0, 0, len(grid)-1, len(grid[0]) - 1, grid)
224. 337. House Robber III
- DFS
- Medium
- O(N)
Postorder traversal, as we need to figure out the maximum value from subtrees rooted at each children under two conditions: 1. the node is robbed 2. the node is not robbed
class Solution:
def rob(self, root: TreeNode) -> int:
values = {None: (0, 0)}
stack = [(root, False)]
while stack:
node, post = stack.pop()
if node is None: continue
if post:
values[node] = (
node.val + values[node.left][1] + values[node.right][1],
max(values[node.left]) + max(values[node.right])
)
else:
stack.extend([(node, True), (node.left, False), (node.right, False)])
return max(values[root])
225. 632. Smallest Range Covering Elements from K Lists
- Priority Queue
- Hard
- O(KNlogK)
class Solution:
def smallestRange(self, nums: List[List[int]]) -> List[int]:
K = len(nums)
pq = []
r = nums[0][0]
for i in range(len(nums)):
num, index = nums[i][0], 0
heappush(pq, (num, index, i))
r = max(r, num)
left, right = pq[0][0], r
min_window_size = right - left
while len(pq) == K:
l = pq[0][0]
window_size = r - l
if window_size < min_window_size: min_window_size, left, right = window_size, l, r
num, index, list_id = heappop(pq)
if index + 1 < len(nums[list_id]):
r = max(r, nums[list_id][index + 1])
heappush(pq, (nums[list_id][index + 1], index + 1, list_id))
return left, right
226. 731. My Calendar II
- SortedList
- Medium
- O(N)
from sortedcontainers import SortedList
class MyCalendarTwo(SortedList):
def book(self, start, end):
self.update([(start, 1), (end, -1)])
bookings = 0
for time, event in self:
bookings += event
if bookings == 3:
self.remove((start, 1))
self.remove((end, -1))
return False
return True
227. [433]
228. 686. Repeated String Match
- KMP
- Medium
- O(N)
def kmp_table(s):
m = len(s)
table, j = [0, 0], 0
for i in range(1, m):
while j > 0 and s[i] != s[j]: j = table[j]
if s[i] == s[j]: j += 1
table.append(j)
return table
class Solution:
def repeatedStringMatch(self, a: str, b: str) -> int:
table = kmp_table(b)
i, j = 0, 0
while i < len(a):
while j < len(b) and a[(i+j) % len(a)] == b[j]: j+= 1
if j == len(b): return (i + j - 1) // len(a) + 1
j = table[j]
i += max(1, j - table[j])
return -1
229. [375]
230. 241. Different Ways to Add Parentheses
- DP
- Medium
- O(N * 2^N)
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
nums, ops = [], []
num = 0
for c in expression:
if c.isdigit(): num = 10 * num + int(c)
else:
ops.append(c)
nums.append(num)
num = 0
nums.append(num)
@cache
def top_down(l, r):
if l == r: return [nums[l]]
result = []
for k in range(l, r):
result.extend([
eval(f"l_val {ops[k]} r_val")
for l_val, r_val in product(
top_down(l, k),
top_down(k + 1, r)
)
])
return result
total = top_down(0, len(nums) - 1)
return total
231. 551. Student Attendance Record I
- String
- Easy
- O(N)
class Solution:
def checkRecord(self, s: str) -> bool:
a_count = l_strike = 0
for i, v in enumerate(s):
a_count += v == 'A'
if a_count >= 2: return False
l_strike = l_strike + 1 if v == 'L' else 0
if l_strike == 3: return False
return True
232. 202. Happy Number
- Two Pointers / Floyd’s algorithm’
- Easy
- O(logN)
class Solution:
def isHappy(self, n: int) -> bool:
def get_next(number):
sum_squares = 0
while number:
number, digit = divmod(number, 10)
sum_squares += digit ** 2
return sum_squares
slow = n
fast = get_next(n)
while fast != 1 and slow != fast:
slow = get_next(slow)
fast = get_next(get_next(fast))
return fast == 1
233. 1366. Rank Teams by Votes
- Sorting
- Medium
- O(NlogN)
class Solution:
def rankTeams(self, votes: List[str]) -> str:
count = {v: [0] * len(votes[0]) + [v] for v in votes[0]}
for vote in votes:
for i, v in enumerate(vote):
count[v][i] -= 1
return ''.join(sorted(votes[0], key=count.get))
count = {v: [0] * len(votes[0]) + [ord('z') - ord(v)] for v in votes[0]}
for vote in votes:
for i, v in enumerate(vote):
count[v][i] += 1
return ''.join(sorted(votes[0], key=count.get, reverse=True))
234. 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
235. 1624. Largest Substring Between Two Equal Characters
- HashSet
- Easy
- O(N)
class Solution:
def maxLengthBetweenEqualCharacters(self, s: str) -> int:
max_len = -1
first = dict()
for i, c in enumerate(s):
if c not in first: first[c] = i
else: max_len = max(max_len, i - first[c] - 1)
return max_len
236. 57. Insert Interval
- Two Pointers
- Medium
- O(N)
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
if not intervals: return [newInterval]
if not newInterval: return intervals
nl, nr = newInterval
n = len(intervals)
if intervals[-1][1] < nl: return intervals + [newInterval]
if intervals[0][0] > nr: return [newInterval] + intervals
def intersect(l1, r1, l2, r2):
l = max(l1, l2)
r = min(r1, r2)
return l <= r
output, l, r = [], None, None
for i, itv in enumerate(intervals):
il, ir = itv
if intersect(il, ir, nl, nr):
if l is None: l = min(il, nl)
if r is None: r = max(ir, nr)
l, r = min(l, il), max(r, ir)
else:
if r is not None:
output.append([l, r])
l, r = None, None
if i and intervals[i - 1][1] < nl and nr < il:
output.append(newInterval)
output.append(itv)
if r is not None:
output.append([l, r])
return output
237. 719. Find K-th Smallest Pair Distance
- Binary Search
- Hard
- O(NlogN)
class Solution:
def smallestDistancePair(self, nums, k):
def possible(guess):
count, l = 0, 0
for r, x in enumerate(nums):
while x - nums[l] > guess:
l += 1
count += r - l
return count >= k
nums.sort()
lo, hi = 0, nums[-1] - nums[0]
while lo < hi:
mid = (lo + hi) // 2
if possible(mid): hi = mid
else: lo = mid + 1
return lo
238. 399. Evaluate Division
- DFS / Union Find(UF is better)
- Medium
- O((M+N)logN)
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
# build graph
edges = defaultdict(defaultdict)
for (num, denum), value in zip(equations, values):
edges[num][denum] = value
edges[denum][num] = 1 / value
for num in edges.keys(): edges[num][num] = 1
def dfs(current, target, used):
if current not in edges: return -1
if target in edges[current]: return edges[current][target]
used.add(current)
for next_ in filter(lambda x: x not in used, edges[current]):
result = dfs(next_, target, used)
if result != -1: return edges[current][next_] * result
return -1
return [dfs(*query, set()) for query in queries]
def calcEquation(self, equations, values, queries):
root = {}
# xr = x/parent(x), pr = parent(x)/root(x), update xr to xr*pr = x/root(x)
def find(x):
p, xr = root.setdefault(x, (x, 1.0))
if x != p:
r, pr = find(p)
root[x] = (r, xr*pr)
return root[x]
# if root(x) = root(y), equations "x / y" doable as (x/root(x)) / (y/root(y)) = xr / yr
def union(x, y, ratio):
px, xr, py, yr = *find(x), *find(y)
if not ratio:
return xr / yr if px == py else -1.0
if px != py:
root[px] = (py, yr/xr*ratio)
for (x, y), v in zip(equations, values):
union(x, y, v)
return [union(x, y, 0) if x in root and y in root else -1.0 for x, y in queries]
239. 889. Construct Binary Tree from Preorder and Postorder Traversal
- Tree Traversal
- Medium
- O(N)
Follow preorder and postorder at the same time to create nodes. Use a stack to keep track of nodes. Attach newly created nodes to top of stack to maintain pre-order. Pop nodes off the stack when it matches the postorder node value to maintain post-order
class Solution:
def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
stack = []
j = 0
for v in preorder:
node = TreeNode(v)
if stack:
while stack[-1].val == postorder[j]:
stack.pop()
j += 1
if not stack[-1].left:
stack[-1].left = node
else:
stack[-1].right = node
stack.append(node)
return stack[0]
240. 582. Kill Process
- BFS / DFS
- Medium
- O(N)
Create parent pid to children pids mapping. Then run DFS/BFS from given pid.
class Solution:
def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
children = defaultdict(list)
for c_id, p_id in zip(pid, ppid): children[p_id].append(c_id)
killed = []
stack = [kill]
while stack:
p_id = stack.pop()
killed.append(p_id)
stack.extend(children[p_id])
return killed
241. 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
return total
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
242. 437. Path Sum III
- Prefix Sum on Tree / DFS
- Medium
- O(N)
class Solution:
def pathSum(self, root: TreeNode, target: int) -> bool:
if not root: return 0
self.total = 0
prefix_sum = defaultdict(int)
prefix_sum[0] = 1
def dfs(node, accum):
self.total += prefix_sum.get(accum - target, 0)
prefix_sum[accum] += 1
for child in node.left, node.right:
if child is None: continue
dfs(child, accum + child.val)
prefix_sum[accum] -= 1
dfs(root, root.val)
return self.total
243. 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.
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []
for asteroid in asteroids:
while stack and asteroid < 0 < stack[-1]: # while we have collision to handle
if - asteroid > stack[-1]:
stack.pop()
continue
elif - asteroid == stack[-1]:
stack.pop()
break
else:
stack.append(asteroid)
return stack
244. 460. LFU Cache
- Design / HashMap / Doubly Linked List
- Hard
- O(1)
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.freq_to_key = defaultdict(OrderedDict)
self.key_to_freq = defaultdict(int)
self.min_freq = 1
def get(self, key: int) -> int:
if key not in self.key_to_freq: return -1
freq = self.key_to_freq[key]
self.key_to_freq[key] = freq + 1
value = self.freq_to_key[freq][key]
del self.freq_to_key[freq][key]
self.freq_to_key[freq+1][key] = value
if self.min_freq == freq and not self.freq_to_key[freq]: self.min_freq += 1
return value
def put(self, key: int, value: int) -> None:
if key in self.key_to_freq:
self.get(key)
self.freq_to_key[self.key_to_freq[key]][key] = value
return
self.capacity -= 1
self.key_to_freq[key] = 1
self.freq_to_key[1][key] = value
if self.capacity < 0:
self.capacity += 1
k, v = self.freq_to_key[self.min_freq].popitem(False)
del self.key_to_freq[k]
self.min_freq = 1
245. 677. Map Sum Pairs
- Trie
- Medium
- O(L^2)
class TrieNode(defaultdict):
def __init__(self):
self.default_factory = TrieNode
self.val = 0
class MapSum:
def __init__(self):
""" Initialize your data structure here. """
self.root = TrieNode()
self.map = defaultdict(int)
def insert(self, key: str, val: int) -> None:
delta = val - self.map[key]
self.map[key] = val
node = self.root
for char in key:
node = node[char]
node.val += delta
def sum(self, prefix: str) -> int:
node = self.root
for char in prefix:
if char not in node: return 0
node = node[char]
return node.val
246. 1252. Cells with Odd Values in a Matrix
- Counting
- Easy
- O(N)
class Solution:
def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
total = 0
row_incs, col_incs = [0] * m, [0] * n
for r, c in indices:
row_incs[r] ^= 1
col_incs[c] ^= 1
for r in range(m):
for c in range(n):
total += (row_incs[r] + col_incs[c]) & 1
return total
247. 312. Burst Balloons
- DP
- Hard
- O(N^3)
class Solution:
def maxCoins(self, nums: List[int]) -> int:
nums = [1] + nums + [1]
n = len(nums)
dp = [[0] * n for _ in range(n)]
for l in range(n - 2, -1, -1):
for r in range(l + 2, n):
dp[l][r] = max(nums[l] * nums[i] * nums[r] + dp[l][i] + dp[i][r]
for i in range(l + 1, r))
return dp[0][-1]
248. [334]
249. [1162]
250. 205. Isomorphic Strings
- HashMap
- Easy
- O(N)
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
m = dict()
for sc, tc in zip(s, t):
if m.get(sc, tc) != tc: return False
m[sc] = tc
return len(s) == len(t) and max(Counter(m.values()).values()) == 1
251. 1049. Last Stone Weight II
- DP
- Medium
- O(N*Sum(stones))
Equivlant to find the partition such that two sum are close to each other as much as possible.
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
dp = {0}
total = sum(stones)
for a in stones:
dp |= {a + i for i in dp}
return min(abs(total - i - i) for i in dp)
252. 459. Repeated Substring Pattern
- String / KMP
- Easy
- O(N)
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
# return s in (s[1:] + s[:-1])
n = len(s)
table, j = [0, 0], 0
for i in range(1, n):
while j > 0 and s[i] != s[j]: j = table[j]
if s[i] == s[j]: j += 1
table.append(j)
return table[-1] and table[-1] % (n - table[-1]) == 0
253. 968. Binary Tree Cameras
- Greedy / Postorder traversal
- Hard
- O(N)
For a leaf node, it is always better to use a camera at it’s parent node to cover it. Thus greedy from bottom up.
class Solution:
def minCameraCover(self, root: TreeNode) -> int:
covered = {None}
num_camera = 0
stack = [(root, None, 0)]
while stack:
node, parent, post = stack.pop()
if node is None: continue
if post:
if (parent is None and node not in covered) or \
(node.left not in covered or node.right not in covered):
num_camera += 1
covered.update([node, parent, node.left, node.right])
else:
stack.extend([(node, parent, 1), (node.left, node, 0), (node.right, node, 0)])
return num_camera
254. 787. Cheapest Flights Within K Stops
- Graph / DP
- Hard
- O(KE)
DP with expansion on middle city.
f(i,j) the cheapest price to fly from src to city j with i flights.
f(K+1,dst) is our solution
relation f(i,j) = min(f(i-1,k) + price from k to j for all k) # , f(i-1,j))
base case f(0,j) = INF if j != src else 0
f(i,src) = 0
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
INF = float('inf')
dp = [[INF] * n for _ in range(K+2)]
for i in range(K+2):
dp[i][src] = 0
for i in range(1, K+2):
for u, v, w in flights:
dp[i][v] = min(dp[i-1][u] + w , dp[i][v])
return dp[-1][dst] if dp[-1][dst] != INF else -1
255. [313]
256. 743. Network Delay Time
- BFS / DFS
- Medium
- O(V+E)
MAX = 2 ** 32
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
adj_list = defaultdict(list)
for u, v, w in times:
adj_list[u].append((v, w))
max_time = 0
time_to_node = dict()
queue = deque([(k, 0)])
while queue:
u, t = queue.popleft()
if time_to_node.get(u, MAX) <= t: continue
time_to_node[u] = t
for v, w in adj_list[u]:
queue.append((v, t + w))
if len(time_to_node) < n: return -1
return max(time_to_node.values())
257. 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
258. 348. Design Tic-Tac-Toe
- HashMap
- Medium
- O(MN)
class TicTacToe:
def __init__(self, n: int):
"""
Initialize your data structure here.
"""
self.count = Counter()
self.n = n
def move(self, row: int, col: int, player: int) -> int:
"""
Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins.
"""
for i, x in enumerate((row, col, row + col, row - col)):
self.count[i, x, player] += 1
if self.count[i, x, player] == self.n: return player
return 0
259. 17. Letter Combinations of a Phone Number
- Backtrack
- Medium
- O(2^N)
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if digits == "": return []
mapping = {
"0": "",
"1": "",
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
digits = list(digits)
results = []
def backtrack(candidate, i):
if i == len(digits):
results.append("".join(candidate))
return
for d in mapping[digits[i]]:
candidate.append(d)
backtrack(candidate, i + 1)
candidate.pop()
backtrack([], 0)
return results
260. 41. First Missing Positive
- Array
- Hard
- O(N)
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
# partition, move positive numbers before non-positive numbers
l, r = 0, len(nums) - 1
while l < r:
if nums[l] <= 0:
nums[l], nums[r] = nums[r], nums[l]
r -= 1
else:
l += 1
# edge case - no number or no postive number at all
if not nums or (r == 0 and nums[0] <= 0): return 1
# make sure r points to last postive number.
if nums[r] <= 0: r -= 1
# if there is no missing positive number nums[0:r) should be 1 to r + 1 (shuffled)
# 2nd pass: mark existing postive numbers that are <= num_max
num_max = r + 1
for i in range(r + 1):
num = abs(nums[i])
if num > num_max: continue
nums[num - 1] = -abs(nums[num - 1])
# 3rd pass: find the first missing positive number
for i in range(r + 1):
if nums[i] >= 0:
return i + 1
return num_max + 1
261. 983. Minimum Cost For Tickets
- DP
- Medium
- O(N)
class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
dp = [0] * (days[-1] + 1)
days = set(days)
for i in range(1, len(dp)):
if i in days:
dp[i] = min(
dp[max(i-1, 0)] + costs[0],
dp[max(i-7, 0)] + costs[1],
dp[max(i-30, 0)] + costs[2]
)
else:
dp[i] = dp[i-1]
return dp[-1]
262. 702. Search in a Sorted Array of Unknown Size
- Binary Search
- Medium
- O(logN)
class Solution:
def search(self, reader, target):
if reader.get(0) == target: return 0
lo, hi = 0, 1
while reader.get(hi) < target:
lo, hi = hi, hi << 1
# binary search
while lo < hi:
mid = (lo + hi) >> 1
if num := reader.get(mid) >= target:
hi = mid
else:
lo = mid + 1
num = reader.get(lo)
return lo if num == target else -1
263. 1446. Consecutive Characters
- Array
- Easy
- O(N)
class Solution:
def maxPower(self, s: str) -> int:
strike, power, curr = 0, 0, ''
for c in s:
if c == curr:
strike += 1
continue
power = max(power, strike)
curr = c
strike = 1
power = max(power, strike)
return power
def maxPower(self, s: str) -> int:
strike, power, curr = 1, 1, s[0]
for c in s[1:]:
if c == curr:
strike += 1
power = max(power, strike)
else:
curr = c
strike = 1
return power
264. 43. Multiply Strings
- Math
- Medium
- O(N)
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == '0' or num2 == '0': return '0'
stoi = {s:i for i, s in enumerate('0123456789')}
itos = {i:s for i, s in enumerate('0123456789')}
def int(x): return stoi[x]
def str(x): return itos[x]
l1, l2 = len(num1), len(num2)
results = [0] * (l1 + l2)
for i, d1 in enumerate(map(int, reversed(num1))):
for j, d2 in enumerate(map(int, reversed(num2))):
carry, reminder = divmod(d1 * d2, 10)
results[i + j] += reminder
results[i + j + 1] += carry
for i, d in enumerate(results):
carry, reminder = divmod(d, 10)
results[i] = reminder
if carry: results[i + 1] += carry
return ''.join(map(str, reversed(results))).lstrip('0')
265. [140]
266. 91. Decode Ways
- DP
- Medium
- O(N)
class Solution:
def numDecodings(self, s: str) -> int:
if not s or s[0]=='0': return 0
n = len(s)
dp = [0 for _ in range(n + 1)]
dp[0: 2] = [1, 1]
for i in range(2, n + 1):
if s[i - 1] > '0': dp[i] += dp[i - 1]
if '10' <= s[i - 2: i] <= '26': dp[i] += dp[i - 2]
return dp[-1]
267. 295. Find Median from Data Stream
- Priority Queue
- Hard
- O(loN)
class MedianFinder:
def __init__(self):
""" initialize your data structure here. """
self.max_heap = PQ("max") # smaller half
self.min_heap = PQ("min") # larger half
def addNum(self, num: int) -> None:
if len(self.max_heap) == 0 or self.max_heap.peek() >= num:
self.max_heap.push(num)
else:
self.min_heap.push(num)
#balancing max and min heap
if len(self.max_heap) < len(self.min_heap):
self.max_heap.push(self.min_heap.pop())
elif len(self.max_heap) - len(self.min_heap) == 2:
self.min_heap.push(self.max_heap.pop())
def findMedian(self) -> float:
if len(self.max_heap) > len(self.min_heap):
return self.max_heap.peek()
else:
return (self.min_heap.peek() + self.max_heap.peek()) / 2
268. 807. Max Increase to Keep City Skyline
- Array
- Medium
- O(MN)
class Solution:
def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
nrow, ncol = len(grid), len(grid[0])
rmax = list(map(max, grid))
cmax = list(map(max, zip(*grid)))
total = 0
for r in range(nrow):
for c in range(ncol):
total += min(rmax[r], cmax[c]) - grid[r][c]
return total
269. 37. Sudoku Solver
- Backtrack
- Hard
- O(9^81)
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
nrow, ncol = len(board), len(board[0])
digits = set('123456789')
not_visited = [(r, c) for r in range(9) for c in range(9) if board[r][c] == '.']
def valid_choices(r, c):
row = board[r]
col = [board[i][c] for i in range(9)]
square = [board[i][j] for i in range(r // 3 * 3, r // 3 * 3 + 3)
for j in range(c // 3 * 3, c // 3 * 3 + 3)]
choices = digits.difference(row).difference(col).difference(square)
return choices
def backtrack(board, not_visited):
if not not_visited: return True
(r, c) = not_visited.pop()
for digit in valid_choices(r, c):
board[r][c] = digit
if backtrack(board, not_visited): return True
board[r][c] = '.'
not_visited.append((r, c))
return False
backtrack(board, not_visited)
270. 1092. Shortest Common Supersequence
- DP
- Hard
- O(MN)
Find LCS between two sequence, and expand from that.
def find_lcs(s1, s2):
l1, l2 = len(s1), len(s2)
dp = [[""] * (l2 + 1) for _ in range(l1 + 1)]
for i in range(1, l1+1):
for j in range(1, l2+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + s1[i-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=len)
return dp[-1][-1]
def form(lcs, s1, s2):
scs = []
i, j = 0, 0
for c in lcs:
while s1[i] != c:
scs.append(s1[i])
i += 1
while s2[j] != c:
scs.append(s2[j])
j += 1
scs.append(c)
i += 1
j += 1
scs.extend(s1[i:])
scs.extend(s2[j:])
return "".join(scs)
class Solution:
def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
lcs = find_lcs(str1, str2)
return form(lcs, str1, str2)
271. 7. Reverse Integer
- Math
- Medium
- O(N)
INT_MIN = -2 ** 31
INT_MAX = 2 ** 31 - 1
class Solution:
def reverse(self, x: int) -> int:
if x == INT_MIN: return 0
is_negative = x < 0
if is_negative: x = 0 - x
y = 0
while x:
x, d = divmod(x, 10)
if y > INT_MAX / 10: return 0
y = 10 * y + d
return y if not is_negative else - y
272. 93. Restore IP Addresses
- Backtrack
- Medium
- O(N * 2^N)
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
def valid_ip(candidate):
if len(candidate) != 4: return
result = []
for section in candidate:
section_str = ''.join(section)
section_int = int(section_str)
if section_int > 255: return
if section_int == 0 and section_str != "0": return
if section_int != 0 and section_str[0] == "0": return
result.append(section_str)
return ".".join(result)
digits = list(s)
ips = []
def backtrack(candidate, i):
if i == len(s):
ip = valid_ip(candidate)
if ip: ips.append(ip)
return
candidate.append([digits[i]])
backtrack(candidate, i + 1)
candidate.pop()
candidate[-1].append(digits[i])
backtrack(candidate, i + 1)
candidate[-1].pop()
backtrack([[digits[0]]], 1)
return ips
273. 66. Plus One
- Math / Array
- Easy
- O(N)
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
carry = 1
for i in reversed(range(len(digits))):
carry, digits[i] = divmod(digits[i] + carry, 10)
if carry: return [1] + digits
return digits
274. 827. Making A Large Island
- DFS / Union Find
- Hard
- O(MN)
Find components, keep track of component membership and reverse mapping as well as size of components. Go through matrix again, find neighbouring unique components for each “0” loc, update running maximum.
class UnionFind:
def __init__(self, nrow, ncol):
self.parents = list(range(nrow * ncol))
self.sizes = [0] * (nrow * ncol)
self.nrow = nrow
self.ncol = ncol
def to_key(self, loc):
r, c = loc
return r * self.ncol + c
# def to_loc(self, key):
# return divmod(key, self.ncol)
def insert(self, i):
i = self.to_key(i)
if self.sizes[i] == 0:
self.sizes[i] = 1
def find(self, i):
if not isinstance(i, int): i = self.to_key(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):
self.insert(p)
self.insert(q)
root_p = self.find(p)
root_q = self.find(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 largestIsland(self, grid: List[List[int]]) -> int:
nrows, ncols = len(grid), len(grid[0])
def get_neighbors(r, c):
for nr, nc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if nrows > nr >= 0 <= nc < ncols:
yield nr, nc
uf = UnionFind(nrows, ncols)
for r, c in product(range(nrows), range(ncols)):
if not grid[r][c]: continue
uf.insert((r, c))
for nr, nc in get_neighbors(r, c):
if not grid[nr][nc]: continue
uf.union((r,c), (nr, nc))
print(uf.parents)
print(uf.sizes)
max_size = max(uf.sizes)
for r, c in product(range(nrows), range(ncols)):
if grid[r][c]: continue
neighbor_info = dict()
for loc in get_neighbors(r, c):
if uf.sizes[uf.find(loc)] == 0: continue
island_id = uf.find(loc)
neighbor_info[island_id] = uf.sizes[island_id]
max_size = max(max_size, 1 + sum(neighbor_info.values(), 0))
return max_size
275. 278. First Bad Version
- Binary Search
- Easy
- O(logN)
class Solution:
def firstBadVersion(self, n):
lo, hi = 1, n
while lo < hi:
mid = (lo + hi) >> 1
if isBadVersion(mid):
hi = mid
else:
lo = mid + 1
return lo
276. [616]
277. 852. Peak Index in a Mountain Array
- Binary Search
- Easy
- O(logN)
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
l, h = 0, len(arr) - 1
while l < h:
mid = (l + h) >> 1
if arr[mid] > arr[mid + 1]:
h = mid
else:
l = mid + 1
return l
278. 23. Merge k Sorted Lists
- Merge Sort / Priority Queue
- Hard
- O(NlogK)
class PQNode:
def __init__(self, node): self.node = node
def __lt__(self, other): return self.node.val < other.node.val
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
pq = [PQNode(head) for head in lists if head is not None]
heapq.heapify(pq)
curr = sentinel = ListNode()
while pq:
nd = heapq.heappop(pq)
curr.next, curr = nd.node, nd.node
if nd.node.next: heapq.heappush(pq, PQNode(nd.node.next))
return sentinel.next
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists: return
def merge(l1, l2):
ret = curr = ListNode(None)
while l1 and l2:
if l1.val < l2.val: curr.next, l1 = l1, l1.next
else: curr.next, l2 = l2, l2.next
curr = curr.next
curr.next = l1 if l1 else l2
return ret.next
lists = collections.deque(lists)
while len(lists) > 1:
l1 = lists.popleft()
l2 = lists.popleft()
l3 = merge(l1, l2)
lists.append(l3)
return lists.pop()
279. [332]
280. 856. Score of Parentheses
- Stack
- Medium
- O(N)
class Solution:
def scoreOfParentheses(self, S: str) -> int:
mapping = {
'((': '2*(',
'()': '1',
')(': '+',
'))': ')'
}
return eval(''.join([mapping[pair] for pair in map(lambda x:''.join(x), zip(S, S[1:]))]))
def scoreOfParentheses(self, S: str) -> int:
stack, cur = [], 0
for i in S:
if i == '(':
stack.append(cur)
cur = 0
else:
cur += stack.pop() + max(cur, 1)
return cur
281. 1101. The Earliest Moment When Everyone Become Friends
- Union Find
- Medium
- O(E)
class UnionFind:
def __init__(self, n):
self.parents = list(range(n))
self.sizes = [1] * n
self.n_components = 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 = 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_components -= 1
return True
class Solution:
def earliestAcq(self, logs: List[List[int]], n: int) -> int:
logs.sort()
uf = UnionFind(n)
for timestamp, a, b in logs:
uf.union(a, b)
if uf.n_components == 1: return timestamp
return -1
282. 3. Longest Substring Without Repeating Characters
- Sliding Window / HashSet
- Medium
- O(N)
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
window = set()
l = 0
max_size = 0
for r, char in enumerate(s):
while char in window:
window.discard(s[l])
l += 1
window.add(s[r])
max_size = max(max_size, r - l + 1)
return max_size
283. 72. Edit Distance
- DP
- Hard
- O(MN)
f(i, j) = edit distance s[:i] and t[:j].
1. f(i-1, j) + 1 delete
f(i, j) = 2. f(i, j-1) + 1 insert
3. f(i-1,j-1) s[i] == t[j] do nothing
4. f(i-1,j-1) + 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,j-1) + 1,
f(i-1,j) + 1,
f(i-1,j-1) + int(word1[i-1] != word2[j-1])
)
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[c-1] + 1,
dp[c-1] + int(char1 != char2)
)
dp = ndp
return dp[-1]
minDistance = bottom_up
284. 1095. Find in Mountain Array
- Binary Search
- Hard
- O(logN)
class Solution:
def findInMountainArray(self, target: int, arr: 'MountainArray') -> int:
n = arr.length()
lo, hi = 0, n - 1
while lo < hi:
mid = (lo + hi) >> 1
if arr.get(mid) < arr.get(mid + 1): lo = pivot = mid + 1
else: hi = mid
lo, hi = 0, pivot
while lo <= hi:
mid_num = arr.get(mid := (lo + hi) >> 1)
if mid_num == target: return mid
elif mid_num > target: hi = mid - 1
else: lo = mid + 1
lo, hi = pivot, n - 1
while lo <= hi:
mid_num = arr.get(mid := (lo + hi) >> 1)
if mid_num == target: return mid
elif mid_num > target: lo = mid + 1
else: hi = mid - 1
return - 1
285. 1730. Shortest Path to Get Food
- BFS
- Medium
- O(MN)
class Solution:
def getFood(self, grid: List[List[str]]) -> int:
nrow, ncol = len(grid), len(grid[0])
people = None
for r in range(nrow):
for c in range(ncol):
if grid[r][c] == '*':
people = (r, c)
break
if people: break
queue = deque([people])
n_steps = 0
seen = set([people])
while queue:
for _ in range(len(queue)):
r, c = queue.popleft()
if grid[r][c] == "#": return n_steps
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] !="X" and (nr, nc) not in seen:
queue.append((nr, nc))
seen.add((nr, nc))
n_steps += 1
return -1
286. 1770. Maximum Score from Performing Multiplication Operations
- DP
- Medium
- O(M^2)
class Solution:
def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
n, m = len(nums), len(multipliers)
# @cache
# def dp(l, r):
# i = l + n - r - 1
# if i == m: return 0
# s1 = dp(l + 1, r) + multipliers[i] * nums[l]
# s2 = dp(l, r - 1) + multipliers[i] * nums[r]
# return max(s1, s2)
# return dp(0, n - 1)
dp = [[0] * m for _ in range(m+1)]
for l in reversed(range(m)):
for r in range(l, m):
i = l + m - r - 1
dp[l][r] = max(
dp[l+1][r] + multipliers[i] * nums[l],
dp[l][r-1] + multipliers[i] * nums[r-m+n]
)
return dp[0][-1]
287. 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
288. 1910. Remove All Occurrences of a Substring
- KMP
- Medium
- O(M + N)
Build KMP table, when we remove an occurrence of pattern, we move the matching to previous match position in pattern before the start of this occurrence. Use two stacks, one to keep track of characters encountered. One to mark the most current consecutive match.
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
class Solution:
def removeOccurrences(self, s: str, p: str) -> str:
table = lps(p)
stack = []
matched = [0]
for i in range(len(s)):
stack.append(s[i])
j = matched[-1]
while j and s[i] != p[j]: j = table[j]
if s[i] == p[j]:
matched.append(j + 1)
else:
matched.append(0)
if matched[-1] == len(p):
for _ in range(len(p)):
matched.pop()
stack.pop()
return ''.join(stack)
289. 1525. Number of Good Ways to Split a String
- Prefix / Math
- Medium
- O(N)
Brute force is try all positions as split point. To speed up, cache prefix num unique from both directions. Then we can realize there are locations where these prefix num unique changes, we only need to consider the gap between the middle two.
class Solution:
def numSplits(self, s: str) -> int:
def prefix_num_unique(arr):
seen = set()
prefix = []
for val in arr:
seen.add(val)
prefix.append(len(seen))
return prefix
n = len(s)
left = prefix_num_unique(s)
right = prefix_num_unique(reversed(s))[::-1]
total = 0
for i in range(n-1):
if left[i] == right[i+1]:
total += 1
return total
def numSplits(self, s: str) -> int:
first_loc, last_loc = dict(), dict()
for i, c in enumerate(s):
if c not in first_loc: first_loc[c] = i
last_loc[c] = i
indices = list(first_loc.values()) + list(last_loc.values())
indices.sort()
m = len(indices) >> 1
return indices[m] - indices[m-1]
290. 1436. Destination City
- Set
- Easy
- O(N)
class Solution:
def destCity(self, paths: List[List[str]]) -> str:
return set([d for s, d in paths]).difference([s for s, d in paths]).pop()
291. 545. Boundary of Binary Tree
- Tree Traversal
- Medium
- O(N)
Find left boundry, right boundry and leaves, union them in order.
class Solution:
def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:
left_sides = [root]
node = root.left
while node:
left_sides.append(node)
node = node.left or node.right
right_sides = [root]
node = root.right
while node:
right_sides.append(node)
node = node.right or node.left
leaves = []
stack = [root]
while stack:
node = stack.pop()
if not node.left and not node.right: leaves.append(node)
stack.extend([child for child in [node.right, node.left] if child])
added = set()
boundries = []
for node in left_sides:
added.add(node)
boundries.append(node.val)
for node in leaves:
if node not in added:
boundries.append(node.val)
added.add(node)
for node in reversed(right_sides):
if node not in added:
boundries.append(node.val)
return boundries
292. 2131. Longest Palindrome by Concatenating Two Letter Words
- HashMap
- Medium
- O(N)
For a given parlindrome, we can always plug in a “XX” in the center to extend the length by two. Iterrate over the pairs, keep track of freq for “XY” and check whether we have “YX” to match it. Also keep track of “XX” case.
class Solution:
def longestPalindrome(self, words):
m = defaultdict(int)
unpaired = ans = 0
for w in words:
if w[0] == w[1]:
if m[w] > 0:
unpaired -= 1
m[w] -= 1
ans += 4
else:
m[w] += 1
unpaired += 1
else:
if m[w[::-1]] > 0: # w[::-1] -> reversed w
ans += 4
m[w[::-1]] -= 1
else:
m[w] += 1
if unpaired > 0:
ans += 2
return ans
293. 92. Reverse Linked List II
- Linked List
- Medium
- O(N)
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
if not head: return None
prev, curr = None, head
while m > 1:
prev, curr = curr, curr.next
m, n = m - 1, n - 1
tail, last = curr, prev
while n:
prev, curr.next, curr = curr, prev, curr.next
n -= 1
if last: last.next = prev
else: head = prev
tail.next = curr
return head
294. 207. Course Schedule
- Cycle Detection
- Medium
- O(V + E)
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
adj_list = [[] for _ in range(numCourses)]
for c, p in prerequisites:
adj_list[p].append(c)
taken = set()
prereq = set()
def dfs_has_cycle(course):
if course in taken: return False
if course in prereq: return True
prereq.add(course)
for next_course in adj_list[course]:
if dfs_has_cycle(next_course): return True
prereq.remove(course)
taken.add(course)
return False
for course in range(numCourses):
if dfs_has_cycle(course): return False
return True
295. 246. Strobogrammatic Number
- Two Pointers
- Easy
- O(N)
class Solution:
def isStrobogrammatic(self, num: str) -> bool:
if len(num) == 1: return num in "018"
mapping = {
'8':'8',
'0':'0',
'1':'1',
'6':'9',
'9':'6'
}
l, r = 0, len(num) - 1
while l <= r:
if num[l] not in mapping or num[r] not in mapping: return False
if mapping[num[l]] != num[r]: return False
l += 1
r -= 1
return True
296. 173. Binary Search Tree Iterator
- Tree Traversal
- Medium
- O(N)
class BSTIterator:
def __init__(self, root: TreeNode):
self.root = root
self._reset()
def _reset(self):
self.node = self.root
self.stack = []
def __iter__(self):
self._reset()
return self
def __next__(self) -> int:
""" Return the next smallest number """
while self.node:
self.stack.append(self.node)
self.node = self.node.left
self.node = self.stack.pop()
ret_val = self.node.val
self.node = self.node.right
return ret_val
next = __next__
def hasNext(self) -> bool:
""" Return whether we have a next smallest number """
return self.stack or self.node
297. 1971. Find if Path Exists in Graph
- Graph Search
- Easy
- O(V + E)
class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
adj_lists = [[] for _ in range(n)]
for f, t in edges:
adj_lists[f].append(t)
adj_lists[t].append(f)
visited = set()
stack = [source]
while stack:
node = stack.pop()
if node == destination: return True
visited.add(node)
for neighbor in adj_lists[node]:
if neighbor in visited: continue
stack.append(neighbor)
return False
298. 785. Is Graph Bipartite?
- BFS / DFS
- Medium
- O(N)
class Solution:
def isBipartite(self, graph):
assignments = dict() # node -> group
for node in range(len(graph)):
if not graph[node] or node in assignments: continue
assignments[node] = 0
to_visit = deque([node])
while to_visit:
# nd = to_visit.popleft() # bfs
nd = to_visit.pop() #dfs
group = assignments[nd]
for neighbor in graph[nd]:
if neighbor not in assignments:
assignments[neighbor] = 1 - group
to_visit.append(neighbor)
if assignments[neighbor] == group:
return False
return True
299. 259. 3Sum Smaller
- Two Pointers / Sorting
- Medium
- O(N^2)
class Solution:
def threeSumSmaller(self, nums: List[int], target: int) -> int:
if not nums or len(nums) < 3: return 0
nums.sort()
n = len(nums)
solutions = 0
for i, num1 in enumerate(nums[:-2]):
j, k = i + 1, n - 1
while j < k:
num2, num3 = nums[j], nums[k]
if num1 + num2 + num3 < target:
solutions += k - j
j += 1
else:
k -= 1
return solutions
300. [918]
301. 463. Island Perimeter
- Counting
- Easy
- O(MN)
Brute froce will be go through cell by cell, for each cell check four neighbors, only add if the side hits boundry or water. Better counting is just that only do so for left and top, as bottom and right is checked by cell below’s top check and cell to the right’s left check.
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
nrow, ncol = len(grid), len(grid[0])
perimeter = 0
for r in range(nrow):
for c in range(ncol):
if not grid[r][c]: continue
perimeter += 4
for nr, nc in [(r-1,c),(r,c-1)]:
if nrow > nr >= 0 <= nc < ncol and grid[nr][nc]:
perimeter -= 2
return perimeter
302. 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][j-1] + int(bool(t[i-1] == s[j-1])) * dp[i-1][j-1]
return dp[-1][-1]
303. 2. Add Two Numbers
- Linked list
- Medium
- O(N)
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
# init
carry = 0
ret = curr = ListNode(None)
# loop
lists = [l1, l2]
while lists or carry: # still work to do
# get digits
next_lists = []
for lst in lists:
carry += lst.val
if lst.next: next_lists.append(lst.next)
# do math
carry, val = divmod(carry, 10)
# create & link nodes
curr.next = ListNode(val)
curr = curr.next
lists = next_lists
return ret.next
304. 997. Find the Town Judge
- Graph
- Easy
- O(N)
Everybody trusts: in degree = n-1 Trusts no one: out degree = 0
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
if n == 1: return 1
in_degrees = Counter((b for _, b in trust))
out_degrees = Counter((a for a, _ in trust))
candidate = [p for p, t in in_degrees.items() if t == n -1]
for p in candidate:
if out_degrees.get(p, 0) == 0: return p
return -1
305. [128]
306. 1636. Sort Array by Increasing Frequency
- Sort
- Easy
- O(NlogN)
class Solution:
def frequencySort(self, nums: List[int]) -> List[int]:
num_freq = Counter(nums)
# return sorted(nums, key=lambda x: (num_freq[x], -x))
freq_to_nums = defaultdict(lambda: SortedList(key=lambda x: -x))
for num, freq in num_freq.items():
freq_to_nums[freq].add(num)
result = []
for freq in sorted(freq_to_nums.keys()):
for val in freq_to_nums[freq]:
result += [val] * freq
return result
307. 53. Maximum Subarray
- Greedy
- Easy
- O(N)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
window_sum = nums[0]
max_sum = nums[0]
for num in nums[1:]:
if num > window_sum + num: window_sum = 0
window_sum += num
max_sum = max(max_sum, window_sum)
return max_sum
308. 979. Distribute Coins in Binary Tree
- Postorder Traversal
- Medium
- O(N)
class Solution:
def distributeCoins(self, root: Optional[TreeNode]) -> int:
cost = 0
states = {None: [0, 0]}
stack = [(root, 0)]
while stack:
node, post = stack.pop()
if not post:
stack.append((node, 1))
stack.extend([(child, 0) for child in [node.left, node.right] if child])
continue
l_extra, l_lack = states[node.left]
r_extra, r_lack = states[node.right]
total_coins = node.val + l_extra + r_extra
total_need = l_lack + r_lack + 1
cost += l_extra + r_extra + l_lack + r_lack
extra = max(0, total_coins - total_need)
lack = max(0, total_need - total_coins)
states[node] = (extra, lack)
for child in node.left, node.right:
if child: states.pop(child)
return cost
309. [8]
310. 103. Binary Tree Zigzag Level Order Traversal
- Tree Traversal
- Medium
- O(N)
class Solution:
def bfs(self, root: TreeNode) -> List[List[int]]:
if not root: return []
queue = deque([root])
level = 0
results = []
while queue:
level_nodes = deque()
for _ in range(len(queue)):
node = queue.popleft()
if level & 1: level_nodes.appendleft(node.val)
else: level_nodes.append(node.val)
for child in [node.left, node.right]:
if not child: continue
queue.append(child)
level += 1
results.append(level_nodes)
return results
def dfs(self, root: TreeNode) -> List[List[int]]:
if not root: return []
stack = [(root, 0)]
results = []
while stack:
node, level = stack.pop()
if level >= len(results): results.append(deque())
if level & 1: results[level].appendleft(node.val)
else: results[level].append(node.val)
for child in [node.right, node.left]:
if not child: continue
stack.append([child, level + 1])
return results
zigzagLevelOrder = dfs # dfs
311. 1472. Design Browser History
- Array
- Medium
- O(1) Operations.
class BrowserHistory:
def __init__(self, homepage: str):
self.urls = [homepage]
self.i = self.top = 0
def visit(self, url: str) -> None:
if self.i + 1 == len(self.urls):
self.urls.append(url)
else:
self.urls[self.i+1] = url
self.i += 1
self.top = self.i
def back(self, steps: int) -> str:
self.i = max(0, self.i - steps)
return self.urls[self.i]
def forward(self, steps: int) -> str:
self.i = min(self.top, self.i + steps)
return self.urls[self.i]
312. 11. Container With Most Water
- Two Pointers
- Medium
- O(N)
class Solution:
def maxArea(self, height: List[int]) -> int:
max_area, l, r = 0, 0, len(height) - 1
while l < r:
max_area = max(max_area, min(height[l], height[r]) * (r- l))
if height[l] < height[r]: l += 1
else: r -= 1
return max_area
313. 1200. Minimum Absolute Difference
- Sort
- Easy
- O(NlogN) / O(Range)
class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
# arr.sort()
# min_abs_diff = arr[-1] - arr[0]
# for prev, curr in pairwise(arr):
# diff = curr - prev
# min_abs_diff = min(min_abs_diff, diff)
# result = []
# for prev, curr in pairwise(arr):
# if curr - prev == min_abs_diff:
# result.append((prev, curr))
# return result
# Counting sort
min_x, max_x = min(arr), max(arr)
buckets = [0] * (max_x - min_x + 1)
for num in arr: buckets[num - min_x] = 1
min_abs_diff = max_x - min_x
sentinel = 0
while buckets[sentinel] == 0: sentinel += 1
prev, curr = sentinel, sentinel + 1
while curr < len(buckets):
while curr < len(buckets) and buckets[curr] == 0: curr += 1
min_abs_diff = min(min_abs_diff, curr - prev)
prev = curr
curr += 1
results = []
prev, curr = sentinel, sentinel + 1
while curr < len(buckets):
while curr < len(buckets) and buckets[curr] == 0: curr += 1
if curr < len(buckets) and curr - prev == min_abs_diff:
results.append([prev + min_x, curr + min_x])
min_abs_diff = min(min_abs_diff, curr - prev)
prev = curr
curr += 1
return results
314. 1202. Smallest String With Swaps
- Sorting / Connected components
- Medium
- O(NlogN)
Find components of locations within each, locations can be reordered aribitrarily, sort within each components.
class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
s = list(s)
n = len(s)
# graph in adj list
adj_list = defaultdict(list)
for f, t in pairs:
adj_list[f].append(t)
adj_list[t].append(f)
# components finding - dfs
visited = set()
for i in range(n):
if i in visited: continue
stack = [i]
component = set()
while stack:
loc = stack.pop()
component.add(loc)
for next_ in adj_list[loc]:
if next_ in component: continue
stack.append(next_)
visited.update(component)
for char, loc in zip(sorted(s[i] for i in component), sorted(component)):
s[loc] = char
return "".join(s)
315. 540. Single Element in a Sorted Array
- Binary Search
- Medium
- O(logN)
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
l, h = 0, len(nums) - 1
while l < h:
m = (l + h) // 2
n = m - 1 if m & 1 else m + 1
if nums[m] == nums[n]:
l = m + 1
else:
h = m
return nums[l]
316. 925. Long Pressed Name
- Two Pointers
- Easy
- O(N)
class Solution:
def isLongPressedName(self, name: str, typed: str) -> bool:
i, j = 0, 0
while i < len(name) and j < len(typed):
if name[i] == typed[j]:
i += 1
j += 1
elif i and typed[j] == name[i-1]:
j += 1
else:
return False
if i == len(name):
while j < len(typed):
if typed[j] != name[-1]: return False
j += 1
return i == len(name) and j == len(typed)
317. 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:])
318. [124]
319. 174. Dungeon Game
- DP
- Hard
- O(MN)
INT_MAX = 2 ** 32
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
nrow, ncol = len(dungeon), len(dungeon[0])
hp = [[INT_MAX] * (ncol + 1) for _ in range(nrow + 1)]
for r in reversed(range(nrow)):
for c in reversed(range(ncol)):
# basecase
if (r, c) == (nrow - 1, ncol - 1):
hp[r][c] = max(1, 1 - dungeon[-1][-1])
else:
hp[r][c] = max(1, min(hp[r][c+1], hp[r+1][c]) - dungeon[r][c])
return hp[0][0]
320. [135]
321. 965. Univalued Binary Tree
- Tree
- Easy
- O(N)
class Solution:
def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
val = root.val
stack = [root]
while stack:
node = stack.pop()
if not node: continue
if node.val != val: return False
stack.extend([node.left, node.right])
return True
322. 560. Subarray Sum Equals K
- Prefix Sum
- Medium
- O(N)
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
total, accum = 0, 0
prefix_sums = {0: 1}
for num in nums:
accum += num
total += prefix_sums.get(accum - k, 0)
prefix_sums[accum] = prefix_sums.get(accum, 0) + 1
return total
323. 77. Combinations
- Backtrack
- Medium
- O(2^N)
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
def backtrack(candidate, i):
if len(candidate) == k:
result.append(candidate.copy())
return
for j in range(i, n+1):
candidate.append(j)
backtrack(candidate, j+1)
candidate.pop()
backtrack([], 1)
return result
324. [1335]
325. 2089. Find Target Indices After Sorting Array
- Counting
- Easy
- O(N)
class Solution:
def targetIndices(self, nums: List[int], target: int) -> List[int]:
num_smaller, num_equal = 0, 0
for num in nums:
num_smaller += num < target
num_equal += num == target
return list(range(num_smaller, num_smaller + num_equal))
326. 415. Add Strings
- Math
- Easy
- O(N)
def zip_longest(i1, i2, filler='0'):
while i1 or i2:
val1 = next(i1, None)
val2 = next(i2, None)
if val1 is None and val2 is None: return
if val1 is None: val1 = filler
if val2 is None: val2 = filler
yield val1, val2
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
if len(num1) < len(num2): num1, num2 = num2, num1
total, carry = deque([]), 0
for d1, d2 in zip_longest(reversed(num1), reversed(num2), '0'):
carry, d = divmod(int(d1) + int(d2) + carry, 10)
total.appendleft(d)
if carry: total.appendleft(1)
return ''.join(map(str, total))
327. 763. Partition Labels
- Greedy
- Medium
- O(N)
One path to scan and record last location for each character. Second path to greedily partition array. For each character we see update the optential partition point as max(pp, last_loc[char]) when the current index is the pp, do a partition.
class Solution:
def partitionLabels(self, S: str) -> List[int]:
last_pos = {char:idx for idx, char in enumerate(S)}
l, r = 0, 0
partitions = []
for i, char in enumerate(S):
r = max(r, last_pos[char])
if i == r:
partitions.append(i - l + 1)
l = i + 1
return partitions
328. 215. Kth Largest Element in an Array
- Quickselect
- Medium
- O(N)
class Solution:
def solution_priority_queue(self, nums: List[int], k: int) -> int:
pq = []
for num in nums:
if len(pq) < k: heappush(pq, num)
elif num > pq[0]: heapreplace(pq, num)
return pq[0]
def solution_quick_select(self, arr, k):
if k == 1: return max(arr)
def swap(i, j): arr[i], arr[j] = arr[j], arr[i]
def partition(arr, l, h):
if l >= h: return
p = random.randint(l, h)
p_val = arr[p]
swap(l, p)
i, j = l, h
while i < j:
while i < h and arr[i] <= p_val: i += 1
while j > l and arr[j] >= p_val: j -= 1
if j > i and arr[j] < arr[i]: swap(i, j)
swap(j, l)
return j
n = len(arr)
l, h, j = 0, n - 1, None
t = len(arr) - k
while j != t:
j = partition(arr, l, h)
if arr[j] == arr[-k]: break
if j > t: l, h = 0, j
if j < t: l, h = j, n - 1
return arr[-k]
findKthLargest = solution_quick_select
329. [450]
330. 1167. Minimum Cost to Connect Sticks
- Greedy / Priority Queue
- Medium
- O(NlogN)
class Solution:
def connectSticks(self, sticks: List[int]) -> int:
total = 0
heapify(sticks)
while len(sticks) >= 2:
s1, s2 = heappop(sticks), heappop(sticks)
total += s1 + s2
heappush(sticks, s1 + s2)
return total
331. 974. Subarray Sums Divisible by K
- Prefix Sum
- Medium
- O(N)
class Solution:
def subarraysDivByK(self, A: List[int], K: int) -> int:
accum = [0]
for num in A: accum.append((accum[-1] + num) % K)
counts = Counter(accum)
return sum([v * (v - 1) // 2 for v in counts.values()])
332. 29. Divide Two Integers
- Math
- Medium
- O(logN)
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
INT_MIN = -2**31
INT_MAX = 2**30 + (2**30 - 1)
if dividend == INT_MIN and divisor==-1: return INT_MAX
if dividend == INT_MIN and divisor==1: return INT_MIN
negative = (dividend < 0) ^ (divisor < 0)
dividend = -dividend if dividend > 0 else dividend
divisor = -divisor if divisor > 0 else divisor
quotient, i, accum = 0, 1, divisor
while accum >= INT_MIN >> 1 and dividend <= accum + accum:
i <<= 1
accum += accum
while dividend <= divisor:
if dividend <= accum:
dividend -= accum
quotient += i
accum >>= 1
i >>= 1
return -quotient if negative else quotient
333. 260. Single Number III
- Bit
- Medium
- O(N)
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
mixed = reduce(xor, nums)
lsb = mixed & -mixed
x = reduce(xor, filter(partial(and_, lsb), nums))
return [x, mixed ^ x]
334. 18. 4Sum
- Two Pointers
- Medium
- O(N^3)
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
def two_sum(nums, target):
n = len(nums)
l, r = 0, n - 1
pairs = []
while l < r:
s = nums[l] + nums[r]
if s > target or (r < n - 1 and nums[r] == nums[r + 1]):
r -= 1
elif s < target or (l > 0 and nums[l] == nums[l - 1]):
l += 1
else:
pairs.append([nums[l], nums[r]])
l += 1
r -= 1
return pairs
def k_sum(nums, target, k):
if len(nums) == 0: return []
if nums[0] > target / k or nums[~0] < target / k: return []
result = []
if k == 2: return two_sum(nums, target)
for i, num in enumerate(nums):
if i == 0 or nums[i - 1] != num:
for pair in k_sum(nums[i + 1:], target - num, k - 1):
result.append([num] + pair)
return result
nums.sort()
return k_sum(0, target, 4)
335. 684. Redundant Connection
- Union Find
- Medium
- O(N)
Go throught the edges, if two nodes are already in the seame connected components, the edge is redundent.
class UnionFind:
def __init__(self, n):
self.parents = list(range(n))
self.sizes = [1] * 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 = 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
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
n = len(edges) + 1
uf = UnionFind(n)
for edge in edges:
if (uf.union(edge[0], edge[1])): continue
return edge
336. 79. Word Search
- Backtrack
- Medium
- O(N * 4 ^ L)
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
nrow, ncol = len(board), len(board[0])
n = len(word)
def backtrack(r, c, i):
if i == n: return True
if 0 <= r < nrow and 0 <= c < ncol and board[r][c] == word[i]:
char = board[r][c]
board[r][c] = ''
for rr, cc in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
if backtrack(rr, cc, i+1): return True
board[r][c] = char
for r in range(nrow):
for c in range(ncol):
if backtrack(r, c, 0): return True
return False
337. 349. Intersection of Two Arrays
- Set
- Easy
- O(N)
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(num for num in nums1 if num in nums2))
338. [282]
339. 367. Valid Perfect Square
- Binary Search / Newton’s Method
- Easy
- O(logN)
class Solution:
def isPerfectSquare(self, num: int) -> bool:
# l, h = 1, num
# while l < h:
# m = (l + h) // 2
# if m * m >= num:
# h = m
# else:
# l = m + 1
# return l * l == num
h = lambda x: - (x**2 - num) // (2*x)
x = num
while x * x > num: x += h(x)
return x * x == num
340. 1650. Lowest Common Ancestor of a Binary Tree III
- Tree
- Medium
- O(N)
class Solution:
def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
p_parents = set([p])
q_parents = set([q])
while True:
if p in q_parents: return p
if q in p_parents: return q
if p.parent:
p = p.parent
p_parents.add(p)
if q.parent:
q = q.parent
q_parents.add(q)
341. 14. Longest Common Prefix
- Sweep Line
- Easy
- O(MN)
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
res = []
for chars in zip(*strs):
if len(set(chars)) != 1: break
res.append(chars[0])
return "".join(res)
342. 228. Summary Ranges
- Two Pointers
- Easy
- O(N)
class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
result = []
if not nums: return result
def add_range(n1, n2):
if n1 != n2: result.append(f"{n1}->{n2}")
else: result.append(str(n1))
l = 0
for r in range(1, len(nums)):
if nums[r] != nums[r-1] + 1:
add_range(nums[l], nums[r-1])
l = r
add_range(nums[l], nums[len(nums) - 1])
return result
343. 658. Find K Closest Elements
- Binary Search
- Medium
- O(logN)
// f(i) = abs(arr[i] - x) vs i
// g(i) = f(i) <= f(i+k)
// k == 5
// 00 1 11111
// f(i)
// ^* *
// | * *
// | |*_________*
// | *|
// | * *
// | *
// ------------------> i
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
lo, hi = 0, len(arr) - k
while lo < hi:
mid = (lo + hi) >> 1
if x - arr[mid] > arr[mid + k] - x: lo = mid + 1
else: hi = mid
return arr[lo:lo+k]
344. 131. Palindrome Partitioning
- Backtrack
- Medium
- O(2^N * N)
class Solution:
def partition(self, s):
n = len(s)
def is_palindrome(i, j):
# return s[i:j] == x[i:j][::-1]
while i < j:
if s[i] != s[j]: return False
i += 1; j -= 1
return True
results = []
def backtrack(candidate, i):
if i == len(s): return results.append(candidate.copy())
for j in range(i+1, n+1):
if is_palindrome(i, j-1):
candidate.append(s[i:j])
backtrack(candidate, j)
candidate.pop()
backtrack([], 0)
return results
345. 16. 3Sum Closest
- Two Pointers
- Medium
- O(N^2)
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
result = nums[0] + nums[1] + nums[-1]
for i in range(n - 2):
j, k = i + 1, n - 1
while j < k:
total = nums[i] + nums[j] + nums[k]
if total == target: return total
if abs(total - target) < abs(result - target): result = total
if total < target: j += 1
else: k -= 1
return result
346. 67. Add Binary
- Math
- Easy
- O(N)
class Solution:
def addBinary(self, a: str, b: str) -> str:
if len(a) < len(b): a, b = b, a
total, carry = deque([]), 0
for d1, d2 in zip_longest(reversed(a), reversed(b), fillvalue="0"):
carry, d = divmod(int(d1) + int(d2) + carry, 2)
total.appendleft(d)
if carry: total.appendleft(1)
return ''.join(map(str, total))
347. 220. Contains Duplicate III
- Bucket Sort
- Medium
- O(N)
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
def get_id(x, w = t + 1): return (x + 1) // w - 1 if x < 0 else x // w
if t < 0: return False
buckets = dict()
for i, num in enumerate(nums):
bucket_id = get_id(num)
if bucket_id in buckets: return True
if (bucket_id - 1) in buckets and abs(num - buckets[bucket_id - 1]) < t + 1: return True
if (bucket_id + 1) in buckets and abs(num - buckets[bucket_id + 1]) < t + 1: return True
buckets[bucket_id] = num
if i >= k: buckets.pop(get_id(nums[i - k]))
return False
348. 392. Is Subsequence
- Greedy
- Easy
- O(N)
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i = 0
n = len(t)
for char in s:
while i < n and t[i] != char: i += 1
i += 1
if i > n: return False
return True
349. 442. Find All Duplicates in an Array
- Array
- Medium
- O(N)
Use sign of the elements at index i to mark even or odd number of times number i appeared.
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
dups = []
for num in nums:
if nums[abs(num) - 1] < 0: dups.append(abs(num))
else: nums[abs(num) - 1] *= -1
return dups
350. 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]
351. 289. Game of Life
- Array
- Medium
- O(MN)
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
""" Do not return anything, modify board in-place instead. """
# two pass the board, one pass marking, second pass finalize.
#
# states:
# 0 dead | undetermined or will be dead
# 1 live | undetermined or will be live
# 2 dead | will be live
# 3 live | will be dead
#
# => state & 1 tells whether the cell is a live cell in previous state
# state in [1, 2] tells whether the cell should live in next state
nrow, ncol = len(board), len(board[0])
def count_living_neighbors(r, c):
count = 0
for nr, nc in [(r + 1, c), (r - 1, c), (r + 1, c + 1), (r + 1, c - 1),
(r, c - 1), (r, c + 1), (r - 1, c + 1), (r - 1, c - 1)]:
if nrow > nr >= 0 <= nc < ncol:
count += board[nr][nc] & 1
return count
for r in range(nrow):
for c in range(ncol):
living_neighbors = count_living_neighbors(r, c)
if board[r][c] == 1: # rule 2 is no change
if living_neighbors < 2: board[r][c] = 3 # rule 1
if living_neighbors > 3: board[r][c] = 3 # rule 3
else:
if living_neighbors == 3: board[r][c] = 2 # rule 4
for r in range(nrow):
for c in range(ncol):
board[r][c] = 1 if board[r][c] in [1, 2] else 0
352. 226. Invert Binary Tree
- Tree / DFS
- Easy
- O(N)
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root: return root
stack = [root]
while stack:
node = stack.pop()
node.left, node.right = node.right, node.left
for child in (node.left, node.right):
if not child: continue
stack.append(child)
return root
353. 5. Longest Palindromic Substring
- Array / Two Pointers
- Medium
- O(N^2)
Manacher’s algorithm is O(N)
class Solution:
def longestPalindrome(self, s: str) -> str:
max_length, max_l, max_r = 0, None, None
for i in range(len(s)):
l, r, length = i-1, i+1, 1
while 0 <= l < r < len(s) and s[l] == s[r]:
length += 2; l -= 1; r += 1
if length > max_length:
max_length, max_l, max_r = length, l+1, r-1
l, r, length = i, i + 1, 0
while 0 <= l < r < len(s) and s[l] == s[r]:
length += 2; l -= 1; r += 1
if length > max_length:
max_length, max_l, max_r = length, l+1, r-1
return s[max_l: max_r + 1]
354. 316. Remove Duplicate Letters
- Stack
- Medium
- O(N)
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
last = {c: i for i, c in enumerate(s)}
stack, used = list(), set()
for i, c in enumerate(s):
if c in used: continue
# not empty & insert c reduce lexi & not the last one
while stack and stack[-1] > c and i < last[stack[-1]]:
used.remove(stack.pop())
stack.append(c)
used.add(c)
return "".join(stack)
355. 1047. Remove All Adjacent Duplicates In String
- Stack
- Easy
- O(N)
class Solution:
def removeDuplicates(self, s: str) -> str:
stack = []
for c in s:
if stack and stack[-1] == c:
stack.pop()
continue
stack.append(c)
return "".join(stack)
356. 217. Contains Duplicate
- HashSet
- Easy
- O(N)
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return len(set(nums)) < len(nums)
357. 461. Hamming Distance
- Bit
- O(N)
- Easy
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
total = 0
while x or y:
total += (x & 1) ^ (y & 1)
x >>= 1
y >>= 1
return total
def hammingDistance(self, x: int, y: int) -> int:
xor = x ^ y
distance = 0
while xor:
distance += 1
xor &= (xor - 1)
return distance
358. 387. First Unique Character in a String
- HashSet / HashMap
- Easy
- O(N)
class Solution:
def firstUniqChar(self, s: str) -> int:
seen = set()
char_loc = dict()
for loc, c in enumerate(s):
if c in seen:
char_loc.pop(c, None)
continue
seen.add(c)
char_loc[c] = loc
return -1 if not char_loc else next(iter(char_loc.values()))
359. 198. House Robber
- DP
- Medium
- O(N)
DP[i] is the maximum value obtained with first i houses. DP[i] = max(DP[i-1], DP[i-2] + value at house i])
def dp_1(nums):
dp = [0] * (len(nums) + 2) # left pad by two for easy indexing
for i in range(2, n + 2):
dp[i] = max(dp[i-1], dp[i-2]+ nums[i - 2])
return max(dp)
# reduce above to constant space, since we only need previous two values from 1D DP array.
def dp_2(nums):
maximum = -2 ** 32
rest, rob = 0, 0
for num in nums:
rest, rob = rob, max(rest + num, rob)
maximum = max(maximum, rob)
return maximum
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums: return 0
return dp_2(nums)
360. 70. Climbing Stairs
- DP
- Easy
- O(N)
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 3: return n
prev, curr = 1, 1
for _ in range(2, n + 1): prev, curr = curr, prev + curr
return curr
361. 973. K Closest Points to Origin
- Quick Select
- Medium
- O(N)
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
pq = []
dist = lambda x: - (x[0] ** 2 + x[1] ** 2)
for p in points:
d = dist(p)
if len(pq) < K: heapq.heappush(pq, (d, p))
elif d < -pq[0][0]: heapq.heapreplace(pq, (d, p))
return [t[1] for t in pq]
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
@cache
def dist(x, y): return x ** 2 + y ** 2
def swap(i, j): points[i], points[j] = points[j], points[i]
def partition(l, r):
m = (l + r) >> 1
pivot = dist(*points[m])
swap(l, m)
i, j = l, r
while i < j:
while i < r and dist(*points[i]) <= pivot: i += 1
while j > l and dist(*points[j]) >= pivot: j -= 1
if i < j and dist(*points[i]) > dist(*points[j]): swap(i, j)
swap(j, l)
return j
def sort(l, r, k):
m = partition(l, r)
d = m - l + 1
if d == k: return
elif d < k: sort(m + 1, r, k - d)
else: sort(l, m - 1, k)
sort(0, len(points) - 1, K)
return points[:K]
362. 310. Minimum Height Trees
- Topological Sort
- Medium
- O(V + E)
BFS from leaf and up
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n <= 2: return list(range(n))
adj_list = defaultdict(set)
for (n1, n2) in edges:
adj_list[n1].add(n2)
adj_list[n2].add(n1)
level = deque([node for node in adj_list if len(adj_list[node]) == 1])
while n > 2:
nodes_this_level = len(level)
n -= nodes_this_level
for i in range(nodes_this_level):
node = level.popleft()
for next_ in adj_list[node]:
adj_list[next_].remove(node)
if len(adj_list[next_]) == 1: level.append(next_)
return level
363. 50. Pow(x, n)
- Math
- Medium
- O(logN)
class Solution:
def myPow(self, x: float, n: int) -> float:
if n < 0:
x = 1 / x
n = - n
accum, p = 1, x
while n:
if n & 1: accum *= p
p *= p
n >>= 1
return accum
364. 322. Coin Change
- DP
- Medium
- O(NK)
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
min_coin = min(coins)
dp = [0] + [float('inf')] * amount
for amt in range(amount + 1):
if amt < min_coin: continue
dp[amt] = min({dp[amt - c] for c in coins if amt >= c}) + 1
return dp[amount] if dp[amount] != float('inf') else -1
365. 1859. Sorting the Sentence
- String
- Easy
- O(N)
class Solution:
def sortSentence(self, s: str) -> str:
result = [""] * 10
for token in s.split():
word, index = token[:-1], token[-1]
result[int(index)] = word
return " ".join(result).strip()
366. 155. Min Stack
- Design
- Easy
- O(1) push, pop and get min
Store tuple (val, min_val) on a regular stack.
class MinStack:
def __init__(self):
self.arr = []
def push(self, x: int) -> None:
if self.is_empty(): return self.arr.append((x, x))
new_min = min(self.getMin(), x)
self.arr.append((x, new_min))
def pop(self) -> None:
self.arr.pop()
def top(self) -> int:
if self.is_empty(): return
return self.arr[-1][0]
def getMin(self) -> int:
if self.is_empty(): return
return self.arr[-1][1]
def is_empty(self):
return not self.arr
367. 49. Group Anagrams
- Hash
- Medium
- O(MN)
class Solution:
def groupAnagrams(self, strs):
def count_hash(s):
counts = [0] * 26
for c in s:
counts[ord(c) - ord('a')] += 1
return tuple(counts)
groups = defaultdict(list)
for s in strs:
groups[count_hash(s)].append(s)
return list(groups.values())
368. 724. Find Pivot Index
- Prefix Sum
- Easy
- O(N)
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
if not nums: return -1
total = sum(nums)
accum = 0
for i, num in enumerate(nums):
if (total - num) / 2 == accum: return i
accum += num
return -1
369. 1207. Unique Number of Occurrences
- HashMap / HashSet
- Easy
- O(N)
class Solution:
def uniqueOccurrences(self, arr: List[int]) -> bool:
vc = Counter(arr)
return len(vc) == len(set(vc.values()))
370. 54. Spiral Matrix
- Array
- Medium
- O(MN)
class Solution:
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
return matrix and matrix[0] + self.spiralOrder(self.__ccw_rotate(matrix[1:]))
@staticmethod
def __ccw_rotate(matrix):
return list(map(list, zip(*[reversed(row) for row in matrix])))
def spiralOrder(self, matrix):
res = []
if len(matrix) == 0: return res
row_begin = col_begin = 0
row_end = len(matrix) - 1
col_end = len(matrix[0]) - 1
while (row_begin <= row_end and col_begin <= col_end):
res += [matrix[row_begin][col] for col in range(col_begin, col_end + 1)]
row_begin += 1
res += [matrix[row][col_end] for row in range(row_begin, row_end + 1)]
col_end -= 1
if (row_begin <= row_end):
res += [matrix[row_end][col] for col in range(col_end, col_begin - 1, -1)]
row_end -= 1
if (col_begin <= col_end):
res += [matrix[row][col_begin] for row in range(row_end, row_begin - 1, -1)]
col_begin += 1
return res
371. 543. Diameter of Binary Tree
- Postorder Tree traversal
- Easy
- O(N)
Compute depths for each node, and find the max obtained by sum of depths from both sides.
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
max_dim = 0
depths = {None: 0}
stack = [(root, 0)]
while stack:
node, post = stack.pop()
if not node: continue
if post:
l, r = depths[node.left], depths[node.right]
depths[node] = max(l, r) + 1
max_dim = max(max_dim, l + r)
else:
stack.extend([(node, 1), (node.left, 0), (node.right, 0)])
return max_dim
372. 219. Contains Duplicate II
- HashMap / HashSet
- Easy
- O(N)
Don’t need remember the last location of elements, can use window size to make sure <= K distance away.
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
# INF = 2 ** 32
# last_loc = dict()
# for i, num in enumerate(nums):
# if last_loc.get(num, -INF) + k >= i: return True
# last_loc[num] = i
# return False
window = set()
for i, num in enumerate(nums):
if num in window: return True
window.add(num)
if len(window) > k: window.remove(nums[i-k])
return False
373. 9. Palindrome Number
- Math
- Easy
- O(N) number of digits in number
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0 or (x % 10 == 0 and x != 0): return False
y = 0
while x > y:
x, d = divmod(x, 10)
y = y * 10 + d
return y == x or y // 10 == x
374. 389. Find the Difference
- Bit
- Easy
- O(N)
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
# return (Counter(t) - Counter(s)).popitem()[0]
bits = 0
for c in s: bits ^= ord(c)
for c in t: bits ^= ord(c)
return chr(bits)
375. 25. Reverse Nodes in k-Group
- Linked List
- Hard
- O(N)
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if not head: return head
def has_k_nodes(curr, k):
while curr and k:
curr = curr.next
k -= 1
return k == 0
def reverse_k_nodes(curr, k):
tail = curr
prev = None
for i in range(k): curr.next, prev, curr = prev, curr, curr.next
return curr, prev, tail
sentinel = prev = ListNode(None)
sentinel.next = curr = head
while has_k_nodes(curr, k):
next_curr, new_head, new_tail = reverse_k_nodes(curr, k)
prev.next = new_head
new_tail.next = next_curr
prev = curr
curr = next_curr
prev.next = curr
return sentinel.next
376. 151. Reverse Words in a String
- Two Pointers
- Medium
- O(N)
class Solution:
def reverseWords(self, s: str) -> str:
S = list(s)
n = len(S)
l = r = 0
while S[r] == " ": r += 1
while r < n:
ws = 0
while r < n and S[r] != " ":
r += 1
ws += 1
ll, rr = l, r - 1
m = min(ws, (r - l) >> 1)
while m:
S[ll], S[rr] = S[rr], S[ll]
ll += 1
rr -= 1
m -= 1
l += ws + 1
while r < n and S[r] == " ": r += 1
while S and S[-1] == " ": S.pop()
l, r = 0, len(S) - 1
while l < r:
S[l], S[r] = S[r], S[l]
r -= 1
l += 1
return "".join(S)
377. 766. Toeplitz Matrix
- Array
- Easy
- O(MN)
class Solution:
def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
nrow, ncol = len(matrix), len(matrix[0])
for r in range(nrow):
for c in range(ncol):
if r == 0 or c == 0: continue
if matrix[r][c] != matrix[r-1][c-1]: return False
return True
378. 345. Reverse Vowels of a String
- Two Pointers
- Easy
- O(N)
class Solution:
def reverseVowels(self, s: str) -> str:
vowels = set('AEIOUaeiou')
chars = list(s)
l, r = 0, len(chars) - 1
while l < r:
while l < r and chars[l] not in vowels: l += 1
while l < r and chars[r] not in vowels: r -= 1
if l < r:
chars[l], chars[r] = chars[r], chars[l]
l += 1
r -= 1
return ''.join(chars)
379. [297]
380. 208. Implement Trie (Prefix Tree)
- Trie
- Medium
- O(M)
class TrieNode(defaultdict):
def __init__(self):
self.terminal = False
self.default_factory = TrieNode
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word: node = node[char]
node.terminal = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node: return False
node = node[char]
return node.terminal
def startsWith(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node: return False
node = node[char]
return True
381. 27. Remove Element
- Two Pointers
- Easy
- O(N)
Swap
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow = 0
for fast in range(len(nums)):
if nums[fast] == val: continue
nums[slow] = nums[fast]
slow += 1
return slow
382. 498. Diagonal Traverse
- Math
- Medium
- O(MN)
class Solution:
def findDiagonalOrder(self, matrix):
nrow, ncol = len(matrix), len(matrix[0])
r, c, d = 0, 0, 1
result = []
while len(result) < nrow * ncol:
result.append(matrix[r][c])
nr, nc = r - d, c + d
if not (nrow > nr >= 0 <= nc < ncol):
if d == 1:
if nc == ncol: r += 1
else: c += 1
else:
if nr == nrow: c += 1
else: r += 1
d = -d
else:
r, c = nr, nc
return result
383. 98. Validate Binary Search Tree
- Inorder Traversal
- Medium
- O(N)
inorder traversal of BST is non decreasing.
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
stack, prev, node = [], float('-inf'), root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
if prev >= node.val: return False
prev = node.val
node = node.right
return True
384. 146. LRU Cache
- Linked HashMap / OrderedDict
- Medium
- O(1)
Doubly linked list allow O(1) delete (given reference to node) and O(1) add to end. HashMap to allow O(1) access to the nodes in the doubly linked list.
class LRUCache(OrderedDict):
def __init__(self, capacity: int):
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self: return -1
super().move_to_end(key)
return self[key]
def put(self, key: int, value: int) -> None:
if key not in self and len(self) == self.capacity : super().popitem(last=False)
self[key] = value
super().move_to_end(key)
class LRUCache {
private:
int _capacity;
list<pair<int, int>> l;
unordered_map<int, list<pair<int, int>>::iterator> m;
public:
LRUCache(int capacity) { _capacity = capacity; }
int get(int key) {
if (not m.count(key)) return -1;
l.splice(l.begin(), l, m[key]);
return m[key]->second;
}
void put(int key, int value) {
if (l.size() == _capacity and not m.count(key)) {
m.erase(l.back().first);
l.pop_back();
}
if (m.count(key)) l.erase(m[key]);
l.push_front({key, value});
m[key] = l.begin();
}
};
385. [162]
386. 22. Generate Parentheses
- Backtrack
- Medium
- O(2^N * N)
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
solutions = set()
def backtrack(s, lp, rp):
if lp + rp == 2 * n: return solutions.add("".join(s))
if lp < n: backtrack(s + ['('], lp + 1, rp)
if rp < lp: backtrack(s + [')'], lp, rp + 1)
backtrack([], 0, 0)
return solutions
387. 35. Search Insert Position
- Binary Search
- Easy
- O(logN)
class Solution:
def searchInsert(self, arr: List[int], t: int) -> int:
lo, hi = 0, len(arr)
while lo < hi:
mid = (hi + lo) // 2
if arr[mid] >= t:
hi = mid # new search space [lo, mid)
else:
lo = mid + 1 # new search space [mid + 1, hi)
return lo
388. 408. Valid Word Abbreviation
- Two Pointers
- Easy
- O(N)
class Solution:
def validWordAbbreviation(self, word: str, abbr: str) -> bool:
i, j = 0, 0
while i < len(word) and j < len(abbr):
if word[i] == abbr[j]:
i += 1
j += 1
elif abbr[j].isdigit():
if abbr[j] == '0': return False
d = 0
while j < len(abbr) and abbr[j].isdigit():
d = 10 * d + int(abbr[j])
j += 1
i += d
else:
return False
return i == len(word) and j == len(abbr)
389. [377]
390. 15. 3Sum
- Two Pointers / HashMap
- Medium
- O(N^2)
class Solution:
def threeSum(self, nums):
nums.sort()
n = len(nums)
def find_two_sum(target, i):
j = i + 1
k = n - 1
pairs = []
while j < k:
if nums[j] + nums[k] == target:
pairs.append((j, k))
j += 1
k -= 1
elif nums[j] + nums[k] > target:
k -=1
else:
j += 1
return pairs
result = set()
for i, num1 in enumerate(nums):
if i and num1 == nums[i-1]: continue
pairs = find_two_sum(-num1, i)
for j, k in pairs:
result.add((nums[i],nums[j],nums[k]))
return result
def threeSum(self, nums: List[int]) -> List[List[int]]:
results = set()
examed_first = set()
seen = dict()
for i, num1 in enumerate(nums):
if num1 in examed_first: continue
examed_first.add(num1)
for num2 in nums[i+1:]:
target = - (num1 + num2)
if target in seen and seen[target] == i:
results.add(tuple(sorted([num1, num2, target])))
seen[num2] = i
return results
391. 733. Flood Fill
- DFS
- Easy
- O(MN)
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, new_color: int) -> List[List[int]]:
nrow, ncol = len(image), len(image[0])
old_color = image[sr][sc]
if old_color == new_color: return image
def get_neighbor(r, c):
for nr, nc in [(r, c + 1), (r, c - 1), (r - 1, c), (r + 1, c)]:
if nrow > r >= 0 <= c < ncol:
yield nr, nc
stack = [(sr, sc)]
while stack:
r, c = stack.pop()
image[r][c] = new_color
for nr, nc in get_neighbor(r, c):
if image[nr][nc] == old_color:
stack.append((nr, nc))
return image
392. 106. Construct Binary Tree from Inorder and Postorder Traversal
- Tree Traversal
- Medium
- O(N)
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
prev = root = TreeNode(postorder[-1])
i = 0
stack = [root]
for val in reversed(postorder[:-1]):
curr = TreeNode(val)
if prev.val == inorder[~i]: # did we just processed the rightmost leaf for current subtree?
# backtrack to the node to which we should attach new node as left child
while stack and stack[-1].val == inorder[~i]:
i += 1
prev = stack.pop()
prev.left = curr
else:
prev.right = curr
prev = curr
stack.append(curr)
return root
393. 287. Find the Duplicate Number
- Two Pointers
- Medium
- O(N)
Floyd’s algorithm for cycle detection.
0 1 2 3 4 1
[1,2,3,4,5,2]
0 -> 1 -> 2 -> 3 -> 4
^ |
|--------------|
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
394. 110. Balanced Binary Tree
- Postorder traversal
- Easy
- O()
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
heights = {None: 0}
stack = [(root, 0)]
while stack:
node, post = stack.pop()
if node is None: continue
if post:
l, r = heights[node.left], heights[node.right]
if r > l + 1 or l > r + 1: return False
heights[node] = max(l, r) + 1
else:
stack.extend([(node, 1), (node.left, 0), (node.right, 0)])
return True
395. 249. Group Shifted Strings
- Hash
- Medium
- O(MN)
class Solution:
def groupStrings(self, strings: List[str]) -> List[List[str]]:
def hash(s):
return tuple([(ord(c) - ord(s[0])) % 26 for c in s])
groupby = defaultdict(list)
for s in strings:
groupby[hash(s)].append(s)
return list(groupby.values())
396. 105. Construct Binary Tree from Preorder and Inorder Traversal
- Tree Traversal
- Medium
- O(N)
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
root, stack, i = None, [], 0
for val in preorder:
new = TreeNode(val)
if not root:
last = root = new
else:
if last.val == inorder[i]:
while stack and stack[-1].val == inorder[i]:
last = stack.pop()
i += 1
last.right = new
else:
last.left = new
last = new
stack.append(new)
return root
397. 12. Integer to Roman
- Loop?
- Medium
- O(N)
class Solution:
def intToRoman(self, num: int) -> str:
numbers = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
symbols = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
n = len(numbers)
result = []
i = 0
while i < n:
while i < n and num < numbers[i]: i += 1
while i < n and num >= numbers[i]:
result.append(symbols[i])
num -= numbers[i]
return "".join(result)
398. 707. Design Linked List
- Linked List
- Medium
- O(1) / O(N)
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class MyLinkedList:
def __init__(self):
self.size = 0
self.sentinel = ListNode(None)
def get(self, index: int) -> int:
if index < 0 or index >= self.size: return -1
curr = self.sentinel
for _ in range(index + 1): curr = curr.next
return curr.val
def addAtIndex(self, index: int, val: int):
if index > self.size: return
if index < 0: index = 0
self.size += 1
pred = self.sentinel
for _ in range(index): pred = pred.next
to_add = ListNode(val)
to_add.next = pred.next
pred.next = to_add
def deleteAtIndex(self, index: int):
if index < 0 or index >= self.size: return
self.size -= 1
pred = self.sentinel
for _ in range(index): pred = pred.next
# delete pred.next
pred.next = pred.next.next
def addAtHead(self, val: int): self.addAtIndex(0, val)
def addAtTail(self, val: int): self.addAtIndex(self.size, val)
399. 252. Meeting Rooms
- Sorting
- Easy
- O(NlogN)
class Solution:
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
if intervals[i-1][1] > intervals[i][0]: return False
return True
400. 46. Permutations
- Backtrack
- Medium
- O(2^N * N)
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
permutations = []
def backtrack(i):
if i == n: permutations.append(nums.copy())
for j in range(i, n):
nums[i], nums[j] = nums[j], nums[i]
backtrack(i + 1)
nums[i], nums[j] = nums[j], nums[i]
backtrack(0)
return permutations
401. 1929. Concatenation of Array
- Joke
- Easy
- O(N)
class Solution:
def getConcatenation(self, nums: List[int]) -> List[int]:
return [n for _ in range(2) for n in nums]
402. 121. Best Time to Buy and Sell Stock
- Greedy / Kadane
- Easy
- O(N)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
prev_min_price = prices[0]
max_profit = 0
for price in prices[1:]:
max_profit = max(max_profit, price - prev_min_price)
prev_min_price = min(prev_min_price, price)
return max_profit
403. 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
404. 133. Clone Graph
- BFS / DFS
- Medium
- O(N)
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if not node: return
dq = deque([node])
mapping = dict()
while dq: # Visit all the node
nd = dq.popleft() # bfs
# nd = deque.pop() # dfs
if nd not in mapping: mapping[nd] = Node(nd.val)
for nei in nd.neighbors: # visit all the edges for the node
if nei not in mapping:
mapping[nei] = Node(nei.val)
dq.append(nei)
mapping[nd].neighbors.append(mapping[nei])
return mapping[node]
405. [279]
406. 231. Power of Two
- Bit / Math
- Easy
- O(1)
number that is power of two only have one 1 bit.
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n == 0: return False
return n & (n - 1) == 0
407. 1011. Capacity To Ship Packages Within D Days
- Binary Search
- Medium
- O(Nlog(M))
class Solution:
def shipWithinDays(self, weights: List[int], D: int) -> int:
def can_finish(capacity):
loaded, days = 0, 0
for weight in weights:
if loaded + weight > capacity:
days += 1
loaded = 0
loaded += weight
return days < D
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) >> 1
if can_finish(mid):
hi = mid
else:
lo = mid + 1
return lo
408. 238. Product of Array Except Self
- Prefix Prod
- Medium
- O(N)
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
output = [1] * n
accum_l = accum_r = 1
for i in range(n):
output[i] *= accum_l
output[~i] *= accum_r
accum_l *= nums[i]
accum_r *= nums[~i]
return output
409. 986. Interval List Intersections
- Two Pointers / Sweep Line
- Medium
- O(N)
class Solution:
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
def intersection(itv1, itv2):
l = max(itv1[0], itv2[0])
r = min(itv1[1], itv2[1])
if l <= r: return [l, r]
return []
intersections = []
n_itv1, n_itv2 = len(firstList), len(secondList)
i, j = 0, 0
while i < n_itv1 and j < n_itv2:
itv = intersection(firstList[i], secondList[j])
if itv: intersections.append(itv)
if firstList[i][1] < secondList[j][1]: i += 1
else: j += 1
return intersections
410. 78. Subsets
- Bit / Backtrack
- Medium
- O(2^N)
Use bit mask from [0, 1 « n) as recipe for creating subsets.
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
subsets = []
for i in range(1 << len(nums)):
subset = []
for j, num in enumerate(nums):
if i & (1 << j): subset.append(num)
subsets.append(subset)
return subsets
411. 905. Sort Array By Parity
- Array / Two Pointers
- Easy
- O(N)
Swaps
class Solution:
def sortArrayByParity(self, A: List[int]) -> List[int]:
i, j = 0, len(A) - 1
while i < j:
while i < len(A) and not A[i] % 2: i += 1
while j >= 0 and A[j] % 2: j -= 1
if i < j: A[i], A[j] = A[j], A[i]
return A
412. 257. Binary Tree Paths
- Tree Traversal
- Easy
- O(N)
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
result = []
def dfs(path, node):
if node.left is None and node.right is None:
result.append('->'.join(map(str, path)))
return
for child in node.left, node.right:
if child is None: continue
path.append(child.val)
dfs(path, child)
path.pop()
dfs([root.val], root)
return result
413. 45. Jump Game II
- Greedy / Sweep Line
- Medium
- O(N)
Go through locations, keep track of the farthest location we can jump to as well as the previous location we jumped to.
Only jump when it is neccessary, ie when previous jumped location is smaller than current location.
class Solution:
def jump(self, nums: List[int]) -> int:
prev, nxt, num_steps = 0, 0, 0
for i, num in enumerate(nums):
if i > prev:
prev = nxt
num_steps += 1
nxt = max(nxt, i + num)
return num_steps
414. 117. Populating Next Right Pointers in Each Node II
- BFS
- Medium
- O(N)
class Solution:
def connect(self, root):
queue = deque([root]) if root else []
while queue:
n = len(queue)
for i in range(n):
node = queue.popleft()
if i != n - 1: node.next = queue[0]
for child in [node.left, node.right]:
if not child: continue
queue.append(child)
return root
415. 518. Coin Change 2
- DP
- Medium
- O(NM)
f(amt, options) = f(amt, options.popfront()) + f(amt - options[0], options)
f(0, xx) = 1
f(amt >0, {}) = 0
f(amt <0, xx) = 0
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
# @lru_cache(maxsize=None)
# def make_change(amount, i):
# if amount == 0: return 1
# if i == len(coins) or amount < 0: return 0
# return make_change(amount, i+1) + make_change(amount - coins[i], i)
# return make_change(amount, 0)
dp = [1] + [0] * amount
for coin in coins:
for i in range(amount+1):
if i + coin > amount: break
dp[i+coin] += dp[i]
return dp[-1]
416. 523. Continuous Subarray Sum
- Prefix Sum / HashMap
- Medium
- O(N)
class Solution(object):
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
total = 0
memo = {0: -1}
for i, num in enumerate(nums):
total += num
reminder = total % k
if reminder not in memo: memo[reminder] = i
elif i - memo[reminder] >= 2: return True
return False
417. 167. Two Sum II - Input Array Is Sorted
- Two Pointers
- Easy
- O(N)
class Solution:
def twoSum(self, numbers, target):
l, r = 0, len(numbers)-1
while l < r:
total = numbers[l] + numbers[r]
if total == target: return [l + 1, r + 1]
if total > target: r -= 1
else: l += 1
return [-1, -1]
418. 26. Remove Duplicates from Sorted Array
- Two Pointers
- Easy
- O(N)
class Solution:
def removeDuplicates(self, nums):
i = 0
k = 1
for n in nums:
if i < k or n > nums[i - k]:
nums[i] = n
i += 1
return i
419. 32. Longest Valid Parentheses
- DP
- Hard
- O(N)
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
dp = [0] * n
for i in range(1, n):
if s[i] == ')':
if s[i - 1] == '(':
dp[i] = dp[i - 2] + 2
elif i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == '(':
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
return max(dp) if dp else 0
420. 212. Word Search II
- Backtrack / Trie
- Hard
- O(2^N)
class Trie:
class TrieNode(defaultdict):
def __init__(self):
super().__init__(Trie.TrieNode)
self.word = ""
def __init__(self):
self.root = Trie.TrieNode()
def insert(self, word):
node = self.root
for char in word: node = node[char]
node.word = word
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
nrow, ncol = len(board), len(board[0])
trie = Trie()
for word in words: trie.insert(word)
crossed = set()
def backtrack(node, r, c):
if node.word: crossed.add(node.word)
if 0 <= r < nrow and 0 <= c < ncol and board[r][c] in node:
char = board[r][c]
board[r][c] = 'X'
for rr, cc in [(r-1,c),(r+1,c),(r,c-1),(r,c+1)]:
backtrack(node[char], rr, cc)
board[r][c] = char
for r in range(nrow):
for c in range(ncol):
backtrack(trie.root, r, c)
return crossed
421. 1512. Number of Good Pairs
- HashMap
- Easy
- O(N)
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
freq = dict()
total = 0
for num in nums:
total += freq.setdefault(num, 0)
freq[num] += 1
return total
422. 416. Partition Equal Subset Sum
- DP
- Medium
- O(N^2)
let dp[i][j] indicate whether we can use nums[:i] to sum up to j.
class Solution:
def canPartition(self, nums: List[int]) -> bool:
s = sum(nums)
if s % 2: return False
s //= 2
n = len(nums)
dp = [[True] + [False] * s for _ in range(n)] # dp[i][j] can I subset sum to j with nums[:i] (inclusive)
if nums[0] <= s: dp[0][nums[0]] = True
for i, num in enumerate(nums[1:], 1):
for j in range(1, s + 1):
if dp[i - 1][j]: dp[i][j] = True # did not take num
elif j >= num: dp[i][j] = dp[i - 1][j - num] # take num
return dp[-1][-1]
423. 113. Path Sum II
- Tree
- Medium
- O(N)
class Solution:
def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
if not root: return []
solutions = []
stack = [(root, [root.val], root.val)]
while stack:
node, vals, path_sum = stack.pop()
if not (node.left or node.right) and path_sum == target: solutions.append(vals)
if node.left: stack.append((node.left, vals + [node.left.val], path_sum + node.left.val))
if node.right: stack.append((node.right, vals + [node.right.val], path_sum + node.right.val))
return solutions
424. 647. Palindromic Substrings
- DP
- Medium
- O(N^2)
class Solution:
def countSubstrings(self, s: str) -> int:
total = 0
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
total += 1
for i in range(n-1):
if s[i] == s[i + 1]:
dp[i][i+1] += 1
total += 1
for l in range(3, n+1): # increasing window size
for i in range(n):
j = i + l - 1
if j >= n: break
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1]
total += dp[i][j]
return total
425. 383. Ransom Note
- HashMap
- Easy
- O(N)
class Solution:
def canConstruct(self, ransomNote, magazine):
m = dict()
for c in ransomNote: m[c] = m.get(c, 0) + 1
for c in magazine: m[c] = m.get(c, 0) - 1
return all(v <= 0 for v in m.values())
426. 21. Merge Two Sorted Lists
- Two Pointers / Linked List
- Easy
- O(N)
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
ret = curr = ListNode(None)
while l1 and l2:
if l1.val < l2.val: curr.next, l1 = l1, l1.next
else: curr.next, l2 = l2, l2.next
curr = curr.next
curr.next = l1 if l1 else l2
return ret.next
427. 977. Squares of a Sorted Array
- Two Pointers
- Easy
- O(N)
Fill a result array from right to left. Compare values from both sides of the original arry., put the larger square to result array and advance.
class Solution:
def sortedSquares(self, A: List[int]) -> List[int]:
n = len(A)
l, r = 0, n - 1
result = [0] * n
k = n - 1
while l <= r:
if abs(A[l]) > abs(A[r]):
result[k] = A[l] ** 2
l += 1
k -= 1
else:
result[k] = A[r] ** 2
r -= 1
k -= 1
return result
428. 797. All Paths From Source to Target
- Backtracking
- Medium
- O(2^N * N)
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
n = len(graph) - 1
paths = []
def backtrack(path):
if path[-1] == n:
paths.append(path.copy())
return
for nei in graph[path[-1]]:
path.append(nei)
backtrack(path)
path.pop()
backtrack([0])
return paths
429. 347. Top K Frequent Elements
- Counting / Sorting
- Medium
- NlogN if heap, O(N) if quickselect, O(range) if bucket
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
freq_counts = Counter(nums)
buckets = defaultdict(set)
for elem, freq in freq_counts.items():
buckets[freq].add(elem)
topk = []
for freq in range(len(nums), -1, -1):
if freq in buckets: topk.extend(buckets[freq])
if len(topk) >= k: break
return topk[:k]
class Solution:
def topKFrequent(self, nums, k):
freq_nums = [(f, v) for v, f in Counter(nums).items()]
return [v for _, v in nlargest(k, freq_nums)]
430. 33. Search in Rotated Sorted Array
- Binary Search
- Medium
- O(logN)
The array consists of two sorted part. / / / / / l r Compare nums[mid] with nums[l] (or nums[h]) tell us which part mid is in. Then since each part is sorted, figure out how to bisect based of target, nums[mid] and nums[l] or nums[h]
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, h = 0, len(nums) - 1
while l <= h:
mid = (l + h) >> 1
if nums[mid] == target: return mid
elif nums[mid] >= nums[l]:
if nums[l] <= target < nums[mid]:
h = mid - 1
else:
l = mid + 1
else:
if nums[mid] < target <= nums[h]:
l = mid + 1
else:
h = mid - 1
return -1
431. 63. Unique Paths II
- DP
- Medium
- O(MN)
class Solution:
def uniquePathsWithObstacles(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
target = (m-1, n-1)
dp = [0] * n
dp[0] = int(grid[0][0] == 0)
for c in range(1, n):
dp[c] = int(dp[c-1] == 1 and grid[0][c] == 0)
for r in range(1, m):
dp[0] = int(dp[0] == 1 and grid[r][0] == 0)
for c in range(1, n):
dp[c] = dp[c] + dp[c-1] if grid[r][c] == 0 else 0
return dp[-1]
432. 143. Reorder List
- Linked List
- Medium
- O(N)
class Solution:
def reorderList(self, head: ListNode) -> None:
if not head: return head
def get_middle(head):
# return (n + 1) // 2 th node
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def reverse(head):
prev, curr = None, head
while curr: curr.next, prev, curr = prev, curr, curr.next
return prev
def merge_2_list(l1, l2):
curr = ListNode(None)
while l1 and l2:
curr.next, curr, l1 = l1, l1, l1.next
curr.next, curr, l2 = l2, l2, l2.next
if l1: curr.next = l1
# split
l1_tail = get_middle(head)
l2_head = l1_tail.next
l1_tail.next = None
# reverse
l2_head = reverse(l2_head)
# merge
merge_2_list(head, l2_head)
433. 338. Counting Bits
- DP / Bit
- Easy
- O(N)
Count number by number, bit by bit is NlogN.
DP(x) = DP(x & (x - 1)) + 1 x & (x - 1) is to clear the last set bit, that is, x is one bit more than x & (x - 1) thus dp relationship.
class Solution:
def countBits(self, num: int) -> List[int]:
dp = [0] * (num + 1)
for i in range(1, num + 1):
dp[i] = dp[i & (i - 1)] + 1
return dp
434. 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)
435. 104. Maximum Depth of Binary Tree
- Tree / DFS / BFS
- Easy
- O(N)
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
max_depth = 0
stack = [(root, 1)]
while stack:
node, depth = stack.pop()
if not node: continue
max_depth = max(max_depth, depth)
stack.extend([(child, depth + 1) for child in (node.left, node.right) if child])
return max_depth
436. 100. Same Tree
- Tree Traversal
- Easy
- O(N)
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
stack = [(p, q)]
while stack:
n1, n2 = stack.pop()
if n1 is None and n2 is None: continue
if n1 is None or n2 is None: return False
if n1.val != n2.val: return False
stack.append([n1.left, n2.left])
stack.append([n1.right, n2.right])
return True
437. 55. Jump Game
- Greedy / Sweep Line
- Medium
- O(N)
Go throught the locations, use a variable to keep track the farthest location we can jump to. As long as current location is less than that, we can try update the fartherst and move on.
class Solution:
def canJump(self, nums: List[int]) -> bool:
m = nums[0]
for i, step in enumerate(nums):
if i <= m: # reachable
m = max(m, i + step)
else: # non reachable
return False
if m >= len(nums) - 1: return True
return True
438. 101. Symmetric Tree
- Tree
- Easy
- O(N)
class Solution:
def iterative(self, root):
queue = deque()
queue.extend([root, root])
while queue:
node1 = queue.popleft()
node2 = queue.popleft()
if not (node1 or node2): continue
if not (node1 and node2): return False
if node1.val != node2.val: return False
queue.extend([node1.left, node2.right, node2.right, node1.left])
return True
def recursive(self, root):
def dfs(node1, node2):
if not (node1 or node2): return True
if not (node1 and node2): return False
return (node1.val == node2.val) and dfs(node1.right, node2.left) and dfs(node2.right, node1.left)
return dfs(root, root)
isSymmetric = iterative # recursive
439. [176]
440. 28. Implement strStr()
- KMP / Rabin-Karp
- Easy
- O(N)
def table(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 match(s, p):
n, m = len(s), len(p)
lps = table(p)
ans = []
j = 0
for i in range(n):
while j and s[i] != p[j]: j = lps[j] # don't match, use lps table to jump back
if s[i] == p[j]: j += 1
if j == m: return i - m + 1
return -1
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if needle == '': return 0
# for i in range(len(haystack) - len(needle) + 1):
# if haystack[i:i+ len(needle)] == needle: return i
# return -1
return match(haystack, needle)
441. 138. Copy List with Random Pointer
- Linked List
- Medium
- O(N)
Three pass no aux array.
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
# Insert each node's copy right after it, already copy .label
node = head
while node:
copy = Node(node.val)
copy.next, node.next, node = node.next, copy, node.next
# Set each copy's .random
node = head
while node:
node.next.random = None if not node.random else node.random.next
node = node.next.next
# Separate the copied list from the original, (re)setting every .next
node = head
ret = copy = None if not head else head.next
while node:
node.next = copy.next
node = node.next
copy.next = None if not node else node.next
copy = copy.next
return ret
442. 213. House Robber II
- DP
- Medium
- O(N)
Decompose into two house robber I problem. Each one exclude either tail or head where the circle meet.
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1: return nums[0]
def rob_1(i, j):
if i == j: return 0
maximum = -2 ** 32
pp, p = 0, 0
for num in nums[i: j]:
pp, p = p, max(pp + num, p)
maximum = max(maximum, p)
return maximum
return max(rob_1(1, n), rob_1(0, n-1))
443. 209. Minimum Size Subarray Sum
- Sliding Window
- Medium
- O(N)
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
l = window_sum = 0
min_size = INT_MAX = 2 ** 32
for r, num in enumerate(nums):
window_sum += num
while l <= r and window_sum >= s:
min_size = min(min_size, r - l + 1)
window_sum -= nums[l]
l += 1
return min_size if min_size != INT_MAX else 0
445. 448. Find All Numbers Disappeared in an Array
- Array
- Easy
- O(N)
class Solution:
def findDisappearedNumbers(self, nums):
# seen = [0] * len(nums)
# for num in nums:
# seen[num - 1] -= 1
# return [i for i, c in enumerate(seen, 1) if c == 0]
# for num in nums:
# nums[abs(num) - 1] = - abs(nums[abs(num) - 1])
# return [i for i, num in enumerate(nums, 1) if num > 0]
for i, num in enumerate(nums):
while i != nums[i] - 1 and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
results = [i for i, c in enumerate(nums, 1) if i != c]
return results
446. 525. Contiguous Array
- Prefix Sum
- Medium
- O(N)
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
prefix_sum = {0:-1}
accum = 0
max_length = 0
for i, num in enumerate(nums):
accum += 1 if num == 1 else -1
if accum in prefix_sum:
max_length = max(max_length, i - prefix_sum[accum])
else:
prefix_sum[accum] = i
return max_length
447. 20. Valid Parentheses
- Stack
- Easy
- O(N)
class Solution:
def isValid(self, s: str) -> bool:
matching = {'{': '}', '[': ']', '(': ')'}
stack = []
for parenthese in s:
if parenthese in matching:
stack.append(parenthese)
elif not len(stack): return False
elif matching[stack.pop()] != parenthese:
return False
return not stack
448. 1143. Longest Common Subsequence
- DP
- Medium
- O(NM)
def lcs1(A, B):
a, b = len(A), len(B)
x = [[0] * (b + 1) for _ in range(a + 1)]
for i in reversed(range(a)):
for j in reversed(range(b)):
if A[i] == B[j]:
x[i][j] = x[i + 1][j + 1] + 1
else:
x[i][j] = max(x[i + 1][j], x[i][j + 1])
return x[0][0]
def lcs2(A, B):
a, b = len(A), len(B)
x = [[0] * (b + 1) for _ in range(a + 1)]
for i in range(1, a + 1):
for j in range(1, b + 1):
if A[i-1] == B[j-1]:
x[i][j] = x[i - 1][j - 1] + 1
else:
x[i][j] = max(x[i - 1][j], x[i][j - 1])
return x[-1][-1]
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
return lcs2(text1, text2)
449. 532. K-diff Pairs in an Array
- HashMap
- Medium
- O(N)
class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
freqs = Counter(nums)
total = 0
for num in freqs:
if (k == 0 and freqs[num] > 1) or (k > 0 and num + k in freqs):
total += 1
return total
450. 141. Linked List Cycle
- Two Pointers / Linked List
- Easy
- O(N)
Floyd’s algorithm. -> follow up find the node when cycle started.
class Solution:
def hasCycle(self, head: ListNode) -> bool:
fast, slow = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow: return True
return False
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
def has_cycle(head):
fast, slow = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow: return slow
return None
intersect = has_cycle(head)
if not intersect: return None
node = head
while node != intersect:
node = node.next
intersect = intersect.next
return intersect
451. 19. Remove Nth Node From End of List
- Two Pointers
- Medium
- O(N)
Find the node before the target node, short the node.
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
sentinel = slow = ListNode(None, head)
fast = head
while fast and n: fast = fast.next; n -= 1
while fast: fast = fast.next; slow = slow.next
slow.next = slow.next.next
return sentinel.next
452. 160. Intersection of Two Linked Lists
- Two Pointers
- Easy
- O(N)
prefix a + shared suffix + prefix b = prefix b + shared suffix + prefix a
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
p, q = headA, headB
while p != q:
p = headB if not p else p.next
q = headA if not q else q.next
return p
453. 704. Binary Search
- Binary Search
- Easy
- O(logN)
# class Solution:
# def search(self, nums: List[int], target: int) -> int:
# i = bisect_left(nums, target)
# return i if i < len(nums) and nums[i] == target else -1
# class Solution:
# def search(self, nums: List[int], target: int) -> int:
# i = bisect_right(nums, target)
# return i - 1 if i > 0 and nums[i-1] == target else -1
class Solution:
def search(self, nums, target):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) >> 1
if nums[mid] < target:
lo = mid + 1
else:
hi = mid
return -1 if target != nums[lo] else lo
454. 122. Best Time to Buy and Sell Stock II
- Greedy
- Medium
- O(N)
Grab all possible gains.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
total_profit = 0
for prev, curr in zip(prices, prices[1:]):
if curr > prev: total_profit += curr - prev
return total_profit
455. 31. Next Permutation
- Two Pointers
- Medium
- O(N)
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
def swap(l, r): nums[l], nums[r] = nums[r], nums[l]
def reverse(l, r):
while l < r: swap(l, r); l += 1; r -= 1
n = len(nums)
l = n - 2
while l >= 0 and nums[l] >= nums[l + 1]: l -= 1
if l >= 0:
r = n - 1
while nums[r] <= nums[l]: r -= 1
swap(l, r)
reverse(l + 1, n - 1)
456. 350. Intersection of Two Arrays II
- HashMap
- Easy
- O(N)
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
c1 = Counter(nums1)
c2 = Counter(nums2)
result = []
for k in c1: result.extend([k] * min(c1[k], c2.get(k, 0)))
return result
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1, nums2 = sorted([nums1, nums2], key=len)
c1 = Counter(nums1)
result = []
for num in filter(lambda x: x in c1, nums2):
c1[num] -= 1
if c1[num] >= 0: result.append(num)
return result
457. 234. Palindrome Linked List
- Linked List
- Medium
- O(N)
For constant space solution, reverse from middle, two pointer change, then reverse from middle to recover.
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head or not head.next: return True
def get_midpoint(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def reverse(head):
prev, curr = None, head
while curr: prev, curr.next, curr = curr, prev, curr.next
return prev
mid = reverse(get_midpoint(head))
p, q = head, mid
while p and q and p != q:
if p.val != q.val:
reverse(mid)
return False
p = p.next
q = q.next
reverse(mid)
return True
458. 152. Maximum Product Subarray
- DP / Kadane
- Medium
- O(N)
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums: return 0
curr_min = curr_max = max_prod = nums[0]
for i, num in enumerate(nums[1:], 1):
if num < 0: curr_min, curr_max = curr_max, curr_min
curr_max = max(curr_max * num, num)
curr_min = min(curr_min * num, num)
max_prod = max(max_prod, curr_max)
return max_prod
459. 69. Sqrt(x)
- Binary Search / Math
- Easy
- O(logN)
class Solution:
def mySqrt(self, x: int) -> int:
lo, hi = 0, x
while lo <= hi:
mid = (lo + hi) >> 1
if mid * mid <= x and (mid + 1) * (mid + 1) > x:
return mid
if mid * mid > x:
hi = mid - 1
else:
lo = mid + 1
return -1
460. 48. Rotate Image
- Array / Inplace Swap
- Medium
- O(MN)
class Solution:
def rotate(self, matrix):
n = len(matrix)
for i in range(n - n // 2):
for j in range(n // 2):
matrix[i][j], matrix[~j][i], matrix[~i][~j], matrix[j][~i] = \
matrix[~j][i], matrix[~i][~j], matrix[j][~i], matrix[i][j]
461. 74. Search a 2D Matrix
- Binary Search
- Medium
- O(N + logM + logN)
Sorted list of sorted sublists. Sortedcontainers! Bisect(row max / row min) to find sublist then bisect the right sublist.
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
indices = [row[0] for row in matrix]
r = bisect.bisect_right(indices, target) - 1
if r >= len(matrix): return False
c = bisect.bisect_right(matrix[r], target) - 1
return matrix[r][c] == target
462. 169. Majority Element
- Boyer-Moore Voting Algorithm
- Easy
- O(N)
If for the current candidate in the prefix is not the majority, get rid of the prefix. Since in prefix we just got rid off, the most freq element only 1/2 votes. In the suffix, the true majority candidate is guaranteed to prevail.
class Solution:
def majorityElement(self, nums: List[int]) -> int:
count = 0
for num in nums:
if count == 0: candidate = num
count += 1 if candidate == num else -1
return candidate
463. 268. Missing Number
- Math / Bit Manipulation
- Easy
- O(N)
Total of range(n) - total of array.
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
return n * (n + 1) // 2 - sum(nums)
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
bits = reduce(xor, nums, 0)
full_bits = reduce(xor, range(n+1), 0)
return bits ^ full_bits
464. 118. Pascal’s Triangle
- DP
- Easy
- O(N)
DP[i,j] = DP[i-1][j-1] + DP[i-1][j]
class Solution:
def generate(self, num_rows):
triangle = []
for r in range(1, num_rows + 1):
row = [None for _ in range(r)]
row[0], row[-1] = 1, 1
for j in range(1, r-1):
row[j] = triangle[-1][j-1] + triangle[-1][j]
triangle.append(row)
return triangle
465. 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)
466. 876. Middle of the Linked List
- Linked List / Two Pointers
- Easy
- O(N)
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
slow, fast = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow
467. 189. Rotate Array
- Array
- Medium
- O(N)
Reverse whole then parts. Or swap until cycle.
class Solution:
# from nums = 1, 2, 3, 4, 5, 6 k = 2
# to 5, 6, 1, 2, 3, 4
def solution_reverse(self, nums, k):
# 1 2 3 4 5 6
# 6 5 4 3 2 1 reverse all
# 5 6 4 3 2 1 reverse up to k
# 5 6 1 2 3 4 revsere from k + 1 to end
def reverse_section(nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
n = len(nums)
k = k % n
reverse_section(nums, 0, n - 1)
reverse_section(nums, 0, k - 1)
reverse_section(nums, k, n - 1)
def solution_cycle(self, nums, k):
# 1 2 3 4 5 6
# 1 2 1 4 5 6 current = 2 tmp = 3
# 1 2 1 4 3 6 current = 4 tmp = 5
# 5 2 1 4 3 6 current = 0 tmp = 1
# 5 2 1 2 3 6
# 5 2 1 2 3 4
# 5 6 1 2 3 4
n = len(nums)
k %= n
start, count = 0, 0
while count < n:
current, tmp = start, nums[start]
while True:
next_ = (current + k) % n
nums[next_], tmp = tmp, nums[next_]
current = next_
count += 1
if current == start:
break
start += 1
rotate = solution_cycle # solution_reverse
468. 84. Largest Rectangle in Histogram
- Stack
- Hard
- O(N)
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
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
469. 242. Valid Anagram
- HashMap
- Easy
- O(N)
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return Counter(s) == Counter(t)
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t): return False
char_freqs = Counter(s)
for c in t:
if not char_freqs.get(c, 0): return False
char_freqs[c] -= 1
return True
470. 13. Roman to Integer
- Loop?
- Medium
- O(N)
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
mapping = {
'M': 1000,
'D': 500,
'C': 100,
'L': 50,
'X': 10,
'V': 5,
'I': 1
}
total = 0
for l, r in zip(s, s[1:]):
ln, rn = mapping[l], mapping[r]
total += -ln if ln < rn else ln
return total + mapping[s[-1]]
471. 438. Find All Anagrams in a String
- Sliding Window
- Medium
- O(N)
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
n = len(p)
solution = []
# edge case
if len(s) < len(p): return solution
# target
req_freq = Counter(p)
# initial window
window = Counter(filter(lambda x: x in req_freq, s[:n]))
to_match = len(req_freq)
for char in req_freq: to_match -= window[char] == req_freq[char]
if not to_match: solution.append(0)
# sliding window
for i, (in_char, out_char) in enumerate(zip(s[n:], s), n):
# if in_char in req_freq:
# if window[in_char] == req_freq[in_char]: to_match += 1
# if window[in_char] + 1 == req_freq[in_char]: to_match -= 1
# window.update(in_char)
# if out_char in req_freq:
# if window[out_char] == req_freq[out_char]: to_match += 1
# if window[out_char] - 1 == req_freq[out_char]: to_match -= 1
# window.subtract(out_char)
# if not to_match: solution.append(i - n + 1)
# NK but much simpler
if in_char in req_freq: window[in_char] += 1
if out_char in req_freq: window[out_char] -= 1
if window == req_freq: solution.append(i - n + 1)
return solution
472. 206. Reverse Linked List
- Linked List
- Easy
- O(N)
None 1 --> 2 --> 3
prev curr curr.next
None <- 1 --> 2 --> 3
prev curr
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev, curr = None, head
while curr: prev, curr.next, curr = curr, prev, curr.next
return prev