1function dfs(start_index, [...additional states]):
2 if is_leaf(start_index):
3 return 1
4 ans = initial_value
5 for edge in get_edges(start_index, [...additional states]):
6 if additional states:
7 update([...additional states])
8 ans = aggregate(ans, dfs(start_index + len(edge), [...additional states]))
9 if additional states:
10 revert([...additional states])
11 return ans
121ans = []
2def dfs(start_index, path, [...additional states]):
3 if is_leaf(start_index):
4 ans.append(path[:]) # add a copy of the path to the result
5 return
6 for edge in get_edges(start_index, [...additional states]):
7 # prune if needed
8 if not is_valid(edge):
9 continue
10 path.add(edge)
11 if additional states:
12 update(...additional states)
13 dfs(start_index + len(edge), path, [...additional states])
14 # revert(...additional states) if necessary e.g. permutations
15 path.pop()
161def binary_search(arr: List[int], target: int) -> int:
2 left, right = 0, len(arr) - 1
3 first_true_index = -1
4 while left <= right:
5 mid = (left + right) // 2
6 if feasible(mid):
7 first_true_index = mid
8 right = mid - 1
9 else:
10 left = mid + 1
11
12 return first_true_index
131def bfs(root):
2 queue = deque([root])
3 while len(queue) > 0:
4 node = queue.popleft()
5 for child in node.children:
6 if is_goal(child):
7 return FOUND(child)
8 queue.append(child)
9 return NOT_FOUND
101def dfs(root, target):
2 if root is None:
3 return None
4 if root.val == target:
5 return root
6 left = dfs(root.left, target)
7 if left is not None:
8 return left
9 return dfs(root.right, target)
101def bfs(root):
2 queue = deque([root])
3 visited = set([root])
4 while len(queue) > 0:
5 node = queue.popleft()
6 for neighbor in get_neighbors(node):
7 if neighbor in visited:
8 continue
9 queue.append(neighbor)
10 visited.add(neighbor)
111def dfs(root, visited):
2 for neighbor in get_neighbors(root):
3 if neighbor in visited:
4 continue
5 visited.add(neighbor)
6 dfs(neighbor, visited)
71num_rows, num_cols = len(grid), len(grid[0])
2def get_neighbors(coord):
3 row, col = coord
4 delta_row = [-1, 0, 1, 0]
5 delta_col = [0, 1, 0, -1]
6 res = []
7 for i in range(len(delta_row)):
8 neighbor_row = row + delta_row[i]
9 neighbor_col = col + delta_col[i]
10 if 0 <= neighbor_row < num_rows and 0 <= neighbor_col < num_cols:
11 res.append((neighbor_row, neighbor_col))
12 return res
13
14from collections import deque
15
16def bfs(starting_node):
17 queue = deque([starting_node])
18 visited = set([starting_node])
19 while len(queue) > 0:
20 node = queue.popleft()
21 for neighbor in get_neighbors(node):
22 if neighbor in visited:
23 continue
24 # Do stuff with the node if required
25 # ...
26 queue.append(neighbor)
27 visited.add(neighbor)
281def mono_stack(insert_entries):
2 stack = []
3 for entry in insert_entries:
4 while stack and stack[-1] <= entry:
5 stack.pop()
6 # Do something with the popped item here
7 stack.append(entry)
81def sliding_window_fixed(input, window_size):
2 ans = window = input[0:window_size]
3 for right in range(window_size, len(input)):
4 left = right - window_size
5 remove input[left] from window
6 append input[right] to window
7 ans = optimal(ans, window)
8 return ans
91def sliding_window_flexible_longest(input):
2 initialize window, ans
3 left = 0
4 for right in range(len(input)):
5 append input[right] to window
6 while invalid(window): # update left until window is valid again
7 remove input[left] from window
8 left += 1
9 ans = max(ans, window) # window is guaranteed to be valid here
10 return ans
111def sliding_window_flexible_shortest(input):
2 initialize window, ans
3 left = 0
4 for right in range(len(input)):
5 append input[right] to window
6 while valid(window):
7 ans = min(ans, window) # window is guaranteed to be valid here
8 remove input[left] from window
9 left += 1
10 return ans
111def find_indegree(graph):
2 indegree = { node: 0 for node in graph } # dict
3 for node in graph:
4 for neighbor in graph[node]:
5 indgree[neighbor] += 1
6 return indegree
7
8
9def topo_sort(graph):
10 res = []
11 q = deque()
12 indegree = find_indegree(graph)
13 for node in indegree:
14 if indegree[node] == 0:
15 q.append(node)
16 while len(q) > 0:
17 node = q.popleft()
18 res.append(node)
19 for neighbor in graph[node]:
20 indegree[neighbor] -= 1
21 if indegree[neighbor] == 0:
22 q.append(neighbor)
23 return res if len(graph) == len(res) else None
241class Node:
2 def __init__(self, value):
3 self.value = value
4 self.children = {}
5
6 def insert(self, s, idx):
7 # idx: index of the current character in s
8 if idx != len(s):
9 self.children.setdefault(s[idx], Node(s[idx]))
10 self.children.get(s[idx]).insert(s, idx + 1)
111class UnionFind:
2 def __init__(self):
3 self.id = {}
4
5 def find(self, x):
6 y = self.id.get(x, x)
7 if y != x:
8 self.id[x] = y = self.find(y)
9 return y
10
11 def union(self, x, y):
12 self.id[self.find(x)] = self.find(y)
13