### Two Pointers (Opposite Ends) :::divider ::: :::code{lang="python" filename="Two pointers: one input, opposite ends"} def two_pointers_opposite(nums): l, r = 0, len(nums) - 1 while l < r: # use nums[l], nums[r] # if condition: # l += 1 # else: # r -= 1 pass ::: :::divider ::: :::code{lang="python" filename="Two pointers: two inputs, exhaust both"} def two_pointers_two_inputs(a, b): i = j = 0 res = [] while i < len(a) and j < len(b): # if a[i] <= b[j]: # res.append(a[i]); i += 1 # else: # res.append(b[j]); j += 1 pass while i < len(a): res.append(a[i]); i += 1 while j < len(b): res.append(b[j]); j += 1 return res ::: :::divider ::: :::code{lang="python" filename="Sliding window"} def sliding_window(nums): l = 0 window = 0 # sum / count / hashmap ans = 0 for r in range(len(nums)): # expand window using nums[r] while False: # window invalid # shrink using nums[l] l += 1 ans = max(ans, r - l + 1) return ans ::: :::divider ::: :::code{lang="python" filename="Prefix sum"} def build_prefix(nums): pref = [0] * (len(nums) + 1) for i, x in enumerate(nums): pref[i + 1] = pref[i] + x return pref # sum of nums[l..r] = pref[r + 1] - pref[l] ::: :::divider ::: :::code{lang="python" filename="Efficient string building"} def build_string(parts): return "".join(parts) ::: :::divider ::: :::code{lang="python" filename="Linked list: fast & slow pointer"} class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def fast_slow(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # if slow is fast: cycle return slow ::: :::divider ::: :::code{lang="python" filename="Reverse a linked list"} def reverse_list(head): prev = None cur = head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev ::: :::divider ::: :::code{lang="python" filename="Number of subarrays with exact criteria"} def exactly_k(nums, k): return at_most_k(nums, k) - at_most_k(nums, k - 1) def at_most_k(nums, k): l = 0 ans = 0 # window state here for r in range(len(nums)): # add nums[r] while False: # window invalid (>k) # remove nums[l] l += 1 ans += r - l + 1 return ans ::: :::divider ::: :::code{lang="python" filename="Monotonic increasing stack"} def monotonic_stack(nums): st = [] # indices for i, x in enumerate(nums): while st and nums[st[-1]] > x: j = st.pop() # nums[j]'s next smaller is i st.append(i) return st ::: :::divider ::: :::code{lang="python" filename="Binary tree: DFS (recursive)"} class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def dfs(root): if not root: return 0 left = dfs(root.left) right = dfs(root.right) return 1 + max(left, right) ::: :::divider ::: :::code{lang="python" filename="Binary tree: DFS (iterative)"} def dfs_iterative(root): if not root: return st = [root] while st: node = st.pop() # process node if node.right: st.append(node.right) if node.left: st.append(node.left) ::: :::divider ::: :::code{lang="python" filename="Binary tree: BFS"} from collections import deque def bfs(root): if not root: return q = deque([root]) while q: node = q.popleft() # process node if node.left: q.append(node.left) if node.right: q.append(node.right) ::: :::divider ::: :::code{lang="python" filename="Graph: DFS (recursive)"} def graph_dfs_recursive(graph): n = len(graph) seen = [False] * n def dfs(u): seen[u] = True for v in graph[u]: if not seen[v]: dfs(v) for i in range(n): if not seen[i]: dfs(i) ::: :::divider ::: :::code{lang="python" filename="Graph: DFS (iterative)"} def graph_dfs_iterative(graph, start=0): n = len(graph) seen = [False] * n st = [start] while st: u = st.pop() if seen[u]: continue seen[u] = True for v in graph[u]: if not seen[v]: st.append(v) return seen ::: :::divider ::: :::code{lang="python" filename="Graph: BFS"} from collections import deque def graph_bfs(graph, start=0): n = len(graph) dist = [-1] * n q = deque([start]) dist[start] = 0 while q: u = q.popleft() for v in graph[u]: if dist[v] == -1: dist[v] = dist[u] + 1 q.append(v) return dist ::: :::divider ::: :::code{lang="python" filename="Top K with heap"} import heapq def top_k(nums, k): return heapq.nlargest(k, nums) ::: :::divider ::: :::code{lang="python" filename="Binary search"} def binary_search(nums, target): l, r = 0, len(nums) - 1 while l <= r: m = (l + r) // 2 if nums[m] == target: return m if nums[m] < target: l = m + 1 else: r = m - 1 return -1 ::: :::divider ::: :::code{lang="python" filename="Binary search: left‑most insertion (lower bound)"} def lower_bound(nums, target): l, r = 0, len(nums) while l < r: m = (l + r) // 2 if nums[m] < target: l = m + 1 else: r = m return l ::: :::divider ::: :::code{lang="python" filename="Binary search: right‑most insertion (upper bound)"} def upper_bound(nums, target): l, r = 0, len(nums) while l < r: m = (l + r) // 2 if nums[m] <= target: l = m + 1 else: r = m return l ::: :::divider ::: ### Binary search for greedy problems :::code{lang="python" filename="Minimum"} def first_true(lo, hi, ok): while lo < hi: mid = (lo + hi) // 2 if ok(mid): hi = mid else: lo = mid + 1 return lo ::: :::code{lang="python" filename="Maximum"} def last_true(lo, hi, ok): while lo < hi: mid = (lo + hi + 1) // 2 if ok(mid): lo = mid else: hi = mid - 1 return lo ::: :::divider ::: :::code{lang="python" filename="Backtracking "} def backtrack(nums): res = [] path = [] def dfs(i): # if i == len(nums): # res.append(path.copy()); return # choose # path.append(nums[i]) # dfs(i + 1) # path.pop() # skip # dfs(i + 1) pass dfs(0) return res ::: :::divider ::: :::code{lang="python" filename="Dynamic programming: top‑down memo"} from functools import lru_cache def solve(nums, k): @lru_cache(None) def dp(i, used): if i == len(nums): return 0 best = dp(i + 1, used) if used < k: best = max(best, nums[i] + dp(i + 1, used + 1)) return best return dp(0, 0) ::: :::divider ::: :::code{lang="python" filename="Build a trie"} class TrieNode: def __init__(self): self.children = {} self.end = False class Trie: def __init__(self): self.root = TrieNode() def insert(self, word): node = self.root for ch in word: if ch not in node.children: node.children[ch] = TrieNode() node = node.children[ch] node.end = True def search(self, word): node = self.root for ch in word: if ch not in node.children: return False node = node.children[ch] return node.end def starts_with(self, prefix): node = self.root for ch in prefix: if ch not in node.children: return False node = node.children[ch] return True ::: :::divider ::: :::code{lang="python" filename="Dijkstra’s algorithm"} import heapq def dijkstra(graph, start): # graph[u] = [(v, w)] n = len(graph) INF = 10**18 dist = [INF] * n dist[start] = 0 pq = [(0, start)] while pq: d, u = heapq.heappop(pq) if d != dist[u]: continue for v, w in graph[u]: nd = d + w if nd < dist[v]: dist[v] = nd heapq.heappush(pq, (nd, v)) return dist ::: :::divider ::: :::code{lang="python" filename="Binary Indexed Tree (Fenwick Tree)"} class FenwickTree: def __init__(self, n: int): self.n = n self.tree = [0] * (n + 1) def lsb(i: int) -> int: """Least significant bit.""" return i & -i def update(self, i: int, delta: int) -> None: """Add delta to index i (1-indexed).""" while i <= self.n: self.tree[i] += delta i += self.lsb(i) def query(self, i: int) -> int: res = 0 while i > 0: res += self.tree[i] i -= self.lsb(i) return res def range_query(self, l: int, r: int) -> int: """Sum of range [l..r].""" return self.query(r) - self.query(l - 1) :::

Templates

Two Pointers (Opposite Ends)

Graphs