Facebook Pixel

You are on level: Student

0%
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section

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 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
1def greedy(items):
2    # 1. Sort by the greedy key (deadline, end time, size, ratio, ...)
3    items.sort(key=greedy_key)
4    result = 0
5    state = initial_state()
6    for item in items:
7        # 2. Take the item only if the locally best choice is valid
8        if is_feasible(item, state):
9            result += take(item, state)
10    # 3. Correctness relies on an exchange argument, not just passing tests
11    return result
12
Learn more about this template in the detailed article
1def interval_pattern(intervals):
2    # 1. Sort by start time
3    intervals.sort(key=lambda x: x[0])
4    result = []
5    for start, end in intervals:
6        # 2. Overlap with the last kept interval? end >= next start
7        if result and start <= result[-1][1]:
8            # Merge: extend the end of the last interval
9            result[-1][1] = max(result[-1][1], end)
10        else:
11            # 3. No overlap: keep this interval as-is
12            result.append([start, end])
13    return result
14
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            indegree[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