Templates

Backtracking 2
Backtracking 1
Binary Search
BFS on Tree
DFS on Tree
BFS on Graphs
DFS on Graphs
BFS on a Matrix
Mono Stack
Sliding Window (Fixed Size)
Sliding Window Flexible - Longest
Sliding Window Flexible - Shortest
Topological Sort
Trie
Union Find
1def 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
12
Read the article about this template.
1ans = []
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()
16
Read the article about this template.
1def 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)
11
Read the article about this template.
1def 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)
7
Read the article about this template.
1num_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)
28
Read the article about this template.
1def 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)
8
Read the article about this template.
1def 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
9
Read the article about this template.
1def 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
11
Read the article about this template.
1def 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
11
Read the article about this template.
1def 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
24
Read the article about this template.
1class 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)
11
Read the article about this template.
1class 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
Read the article about this template.