Templates

Learn more about this template in the detailed article

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

Learn more about this template in the detailed article

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

Learn more about this template in the detailed article

1def 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
13

Learn more about this template in the detailed article

1def 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
10

Learn more about this template in the detailed article

1def 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)
10

Learn more about this template in the detailed article

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

Learn more about this template in the detailed article

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

Learn more about this template in the detailed article

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

Learn more about this template in the detailed article

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

Learn more about this template in the detailed article

1def build_prefix_sum(arr):
2    n = len(arr)
3    prefix_sum = [0] * n
4    prefix_sum[0] = arr[0]
5    for i in range(1, n):
6        prefix_sum[i] = prefix_sum[i-1] + arr[i]
7    return prefix_sum
8
9# Query sum of range [left, right] (inclusive)
10def query_range(prefix_sum, left, right):
11    if left == 0:
12        return prefix_sum[right]
13    return prefix_sum[right] - prefix_sum[left-1]
14

Learn more about this template in the detailed article

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

Learn more about this template in the detailed article

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

Learn more about this template in the detailed article

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

Learn more about this template in the detailed article

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

Learn more about this template in the detailed article

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

Learn more about this template in the detailed article

1def two_pointers_opposite(arr):
2    left, right = 0, len(arr) - 1
3    while left < right:
4        # Process current elements
5        current = process(arr[left], arr[right])
6        
7        # Update pointers based on condition
8        if condition(arr[left], arr[right]):
9            left += 1
10        else:
11            right -= 1
12

Learn more about this template in the detailed article

1def two_pointers_same(arr):
2    slow, fast = 0, 0
3    while fast < len(arr):
4        # Process current elements
5        current = process(arr[slow], arr[fast])
6        
7        # Update pointers based on condition
8        if condition(arr[slow], arr[fast]):
9            slow += 1
10        
11        # Fast pointer always moves forward
12        fast += 1
13

Learn more about this template in the detailed article

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