
agent-alchemy-cs-tools
Competitive programming and LeetCode problem-solving with educational explanations
- version
- 0.1.0
- GitHub stars
- 45
Install
/plugin install agent-alchemy-cs-tools@agent-alchemyRun it inside Claude Code after adding the marketplace with /plugin marketplace add sequenzia/agent-alchemy.
Contents
Discovered from sourceSkills 8
Data Structure Patterns
This skill provides recognition signals, core ideas, Python templates, and pitfall guidance for seven advanced data structure patterns. Use it when a problem's constraints or access patterns suggest a specialized structure beyond basic arrays, hash maps, or linked lists. Each pattern section follows a consistent format: when to reach for it, how it works, a clean implementation template, and the mistakes that cost time in practice.
Pattern Recognition Table
| Trigger Signals | Technique | Typical Complexity |
|---|---|---|
| "k-th largest/smallest", "top K", "merge K sorted" | Heap / Priority Queue | O(n log k) |
| "next greater/smaller element", "sliding window max/min" | Monotonic Stack / Queue | O(n) |
| "prefix matching", "autocomplete", "word search in grid" | Trie | O(L) per operation |
| "range query + point update", "range min/max/sum" | Segment Tree | O(log n) per query/update |
| "prefix sums with updates", "count of elements less than X" | Fenwick Tree (BIT) | O(log n) per query/update |
| "balanced parentheses", "evaluate expression", "nested structures" | Stack-Based Parsing | O(n) |
| "rank of element", "k-th smallest in dynamic set", "floor/ceiling" | Ordered Set (SortedList) | O(log n) per operation |
Constraint-to-Technique Mapping
When the problem statement does not name a structure directly, use constraints to narrow the choice:
- n <= 10^5 with repeated range queries -- Segment Tree or Fenwick Tree. Prefer Fenwick when only prefix sums are needed; use Segment Tree for arbitrary range operations.
- n <= 10^6 and "next greater" or "span" language -- Monotonic Stack. Linear time is essential at this scale.
- String dictionary with prefix lookups -- Trie. Hash maps work for exact match but not prefix enumeration.
- "Top K" or "k-th element" with streaming data -- Heap. A size-k heap avoids sorting the full dataset.
- Dynamic insertions + rank/order queries -- SortedList. Python lacks a built-in balanced BST; sortedcontainers fills this gap.
- Nested or recursive syntax (math expressions, HTML tags) -- Stack-Based Parsing. The stack mirrors the nesting depth.
Heap / Priority Queue
Recognition Signals
- "Find the k-th largest/smallest element"
- "Merge k sorted lists/arrays"
- "Continuously add elements and query the median or top-K"
- "Schedule tasks by priority"
Core Idea A heap maintains partial order so that the min (or max) element is always accessible in O(1) with O(log n) insertion and extraction. For "top K" problems, maintain a min-heap of size k: every new element either replaces the root or is discarded, guaranteeing O(n log k) total work.
Python Template
import heapq
from typing import List
def top_k_frequent(nums: List[int], k: int) -> List[int]:
from collections import Counter
freq = Counter(nums)
# Min-heap of size k on frequency
return heapq.nlargest(k, freq.keys(), key=freq.get)
def merge_k_sorted(lists: List[List[int]]) -> List[int]:
result: list[int] = []
heap: list[tuple[int, int, int]] = []
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst[0], i, 0))
while heap:
val, list_idx, elem_idx = heapq.heappop(heap)
result.append(val)
if elem_idx + 1 < len(lists[list_idx]):
heapq.heappush(heap, (lists[list_idx][elem_idx + 1], list_idx, elem_idx + 1))
return result
Key Edge Cases
- Empty input lists or sublists in merge-k scenarios
- All elements identical (heap still works, but deduplication may be needed)
- k equals n (heap degenerates; sorting may be simpler)
- Negative numbers with max-heap emulation (negate values for
heapq)
Common Mistakes
- Forgetting that Python's
heapqis a min-heap; for max-heap, negate values or useheapq.nlargest - Not including a tiebreaker index in the heap tuple, causing crashes on uncomparable objects
- Using
heapifythen manually inserting withoutheappush(breaks the heap invariant)
Monotonic Stack / Queue
Recognition Signals
- "Next greater element" or "next smaller element"
- "Sliding window maximum/minimum"
- "Largest rectangle in histogram"
- "Daily temperatures / stock span"
Core Idea A monotonic stack maintains elements in strictly increasing or decreasing order. When a new element arrives, pop all elements that violate the monotonic property -- each popped element has found its "next greater" (or "next smaller"). Every element is pushed and popped at most once, yielding O(n) total. For sliding windows, a monotonic deque adds front-eviction to maintain the window boundary.
Python Template
from collections import deque
from typing import List
def next_greater_element(nums: List[int]) -> List[int]:
n = len(nums)
result = [-1] * n
stack: list[int] = [] # indices
for i in range(n):
while stack and nums[stack[-1]] < nums[i]:
result[stack.pop()] = nums[i]
stack.append(i)
return result
def sliding_window_max(nums: List[int], k: int) -> List[int]:
dq: deque[int] = deque() # indices, front = max
result: list[int] = []
for i, val in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft()
while dq and nums[dq[-1]] <= val:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
Key Edge Cases
- Array with all equal elements (no element is "greater"; result is all -1)
- Single-element array (result is trivially -1)
- Circular array variant (iterate 2n elements using modular indexing)
- Window size k = 1 (output equals input)
Common Mistakes
- Storing values instead of indices on the stack (cannot determine window boundaries)
- Using the wrong comparison direction (< vs. <=) and getting a non-strictly monotonic stack
- Forgetting to handle the circular case by iterating
range(2 * n)
Trie
Recognition Signals
- "Find all words with a given prefix"
- "Word search in a 2D grid with a dictionary"
- "Autocomplete / typeahead suggestions"
- "Maximum XOR of two numbers in an array"
Core Idea A trie stores strings character-by-character in a tree where each edge represents one character. Shared prefixes share nodes, making prefix lookups O(L) regardless of dictionary size. For XOR tries, store numbers bit-by-bit (MSB to LSB) and greedily choose the opposite bit at each level.
Python Template
from typing import Optional
class TrieNode:
__slots__ = ("children", "is_end", "count")
def __init__(self) -> None:
self.children: dict[str, "TrieNode"] = {}
self.is_end: bool = False
self.count: int = 0 # words passing through this node
class Trie:
def __init__(self) -> None:
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.count += 1
node.is_end = True
def starts_with(self, prefix: str) -> int:
"""Return count of words with given prefix."""
node = self.root
for ch in prefix:
if ch not in node.children:
return 0
node = node.children[ch]
return node.count
Key Edge Cases
- Empty string insertion (root itself becomes an end node)
- Prefix that is also a complete word (must check
is_endseparately from prefix existence) - Unicode or case-sensitive input (normalize before insertion)
- Deletion requires decrementing counts and pruning childless nodes
Common Mistakes
- Not distinguishing "prefix exists" from "exact word exists" (missing
is_endcheck) - Building a trie for exact-match-only problems where a hash set suffices
- Forgetting
__slots__on trie nodes, leading to high memory usage on large dictionaries
Segment Tree
Recognition Signals
- "Range sum/min/max query with point updates"
- "Count of elements in a range satisfying a condition"
- "Range update + range query" (lazy propagation)
Core Idea A segment tree is a binary tree where each leaf represents one element and each internal node stores an aggregate (sum, min, max) of its children's range. Queries and updates both traverse O(log n) nodes. Lazy propagation defers range updates by tagging nodes, applying pending updates only when a child is accessed, keeping range updates at O(log n).
Python Template
from typing import List
class SegmentTree:
"""Range sum query with point update."""
def __init__(self, data: List[int]) -> None:
self.n = len(data)
self.tree = [0] * (2 * self.n)
# Build leaves
for i in range(self.n):
self.tree[self.n + i] = data[i]
# Build internal nodes
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def update(self, idx: int, val: int) -> None:
idx += self.n
self.tree[idx] = val
while idx > 1:
idx >>= 1
self.tree[idx] = self.tree[2 * idx] + self.tree[2 * idx + 1]
def query(self, left: int, right: int) -> int:
"""Sum of data[left:right] (half-open interval)."""
res = 0
left += self.n
right += self.n
while left < right:
if left & 1:
res += self.tree[left]
left += 1
if right & 1:
right -= 1
res += self.tree[right]
left >>= 1
right >>= 1
return res
Key Edge Cases
- Single-element array (tree has two levels; queries are trivial)
- Query range equals the full array (should return root value)
- Index-0 vs. index-1 conventions (this template uses 0-indexed input)
- Overflow on large sums (use Python's arbitrary-precision integers or explicit modular arithmetic)
Common Mistakes
- Off-by-one in the query range (half-open
[left, right)vs. closed[left, right]) - Forgetting to propagate lazy values before accessing children in lazy segment trees
- Building with
2 * nsize but using 1-indexed logic (need4 * nfor 1-indexed recursive style)
Fenwick Tree (BIT)
Recognition Signals
- "Prefix sum queries with dynamic updates"
- "Count of elements less than X after insertions"
- "Inversion count in an array"
- "2D prefix sums with updates"
Core Idea
A Fenwick tree (Binary Indexed Tree) uses the binary representation of indices to partition prefix sums across O(log n) nodes. Each node at index i stores the sum of a range whose length equals the lowest set bit of i. Updates and prefix queries both run in O(log n). Fenwick trees use less memory and have smaller constants than segment trees but only support prefix-based queries natively. Range [l, r] is computed as prefix(r) - prefix(l - 1).
Python Template
from typing import List
class FenwickTree:
def __init__(self, n: int) -> None:
self.n = n
self.tree = [0] * (n + 1) # 1-indexed
def update(self, i: int, delta: int) -> None:
"""Add delta to element at 1-indexed position i."""
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def query(self, i: int) -> int:
"""Return prefix sum from index 1 to i (inclusive)."""
s = 0
while i > 0:
s += self.tree[i]
i -= i & (-i)
return s
def range_query(self, left: int, right: int) -> int:
"""Sum of elements in [left, right], 1-indexed."""
return self.query(right) - self.query(left - 1)
@classmethod
def from_array(cls, data: List[int]) -> "FenwickTree":
ft = cls(len(data))
for i, val in enumerate(data, 1):
ft.update(i, val)
return ft
Key Edge Cases
- Zero-indexed input (convert to 1-indexed before calling update/query)
- Querying index 0 (should return 0, which the while loop handles naturally)
- Negative values in updates (Fenwick handles deltas, not absolute values)
Common Mistakes
- Using 0-indexed positions (index 0 causes an infinite loop in
updatebecause0 & (-0) == 0) - Confusing "set value" with "add delta" (Fenwick stores cumulative deltas, not absolute values)
- Forgetting that
range_query(1, 0)should return 0 (guard against inverted ranges)
Stack-Based Parsing
Recognition Signals
- "Check if parentheses/brackets are balanced"
- "Evaluate arithmetic expression with operator precedence"
- "Decode nested encoded strings like
3[a2[c]]" - "Basic calculator with +, -, *, /, and parentheses"
Core Idea A stack naturally mirrors nesting depth: push context when entering a deeper level (opening bracket, new sub-expression) and pop when leaving it (closing bracket, operator resolution). For expression evaluation, use two stacks (operands and operators) or convert to reverse Polish notation first. The stack preserves the outer context while you process the inner context; restoring is a simple pop.
Python Template
from typing import List
def eval_expression(s: str) -> int:
"""Evaluate expression with +, -, and parentheses."""
stack: list[tuple[int, int]] = [] # (result_before_paren, sign_before_paren)
result = 0
num = 0
sign = 1
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch)
elif ch in "+-":
result += sign * num
num = 0
sign = 1 if ch == "+" else -1
elif ch == "(":
stack.append((result, sign))
result = 0
sign = 1
elif ch == ")":
result += sign * num
num = 0
prev_result, prev_sign = stack.pop()
result = prev_result + prev_sign * result
result += sign * num
return result
def is_balanced(s: str) -> bool:
"""Check if brackets are balanced."""
pairs = {"(": ")", "[": "]", "{": "}"}
stack: list[str] = []
for ch in s:
if ch in pairs:
stack.append(pairs[ch])
elif ch in pairs.values():
if not stack or stack.pop() != ch:
return False
return len(stack) == 0
Key Edge Cases
- Empty string (should be considered balanced / evaluate to 0)
- Unary minus at the start of an expression (e.g.,
-3 + 5) - Deeply nested structures that could overflow recursion (iterative stack avoids this)
Common Mistakes
- Not handling multi-digit numbers (accumulate digits before processing operators)
- Forgetting to process the last number after the loop ends (no trailing operator triggers it)
- Popping from an empty stack on mismatched closing brackets (check
len(stack)first)
Ordered Set (SortedList)
Recognition Signals
- "Find the k-th smallest element in a dynamic collection"
- "Count elements in a range [lo, hi] with insertions and deletions"
- "Floor/ceiling of a value in a dynamic set"
- "Sliding window median"
Core Idea
Python lacks a built-in balanced BST, but sortedcontainers.SortedList provides O(log n) insertion, deletion, and index-based access with excellent constant factors. It supports bisect for floor/ceiling, positional indexing for rank queries, and islice for range iteration. For contest environments without third-party imports, a Fenwick tree over a value-indexed array can simulate rank queries.
Python Template
from sortedcontainers import SortedList
from typing import List, Optional
def sliding_window_median(nums: List[int], k: int) -> List[float]:
sl = SortedList()
result: list[float] = []
for i, val in enumerate(nums):
sl.add(val)
if len(sl) > k:
sl.remove(nums[i - k])
if len(sl) == k:
if k % 2 == 1:
result.append(float(sl[k // 2]))
else:
result.append((sl[k // 2 - 1] + sl[k // 2]) / 2.0)
return result
def floor_ceiling(sl: SortedList, val: int) -> tuple[Optional[int], Optional[int]]:
"""Return (floor, ceiling) of val in the sorted list."""
idx = sl.bisect_right(val)
floor = sl[idx - 1] if idx > 0 else None
ceil_idx = sl.bisect_left(val)
ceiling = sl[ceil_idx] if ceil_idx < len(sl) else None
return floor, ceiling
def count_in_range(sl: SortedList, lo: int, hi: int) -> int:
"""Count elements in [lo, hi] inclusive."""
return sl.bisect_right(hi) - sl.bisect_left(lo)
Key Edge Cases
- Duplicate values (SortedList allows duplicates; use
discardto remove one occurrence, not all) - Empty collection (bisect returns 0; floor/ceiling should return None)
- Value exactly equal to an existing element (floor and ceiling are both that element)
- Large n with frequent add/remove (handles 10^5-10^6 operations efficiently)
Common Mistakes
- Using
removeon a value not in the list (raises ValueError; usediscardfor safe removal) - Confusing
bisect_leftandbisect_rightfor floor/ceiling logic (left for ceiling, right for floor) - Assuming SortedList is available everywhere (some contest judges lack
sortedcontainers; have a BIT fallback)
Dynamic Programming Patterns
This reference covers eight foundational dynamic programming patterns commonly encountered in algorithmic problem solving. Each pattern includes recognition signals to identify when a problem maps to the technique, a working Python template, and specific edge cases and mistakes to watch for. Load this skill when solving optimization, counting, or subsequence problems that exhibit optimal substructure and overlapping subproblems.
General DP Approach
Before selecting a specific pattern, apply this checklist:
- Identify the state: What information do you need to uniquely describe a subproblem? (index, remaining capacity, bitmask of visited nodes)
- Define the recurrence: How does the answer for the current state relate to answers for smaller states?
- Establish base cases: What are the trivial subproblems with known answers?
- Determine iteration order: Ensure every state is computed before it is needed (bottom-up) or use memoization (top-down)
- Optimize space: If dp[i] depends only on dp[i-1] (or a small window), use rolling arrays instead of the full table
Pattern Recognition Table
| Trigger Signals | Technique | Typical Complexity |
|---|---|---|
| "count the number of ways", "how many distinct paths" | Fibonacci / Climbing Stairs | O(N) time, O(1) space |
| "maximize value with weight limit", "partition into two equal subsets" | 0/1 Knapsack | O(N * W) time, O(W) space |
| "longest common subsequence", "minimum edit operations" | LCS / Edit Distance | O(N * M) time, O(min(N, M)) space |
| "longest increasing subsequence", "minimum number of envelopes" | LIS | O(N log N) time, O(N) space |
| "unique paths in grid", "minimum cost to reach bottom-right" | Grid DP | O(R * C) time, O(C) space |
| "maximum subarray sum", "best contiguous segment" | Kadane's Algorithm | O(N) time, O(1) space |
| "fewest coins to make amount", "ways to combine denominations" | Coin Change / Unbounded Knapsack | O(N * amount) time, O(amount) space |
| "visit all nodes exactly once", "assign N items optimally", N <= 20 | Bitmask DP | O(2^N * N) time, O(2^N) space |
Constraint-to-Technique Mapping
Use input constraints to narrow the viable DP approach:
| Constraint Range | Viable Approaches |
|---|---|
| N <= 20 | Bitmask DP, brute-force with memoization |
| N <= 500 | O(N^3) DP (interval DP, Floyd-Warshall) |
| N <= 5,000 | O(N^2) DP (LIS quadratic, 2D tables) |
| N <= 100,000 | O(N log N) DP (LIS with binary search, segment tree optimization) |
| N <= 1,000,000 | O(N) DP (Fibonacci-style, Kadane, sliding window) |
| N * W <= 10^7 | Knapsack variants (0/1 or unbounded) |
| Grid R * C <= 10^6 | Standard grid DP with rolling array |
Fibonacci / Climbing Stairs
Recognition Signals
- "How many ways to reach step N"
- "Count distinct ways to combine steps of size 1, 2, ..."
- "Decode ways" (how many ways to decode a digit string into letters)
- Recurrence follows f(n) = f(n-1) + f(n-2) or a generalized k-step variant
Core Idea The answer at position N depends only on a fixed number of prior positions. Build the result iteratively from the base cases, keeping only the last k values in memory. This generalizes beyond two-step Fibonacci to any linear recurrence. When the recurrence has a fixed number of terms, space reduces to O(k) where k is the number of terms. For very large N (e.g., N > 10^18), matrix exponentiation can compute the result in O(k^3 log N).
Python Template
def climb_stairs(n: int, steps: list[int] | None = None) -> int:
"""Count ways to reach step n using allowed step sizes."""
if steps is None:
steps = [1, 2]
max_step = max(steps)
# dp[i] = number of ways to reach step i
dp: list[int] = [0] * (max_step + 1)
dp[0] = 1 # base case: one way to stay at ground
for i in range(1, n + 1):
total = 0
for s in steps:
if i - s >= 0:
total += dp[(i - s) % (max_step + 1)]
dp[i % (max_step + 1)] = total
return dp[n % (max_step + 1)]
Key Edge Cases
- n = 0: exactly 1 way (do nothing)
- n = 1 with only step size 2: 0 ways (unreachable)
- Large n with modular arithmetic required (typically mod 10^9 + 7)
- Negative step sizes are not valid; guard input
Common Mistakes
- Forgetting the base case dp[0] = 1 and getting all zeros
- Off-by-one in the loop range (should go up to n inclusive)
- Not applying modular arithmetic early, causing integer overflow in languages with fixed-width integers
0/1 Knapsack
Recognition Signals
- "Maximize total value without exceeding capacity W"
- "Can you partition the array into two subsets with equal sum"
- "Select a subset such that the sum equals target"
- Each item can be used at most once
Core Idea For each item, decide to include or exclude it. Build a 1D DP array where dp[w] indicates the best achievable value (or a boolean for subset sum) using capacity w. Iterate items in the outer loop and capacity in reverse to ensure each item is used at most once. Common variants include subset sum (boolean dp), partition equal subset sum (check if total/2 is achievable), and target sum with +/- signs (offset the DP index by a constant).
Python Template
def knapsack_01(weights: list[int], values: list[int], capacity: int) -> int:
"""Return maximum value achievable within capacity."""
n = len(weights)
dp: list[int] = [0] * (capacity + 1)
for i in range(n):
# Traverse capacity in reverse to avoid reusing item i
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
Key Edge Cases
- All items heavier than capacity: answer is 0
- Capacity is 0: answer is 0 regardless of items
- Single item that exactly matches capacity
- Subset sum variant: dp is boolean, dp[0] = True
Common Mistakes
- Iterating capacity forward instead of reverse, which allows items to be picked multiple times (that is unbounded knapsack)
- Confusing 0/1 knapsack with unbounded knapsack when items are reusable
- Not handling the case where weights[i] > capacity (skip the inner loop for that item)
Longest Common Subsequence (LCS)
Recognition Signals
- "Find the longest common subsequence of two strings"
- "Minimum number of insertions and deletions to transform A into B"
- "Edit distance between two strings"
- Two sequences compared element by element
Core Idea Build a 2D table where dp[i][j] represents the LCS length of the first i characters of A and first j characters of B. If characters match, extend the diagonal; otherwise take the max of skipping from either side. Edit distance uses the same table structure with insertion, deletion, and substitution costs, where each operation adds 1 (or a weighted cost) and the goal switches from maximizing to minimizing. The "minimum deletions to make two strings equal" variant is directly: len(A) + len(B) - 2 * LCS(A, B).
Python Template
def lcs(a: str, b: str) -> int:
"""Return length of the longest common subsequence."""
m, n = len(a), len(b)
# Use two rows to reduce space from O(m*n) to O(min(m,n))
if m < n:
a, b, m, n = b, a, n, m
prev: list[int] = [0] * (n + 1)
curr: list[int] = [0] * (n + 1)
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
curr[j] = prev[j - 1] + 1
else:
curr[j] = max(prev[j], curr[j - 1])
prev, curr = curr, [0] * (n + 1)
return prev[n]
Key Edge Cases
- One or both strings empty: LCS is 0
- Strings are identical: LCS equals the full length
- No common characters at all: LCS is 0
- Very long strings (space optimization with rolling rows is critical)
Common Mistakes
- Mixing up 0-indexed and 1-indexed access between the string and the DP table
- Forgetting to reset the curr row between iterations when using rolling arrays
- Reconstructing the actual subsequence requires storing the full table or backtracking pointers, which the space-optimized version does not support
Longest Increasing Subsequence (LIS)
Recognition Signals
- "Find the length of the longest strictly increasing subsequence"
- "Minimum number of envelopes that nest inside each other"
- "Longest chain of pairs"
- Ordering constraint on a single sequence
Core Idea The O(N^2) approach builds dp[i] as the LIS ending at index i by checking all j < i where nums[j] < nums[i]. The O(N log N) approach (patience sorting) maintains a tails array where tails[k] is the smallest tail element of any increasing subsequence of length k+1. For each element, binary search for its position in tails to either extend or replace. To reconstruct the actual subsequence, maintain a parent pointer array alongside the tails.
Python Template
import bisect
def lis_length(nums: list[int]) -> int:
"""Return length of longest strictly increasing subsequence. O(N log N)."""
tails: list[int] = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num) # extend the longest subsequence
else:
tails[pos] = num # replace to keep smallest tail
return len(tails)
Key Edge Cases
- Empty array: LIS is 0
- All elements equal: LIS is 1 (strictly increasing requires distinct values)
- Already sorted in increasing order: LIS equals array length
- Non-strictly increasing (allow equal): use bisect_right instead of bisect_left
Common Mistakes
- Using bisect_right for strictly increasing (gives non-decreasing subsequence instead)
- Assuming the tails array is the actual LIS (it is not; it only gives the correct length)
- Forgetting to handle the 2D variant (e.g., Russian doll envelopes) by sorting one dimension ascending and the second dimension descending before applying LIS on the second dimension
- Confusing "longest non-decreasing subsequence" with "longest strictly increasing subsequence" when duplicate values exist
Grid DP
Recognition Signals
- "How many unique paths from top-left to bottom-right"
- "Minimum cost path in a grid moving only right or down"
- "Fill a matrix where each cell depends on its top and left neighbors"
- "Maximum cherries/gold you can collect traversing a grid" (multi-path grid DP)
Core Idea Process cells row by row (or column by column). Each cell's value depends on its top neighbor and left neighbor. Use a single row array to reduce space: the current value at dp[c] is the "top" neighbor, and dp[c-1] is the "left" neighbor already updated in this row. For "unique paths" counting, the value is the sum of top and left; for "minimum path sum", take the min of top and left plus the current cell cost. Obstacles are handled by zeroing out blocked cells.
Python Template
def min_path_sum(grid: list[list[int]]) -> int:
"""Return minimum path sum from top-left to bottom-right."""
rows, cols = len(grid), len(grid[0])
dp: list[int] = [0] * cols
dp[0] = grid[0][0]
# First row: can only come from the left
for c in range(1, cols):
dp[c] = dp[c - 1] + grid[0][c]
# Remaining rows
for r in range(1, rows):
dp[0] += grid[r][0] # first column: can only come from above
for c in range(1, cols):
dp[c] = min(dp[c], dp[c - 1]) + grid[r][c]
return dp[cols - 1]
Key Edge Cases
- Single row or single column grid: path is forced, just sum all cells
- 1x1 grid: answer is the single cell value
- Grid with negative values: min-path logic still works, but "unique paths" counting is unaffected by values
- Obstacles (cells marked as blocked): set dp to infinity (min-path) or 0 (counting)
Common Mistakes
- Forgetting to initialize the first row and first column separately before the main loop
- Allowing diagonal movement when the problem only permits right and down
- Not handling the obstacle case (setting blocked cells to 0 or infinity depending on the variant)
- Modifying the input grid in place to save space without realizing the problem may need the original values later
Kadane's Algorithm
Recognition Signals
- "Maximum sum of a contiguous subarray"
- "Best time to buy and sell stock" (single transaction variant)
- "Largest sum contiguous segment"
- "Maximum product subarray" (variant with sign tracking)
- "Circular subarray with maximum sum" (run Kadane twice: once normal, once inverted)
Core Idea At each position, decide whether to extend the current subarray or start fresh. Track the running sum and reset it to the current element whenever extending would produce a smaller result. Maintain a global maximum across all positions. The "buy and sell stock" variant is Kadane's in disguise: compute the diff array of consecutive prices, then find the maximum subarray sum of the diffs.
Python Template
def max_subarray_sum(nums: list[int]) -> int:
"""Return maximum sum of any contiguous subarray. Handles all-negative arrays."""
if not nums:
return 0
current_sum = nums[0]
best_sum = nums[0]
for i in range(1, len(nums)):
# Extend current subarray or start new one at nums[i]
current_sum = max(nums[i], current_sum + nums[i])
best_sum = max(best_sum, current_sum)
return best_sum
Key Edge Cases
- All negative numbers: answer is the largest (least negative) single element
- Single element: answer is that element
- Array of all zeros: answer is 0
- Very large arrays where overflow matters (apply constraints)
Common Mistakes
- Initializing current_sum and best_sum to 0 instead of nums[0], which fails for all-negative arrays
- Returning 0 for all-negative arrays by incorrectly assuming subarray must have positive sum
- Not adapting for the "maximum product" variant, which requires tracking both the max and min running product due to sign flips
- For circular subarray max sum: forgetting to handle the case where all elements are negative (the inverted Kadane approach gives total_sum - min_subarray_sum, but if all are negative this wraps to 0, which is invalid since the subarray must be non-empty)
Coin Change / Unbounded Knapsack
Recognition Signals
- "Fewest coins to make amount"
- "Number of ways to make change using denominations"
- "Each coin/item can be used unlimited times"
- "Minimum number of items to reach target sum"
Core Idea Unlike 0/1 knapsack, items can be reused. Iterate capacity in the forward direction so each denomination contributes multiple times. For minimum coins, initialize dp with infinity and take the min. For counting combinations, accumulate sums. The critical distinction between counting combinations vs permutations lies in loop order: coins in the outer loop counts each set of coins once (combinations), while amount in the outer loop counts every ordering (permutations).
Python Template
def coin_change_min(coins: list[int], amount: int) -> int:
"""Return fewest coins to make amount, or -1 if impossible."""
dp: list[float] = [float("inf")] * (amount + 1)
dp[0] = 0 # base case: 0 coins for amount 0
for coin in coins:
# Forward iteration allows reusing the same coin
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)
return dp[amount] if dp[amount] != float("inf") else -1
def coin_change_ways(coins: list[int], amount: int) -> int:
"""Return number of distinct combinations to make amount."""
dp: list[int] = [0] * (amount + 1)
dp[0] = 1 # one way to make amount 0
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]
return dp[amount]
Key Edge Cases
- Amount is 0: min coins is 0, number of ways is 1
- No coins provided: impossible for any positive amount
- Single coin that does not divide the amount: impossible
- Counting permutations vs combinations: iterating coins in outer loop gives combinations; iterating amount in outer loop gives permutations
Common Mistakes
- Confusing combinations and permutations by swapping the loop order (coins-outer counts combinations, amount-outer counts permutations)
- Forgetting to return -1 when dp[amount] remains infinity
- Using reverse iteration (which gives 0/1 knapsack behavior instead of unbounded)
Bitmask DP
Recognition Signals
- "Visit all N cities exactly once" (TSP)
- "Assign N tasks to N workers optimally"
- "Enumerate all subsets of a set"
- Constraint: N <= 20 (since 2^20 = ~10^6 is feasible)
Core Idea Represent the set of visited/used elements as a bitmask integer. dp[mask] (or dp[mask][i]) stores the optimal value when the set of chosen elements is described by mask. Iterate over all 2^N masks and try adding each element not yet in the mask to transition to the next state. For subset enumeration without a "current position" dimension, use dp[mask] alone. When order matters (TSP), add a second dimension dp[mask][last] to track which element was visited last.
Python Template
def tsp(dist: list[list[int]]) -> int:
"""Return minimum cost to visit all cities and return to start (TSP)."""
n = len(dist)
full_mask = (1 << n) - 1
INF = float("inf")
# dp[mask][i] = min cost to reach city i having visited cities in mask
dp: list[list[float]] = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # start at city 0
for mask in range(1, 1 << n):
for u in range(n):
if dp[mask][u] == INF:
continue
if not (mask >> u & 1):
continue # u not in current mask
for v in range(n):
if mask >> v & 1:
continue # v already visited
new_mask = mask | (1 << v)
cost = dp[mask][u] + dist[u][v]
if cost < dp[new_mask][v]:
dp[new_mask][v] = cost
# Return to start city
return int(min(dp[full_mask][i] + dist[i][0] for i in range(n)))
Key Edge Cases
- N = 1: only one city, cost is 0
- N = 0: no cities, trivially 0
- Asymmetric distances: dist[i][j] != dist[j][i] (common in directed TSP)
- Assignment problem variant: no return-to-start, just minimize total assignment cost
Common Mistakes
- Forgetting to check that the current city u is actually in the mask before expanding from it
- Not initializing the start state correctly (dp[1 << start][start] = 0)
- Using N > 20, which makes 2^N states exceed memory and time limits
Top-Down vs Bottom-Up
Both approaches produce the same results but have different trade-offs:
| Aspect | Top-Down (Memoization) | Bottom-Up (Tabulation) |
|---|---|---|
| Implementation | Recursive with cache (functools.cache or dict) | Iterative with array |
| States computed | Only reachable states | All states in the table |
| Stack depth | Risk of RecursionError for large N (Python default limit: 1000) | No recursion; safe for any N |
| Space optimization | Harder to apply rolling arrays | Natural fit for rolling arrays |
| Debugging | Easier to trace individual subproblems | Easier to inspect the full table |
When to prefer top-down: The state space is sparse (many states are unreachable), or the recurrence is complex and hard to order iteratively.
When to prefer bottom-up: Space optimization is needed, the state space is dense, or recursion depth would exceed limits.
Combining Patterns
Many problems require combining two or more patterns:
- LIS on 2D points (Russian doll envelopes): Sort by one dimension, apply LIS on the other
- Grid DP + Bitmask: Collect items in a grid where you must visit specific cells (small item count)
- Knapsack + Fibonacci: Count ways to fill a knapsack where item order matters (permutation variant)
- LCS + Edit Distance: Compute similarity scores between sequences using weighted operations
- Kadane + Grid: Maximum sum rectangle in a 2D matrix by fixing two rows and applying Kadane on column prefix sums
- Coin Change + Counting: Number of ways to make change with a maximum number of coins (bounded knapsack hybrid)
When a problem does not fit cleanly into one pattern, identify the state variables first, then check which pattern's recurrence most closely matches the transitions between states.
Python-Specific Tips
Memoization with functools.cache
For top-down DP in Python 3.9+, use @functools.cache (or @functools.lru_cache(maxsize=None) for 3.8):
import functools
@functools.cache
def fib(n: int) -> int:
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
Recursion limit: Python's default recursion limit is 1000. For deep DP recursion, set sys.setrecursionlimit(N + 100) or convert to bottom-up.
Integer size: Python integers have arbitrary precision, so overflow is not a concern. However, modular arithmetic (% MOD) should still be applied at each step to keep numbers small and avoid slow big-integer operations.
Array initialization: Use [0] * n for 1D and [[0] * cols for _ in range(rows)] for 2D. Never use [[0] * cols] * rows as all rows will share the same reference.
Graph Algorithm Patterns
Graph problems appear frequently in competitive programming and technical interviews. The key challenge is recognizing which technique fits the problem structure. This reference covers eight core patterns with recognition heuristics, templates, and pitfall guides.
Pattern Recognition Table
| Trigger Signals | Technique | Typical Complexity |
|---|---|---|
| Shortest path, unweighted, fewest steps | BFS | O(V + E) |
| Explore all paths, connected components, backtracking | DFS | O(V + E) |
| Shortest path, weighted (non-negative) | Dijkstra | O((V + E) log V) |
| Dependencies, ordering, DAG | Topological Sort | O(V + E) |
| Dynamic connectivity, "are X and Y connected?" | Union-Find (DSU) | O(alpha(N)) per op |
| Minimum cost to connect all nodes | MST (Kruskal/Prim) | O(E log E) |
| Weighted shortest path with negative edges | Bellman-Ford | O(V * E) |
| Two groups, coloring, odd cycle | Bipartite Check | O(V + E) |
Constraint-to-Technique Mapping
Use V (vertices) and E (edges) bounds to narrow viable algorithms:
| Constraint Range | Viable Techniques | Notes |
|---|---|---|
| V <= 20 | Bitmask DP, brute-force BFS/DFS | Exponential OK |
| V <= 1,000, E <= 10,000 | All techniques, Floyd-Warshall for APSP | O(V^3) still feasible |
| V <= 100,000, E <= 200,000 | BFS, DFS, Dijkstra, Topo Sort, DSU, MST | Standard competitive range |
| V <= 1,000,000 | BFS, DFS, DSU, Kahn's | Avoid O(V log V) heaps if possible |
| Negative weights present | Bellman-Ford, SPFA | Dijkstra invalid |
| Dense graph (E ~ V^2) | Prim (adj matrix), Floyd-Warshall | Adjacency list Dijkstra still works |
| Edges arrive online | Union-Find | Incremental connectivity |
Individual Patterns
BFS (Breadth-First Search)
Recognition Signals
- "Shortest path" or "minimum steps" in an unweighted graph or grid
- "Level-order traversal" or "distance from source"
- Multiple starting points (multi-source BFS)
- "Nearest" something in a grid
Core Idea
BFS explores nodes layer by layer from the source, guaranteeing that the first time a node is reached, it is via the shortest path (in terms of edge count). Use a queue (FIFO) to process nodes in discovery order. Multi-source BFS initializes the queue with all sources at distance 0, treating them as a virtual super-source.
Python Template
from collections import deque
def bfs_shortest_path(graph: dict[int, list[int]], start: int) -> dict[int, int]:
"""Return shortest distance from start to all reachable nodes."""
dist: dict[int, int] = {start: 0}
queue: deque[int] = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in dist:
dist[neighbor] = dist[node] + 1
queue.append(neighbor)
return dist
For multi-source BFS, initialize dist and queue with all sources at distance 0 instead of a single start node.
Key Edge Cases
- Disconnected graph: unreachable nodes never appear in
dist - Self-loops: handled naturally (node already visited)
- Start node with no edges: returns
{start: 0} - Grid BFS: encode
(row, col)as queue elements, check bounds before enqueue
Common Mistakes
- Using a list as a queue (
.pop(0)is O(N); usedeque) - Marking visited after popping instead of before enqueuing (causes duplicates)
- Forgetting to handle the case where start == target
DFS (Depth-First Search)
Recognition Signals
- "Find all connected components" or "is there a path?"
- "Cycle detection" in directed or undirected graphs
- "Enumerate all paths" or backtracking required
- Tree traversal (pre-order, post-order, in-order)
Core Idea
DFS explores as deep as possible along each branch before backtracking. It naturally discovers connected components, detects cycles, and computes entry/exit times useful for subtree queries. Use iterative DFS with an explicit stack for large graphs to avoid Python's recursion limit.
Python Template (Iterative)
def dfs_iterative(graph: dict[int, list[int]], start: int) -> list[int]:
"""Return all nodes reachable from start in DFS order."""
visited: set[int] = set()
stack: list[int] = [start]
order: list[int] = []
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
return order
Cycle Detection (Directed Graph)
def has_cycle_directed(graph: dict[int, list[int]], n: int) -> bool:
"""Detect cycle in a directed graph with n nodes (0-indexed)."""
WHITE, GRAY, BLACK = 0, 1, 2
color: list[int] = [WHITE] * n
for start in range(n):
if color[start] != WHITE:
continue
stack: list[tuple[int, int]] = [(start, 0)]
color[start] = GRAY
while stack:
node, idx = stack.pop()
if idx < len(graph.get(node, [])):
stack.append((node, idx + 1))
neighbor = graph[node][idx]
if color[neighbor] == GRAY:
return True
if color[neighbor] == WHITE:
color[neighbor] = GRAY
stack.append((neighbor, 0))
else:
color[node] = BLACK
return False
Key Edge Cases
- Self-loops count as cycles in directed graphs
- Undirected cycle detection must skip the parent edge (not just visited check)
- Single-node graph with no edges has no cycle
- Disconnected graph: must start DFS from every unvisited node
Common Mistakes
- Hitting Python recursion limit on deep graphs (use
sys.setrecursionlimitor iterative) - Confusing undirected vs directed cycle detection logic
- Forgetting to handle disconnected components (only running DFS from node 0)
Dijkstra's Algorithm
Recognition Signals
- "Shortest path" with weighted edges (non-negative weights)
- "Minimum cost to reach target"
- Grid with varying movement costs
- "Cheapest" route or "minimum total weight"
Core Idea
Dijkstra greedily expands the closest unvisited node using a min-heap. Each node is finalized when popped from the heap, and relaxation updates neighbor distances. It fails with negative edge weights because a finalized node's distance may later be improvable. The 0-1 BFS variant handles graphs where edges have weight 0 or 1 using a deque instead of a heap.
Python Template
import heapq
def dijkstra(graph: dict[int, list[tuple[int, int]]], start: int) -> dict[int, int]:
"""Return shortest distance from start. graph[u] = [(v, weight), ...]."""
dist: dict[int, int] = {start: 0}
heap: list[tuple[int, int]] = [(0, start)]
while heap:
d, node = heapq.heappop(heap)
if d > dist.get(node, float("inf")):
continue
for neighbor, weight in graph[node]:
new_dist = d + weight
if new_dist < dist.get(neighbor, float("inf")):
dist[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return dist
For 0-1 BFS (weights are only 0 or 1), use a deque: appendleft for weight-0 edges, append for weight-1 edges. This avoids the heap overhead and runs in O(V + E).
Key Edge Cases
- Unreachable nodes: never appear in
dist - Multiple edges between same pair: all are considered during relaxation
- Zero-weight edges: Dijkstra handles them, but 0-1 BFS is faster when applicable
- Very large weights: use
float("inf")sentinel, not a magic number
Common Mistakes
- Not skipping stale heap entries (the
if d > distguard is essential) - Using Dijkstra with negative weights (silently gives wrong answers)
- Storing
visitedset and skipping revisits without the distance check
Topological Sort
Recognition Signals
- "Order of dependencies" or "prerequisite chain"
- "Is the directed graph a DAG?"
- "Process tasks in valid order"
- Build systems, course scheduling, compilation order
Core Idea
Topological sort produces a linear ordering of vertices such that for every directed edge (u, v), u appears before v. It only exists for DAGs. Kahn's algorithm (BFS-based) processes zero-indegree nodes iteratively and naturally detects cycles when the output is shorter than V. DFS-based topo sort appends nodes in reverse finish order.
Kahn's Algorithm (BFS)
from collections import deque
def topological_sort_kahn(graph: dict[int, list[int]], n: int) -> list[int] | None:
"""Return topo order for n nodes (0-indexed), or None if cycle exists."""
indegree: list[int] = [0] * n
for u in graph:
for v in graph[u]:
indegree[v] += 1
queue: deque[int] = deque(v for v in range(n) if indegree[v] == 0)
order: list[int] = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph.get(node, []):
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == n else None
For DFS-based topo sort, use WHITE/GRAY/BLACK coloring. Append nodes to the order when they turn BLACK (all descendants processed), then reverse. A GRAY-to-GRAY back edge indicates a cycle.
Key Edge Cases
- Multiple valid orderings: Kahn's with a min-heap gives lexicographically smallest
- Isolated nodes (no edges): appear anywhere in the ordering
- Self-loops: always indicate a cycle
- Empty graph: returns empty list (valid)
Common Mistakes
- Forgetting to initialize indegree for nodes with no incoming edges
- Using Kahn's but not checking
len(order) == nfor cycle detection - DFS-based: forgetting to reverse the order at the end
Union-Find (Disjoint Set Union)
Recognition Signals
- "Are nodes X and Y connected?" with dynamic edge additions
- "Number of connected components" after a series of merges
- "Detect cycle in an undirected graph"
- "Group" or "cluster" elements incrementally
Core Idea
Union-Find maintains a forest of disjoint sets. Each element has a parent, and the root of the tree is the set representative. Path compression flattens the tree during find, and union by rank keeps the tree balanced. Together they achieve nearly O(1) amortized per operation. To detect a cycle in an undirected graph, check if both endpoints of an edge share the same root before merging.
Python Template
class UnionFind:
def __init__(self, n: int) -> None:
self.parent: list[int] = list(range(n))
self.rank: list[int] = [0] * n
self.components: int = n
def find(self, x: int) -> int:
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path compression
x = self.parent[x]
return x
def union(self, x: int, y: int) -> bool:
"""Merge sets of x and y. Return False if already in same set."""
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
self.components -= 1
return True
Key Edge Cases
- Single-element sets:
find(x) == xandunion(x, x)returns False - Weighted union-find: store additional data (e.g., edge weights) in the parent relation
- Rollback (offline): use union by rank without path compression for undo support
- Very large N (10^6+): iterative path compression avoids stack overflow
Common Mistakes
- Implementing path compression recursively in Python (stack overflow for large N)
- Forgetting
union by rank(degrades to O(N) per find without it) - Using union-find for directed graph connectivity (it only works for undirected)
MST (Kruskal's and Prim's)
Recognition Signals
- "Minimum cost to connect all nodes"
- "Minimum spanning tree" or "cheapest network"
- "Remove maximum weight edges while keeping connectivity"
- Edge-centric optimization on undirected weighted graphs
Core Idea
A minimum spanning tree connects all vertices with the minimum total edge weight. Kruskal's sorts all edges by weight and greedily adds them using union-find to avoid cycles. Prim's grows the MST from a starting vertex, always adding the cheapest edge to an unvisited neighbor. Kruskal's is simpler for sparse graphs; Prim's with a heap suits dense graphs.
Kruskal's Algorithm
def kruskal(n: int, edges: list[tuple[int, int, int]]) -> list[tuple[int, int, int]]:
"""Return MST edges. edges = [(weight, u, v), ...]. Returns [] if disconnected."""
edges.sort()
uf = UnionFind(n) # uses UnionFind class from above
mst: list[tuple[int, int, int]] = []
for weight, u, v in edges:
if uf.union(u, v):
mst.append((weight, u, v))
if len(mst) == n - 1:
break
return mst if len(mst) == n - 1 else []
Prim's Algorithm
import heapq
def prim(graph: dict[int, list[tuple[int, int]]], n: int) -> int:
"""Return total MST weight. graph[u] = [(v, weight), ...]. -1 if disconnected."""
visited: set[int] = {0}
heap: list[tuple[int, int]] = [(w, v) for v, w in graph.get(0, [])]
heapq.heapify(heap)
total = 0
while heap and len(visited) < n:
weight, node = heapq.heappop(heap)
if node in visited:
continue
visited.add(node)
total += weight
for neighbor, w in graph.get(node, []):
if neighbor not in visited:
heapq.heappush(heap, (w, neighbor))
return total if len(visited) == n else -1
Key Edge Cases
- Disconnected graph: MST does not exist (check edge count or visited count)
- Multiple edges with equal weight: any valid MST is acceptable
- Single node: MST weight is 0, no edges needed
- Parallel edges: Kruskal handles naturally; Prim considers all during relaxation
Common Mistakes
- Kruskal: not sorting edges before processing
- Prim: not checking
if node in visitedafter heap pop (processes stale entries) - Assuming MST is unique (it is only unique when all edge weights are distinct)
Bellman-Ford
Recognition Signals
- "Shortest path" with possible negative edge weights
- "Detect negative cycle"
- "At most K edges" shortest path constraint
- SPFA mentioned or arbitrage detection
Core Idea
Bellman-Ford relaxes all edges V-1 times, which is sufficient to propagate shortest distances through any simple path. If a V-th relaxation still improves a distance, a negative cycle exists. Unlike Dijkstra, it handles negative weights correctly. SPFA is a queue-based optimization that only relaxes edges from recently-updated nodes, offering better average-case performance but the same worst case.
Python Template
def bellman_ford(n: int, edges: list[tuple[int, int, int]], start: int) -> list[float] | None:
"""Return distances from start, or None if negative cycle exists.
edges = [(u, v, weight), ...]."""
dist: list[float] = [float("inf")] * n
dist[start] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Check for negative cycles
for u, v, w in edges:
if dist[u] + w < dist[v]:
return None
return dist
For K-edges variant (shortest path using at most K edges), run only K iterations instead of V-1, and copy dist before each round to prevent using current-round updates: prev = dist[:], then relax using prev[u].
Key Edge Cases
- Negative cycle reachable from start: return None (no valid shortest path)
- Negative cycle not reachable from start: distances to reachable nodes are still valid
- Zero-weight cycles: not negative, do not affect correctness
- K-edges variant: must copy
distbefore each round to avoid using current-round updates
Common Mistakes
- K-edges: relaxing with current-round distances instead of previous-round copy
- Not distinguishing between "negative cycle exists" and "negative cycle reachable from start"
- Running only N-2 iterations instead of N-1
Bipartite Check
Recognition Signals
- "Divide into two groups with no intra-group edges"
- "2-colorable" or "two-coloring"
- "Odd-length cycle" detection
- Matching problems on bipartite graphs
Core Idea
A graph is bipartite if and only if it contains no odd-length cycle. This is equivalent to being 2-colorable: assign alternating colors via BFS or DFS, and if any edge connects two same-colored nodes, the graph is not bipartite. For disconnected graphs, check each component independently.
Python Template (BFS)
from collections import deque
def is_bipartite(graph: dict[int, list[int]], n: int) -> bool:
"""Check if graph with n nodes (0-indexed) is bipartite."""
color: list[int] = [-1] * n
for start in range(n):
if color[start] != -1:
continue
color[start] = 0
queue: deque[int] = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph.get(node, []):
if color[neighbor] == -1:
color[neighbor] = 1 - color[node]
queue.append(neighbor)
elif color[neighbor] == color[node]:
return False
return True
To extract the two partitions, collect nodes by their color value after a successful check: group_a = [v for v in range(n) if color[v] == 0].
Key Edge Cases
- Disconnected graph: each component must be independently bipartite
- Self-loops: immediately make the graph non-bipartite
- Single node with no edges: trivially bipartite
- Tree: always bipartite (no cycles, so no odd cycles)
Common Mistakes
- Only checking one connected component instead of all
- Forgetting that self-loops violate bipartiteness
- Using DFS coloring but not checking the back-edge color correctly
Math and Combinatorics Patterns
Mathematical and combinatorial problems appear frequently in competitive programming and algorithm design. They often hide behind constraints that look like brute-force problems but require algebraic shortcuts to meet time limits. This reference covers eight core pattern families with recognition signals, templates, and pitfalls.
Pattern Recognition Table
| Trigger Signals | Technique | Typical Complexity |
|---|---|---|
| "answer modulo 10^9+7", large product/sum | Modular Arithmetic | O(1) per operation |
| "count primes up to N", "smallest factor" | Sieve of Eratosthenes | O(N log log N) |
| "greatest common divisor", "least common multiple" | GCD / LCM | O(log min(a,b)) |
| "how many ways to choose", "combinations mod p" | Binomial Coefficients | O(N) precompute, O(1) query |
| "compute a^b mod m", "matrix recurrence" | Fast Exponentiation | O(log b) |
| "count arrangements", "distribute items into groups" | Counting Techniques | Varies |
| "count elements satisfying at least one", "derangements" | Inclusion-Exclusion | O(2^k) for k constraints |
| "two players, optimal play", "who wins" | Game Theory (Sprague-Grundy) | Varies by state space |
Constraint-to-Technique Mapping
- N up to 10^7 and asks about primes: Sieve of Eratosthenes.
- N up to 10^6 and asks "how many ways": Precomputed factorials + modular inverse for nCr.
- "modulo 10^9+7" anywhere in the problem: Modular arithmetic throughout; use modular inverse for division.
- Two players, finite game, no randomness: Sprague-Grundy theorem or direct DP on game states.
- "count subsets satisfying property" with small constraint count (k <= 20): Inclusion-exclusion over 2^k subsets.
- Linear recurrence with large N (10^18): Matrix exponentiation to compute nth term in O(k^3 log N).
- "distribute N items into K groups": Stars and bars, possibly combined with inclusion-exclusion for bounded constraints.
Individual Patterns
Modular Arithmetic
Recognition Signals
- Problem says "answer modulo 10^9+7" or any large prime
- Intermediate values overflow 64-bit integers
- Division is required under a modular context
- Counting problem with astronomically large answers
Core Idea
All arithmetic operations (add, subtract, multiply) distribute over modulo. Division under a prime modulus uses modular inverse: a / b mod p = a * b^(p-2) mod p via Fermat's little theorem. Always reduce intermediate results to prevent overflow.
Python Template
MOD = 10**9 + 7
def mod_add(a: int, b: int) -> int:
return (a + b) % MOD
def mod_mul(a: int, b: int) -> int:
return (a * b) % MOD
def mod_pow(base: int, exp: int, mod: int = MOD) -> int:
result = 1
base %= mod
while exp > 0:
if exp & 1:
result = result * base % mod
exp >>= 1
base = base * base % mod
return result
def mod_inv(a: int, mod: int = MOD) -> int:
"""Modular inverse via Fermat's little theorem. Requires mod is prime."""
return mod_pow(a, mod - 2, mod)
def mod_div(a: int, b: int) -> int:
return mod_mul(a, mod_inv(b))
Key Edge Cases
- Subtraction can go negative: use
(a - b + MOD) % MOD - Zero divisor:
mod_inv(0)is undefined; guard against it - Non-prime modulus: Fermat's theorem does not apply; use extended GCD instead
- Chained multiplications: reduce after every multiply, not just at the end
Common Mistakes
- Forgetting to take mod after subtraction, producing negative values
- Using Fermat's inverse with a composite modulus
- Applying mod to intermediate index calculations where exact values are needed
Sieve of Eratosthenes
Recognition Signals
- "Find all primes up to N" with N up to 10^7
- "Smallest prime factor of every number"
- Need to factorize many numbers efficiently
- "Count of prime factors" across a range
Core Idea
The classic sieve marks composites by iterating through multiples of each prime. The smallest-prime-factor (SPF) variant stores the smallest divisor at each index, enabling O(log N) factorization of any number after an O(N log log N) precompute. For ranges beyond memory, use a segmented sieve.
Python Template
def sieve_primes(n: int) -> list[bool]:
"""Standard boolean sieve. is_prime[i] is True if i is prime."""
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return is_prime
def smallest_prime_factor(n: int) -> list[int]:
"""SPF sieve for fast factorization."""
spf = list(range(n + 1))
for i in range(2, int(n**0.5) + 1):
if spf[i] == i: # i is prime
for j in range(i * i, n + 1, i):
if spf[j] == j:
spf[j] = i
return spf
def factorize(x: int, spf: list[int]) -> list[int]:
"""Factorize x using precomputed SPF table."""
factors: list[int] = []
while x > 1:
factors.append(spf[x])
x //= spf[x]
return factors
Key Edge Cases
- N = 0 or 1: no primes exist; handle boundary
- Memory limit: standard sieve needs O(N) space; switch to segmented sieve above ~10^8
- SPF of 1: not defined; skip or handle separately
- Even numbers: can optimize by treating 2 specially and only sieving odds
Common Mistakes
- Starting inner loop at
2*iinstead ofi*i(correct but slower) - Off-by-one on sieve size (allocate
n+1slots) - Forgetting that
sieve[0]andsieve[1]are not prime
GCD / LCM
Recognition Signals
- Problem explicitly mentions GCD or LCM
- "Find the largest number that divides all elements"
- "Smallest number divisible by all elements"
- Equations involving linear combinations of two integers (Bezout's identity)
Core Idea
Euclidean algorithm computes GCD in O(log min(a,b)). LCM derives from GCD: lcm(a,b) = a * b // gcd(a,b). Extended Euclidean finds coefficients x, y such that a*x + b*y = gcd(a,b), which is essential for modular inverse when the modulus is not prime.
Python Template
from math import gcd
from functools import reduce
def lcm(a: int, b: int) -> int:
return a * b // gcd(a, b)
def lcm_array(arr: list[int]) -> int:
return reduce(lcm, arr)
def gcd_array(arr: list[int]) -> int:
return reduce(gcd, arr)
def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
"""Returns (g, x, y) such that a*x + b*y = g = gcd(a, b)."""
if b == 0:
return a, 1, 0
g, x1, y1 = extended_gcd(b, a % b)
return g, y1, x1 - (a // b) * y1
def mod_inv_ext(a: int, m: int) -> int:
"""Modular inverse via extended GCD. Works for any coprime a, m."""
g, x, _ = extended_gcd(a % m, m)
if g != 1:
raise ValueError(f"Inverse does not exist: gcd({a}, {m}) = {g}")
return x % m
Key Edge Cases
gcd(0, x) = xandgcd(0, 0) = 0by convention- LCM overflow: compute
a // gcd(a,b) * binstead ofa * b // gcd(a,b) - Negative inputs: take absolute values before computing
- Extended GCD with
b = 0: base case returns(a, 1, 0)
Common Mistakes
- LCM overflow from multiplying before dividing by GCD
- Assuming modular inverse exists when
gcd(a, m) != 1 - Recursion depth for very large inputs (Python's default limit); use iterative version if needed
Binomial Coefficients
Recognition Signals
- "How many ways to choose k items from n"
- "nCr mod p" with large n
- Pascal's triangle or binomial theorem mentioned
- Lattice path counting (grid movement problems)
Core Idea
For small n (up to ~10^6), precompute factorials and inverse factorials modulo a prime, then answer nCr queries in O(1). Pascal's triangle DP works for smaller n without modular arithmetic. Lucas' theorem handles nCr mod p when n is very large but p is small.
Python Template
MOD = 10**9 + 7
def precompute_factorials(n: int) -> tuple[list[int], list[int]]:
"""Precompute factorial and inverse factorial arrays mod MOD."""
fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i % MOD
inv_fact = [1] * (n + 1)
inv_fact[n] = pow(fact[n], MOD - 2, MOD)
for i in range(n - 1, -1, -1):
inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
return fact, inv_fact
def nCr(n: int, r: int, fact: list[int], inv_fact: list[int]) -> int:
if r < 0 or r > n:
return 0
return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD
def lucas(n: int, r: int, p: int) -> int:
"""nCr mod p for small prime p, using Lucas' theorem."""
if r == 0:
return 1
return lucas(n // p, r // p, p) * nCr_small(n % p, r % p, p) % p
def nCr_small(n: int, r: int, p: int) -> int:
"""Direct nCr mod p for n < p."""
if r < 0 or r > n:
return 0
num = den = 1
for i in range(r):
num = num * (n - i) % p
den = den * (i + 1) % p
return num * pow(den, p - 2, p) % p
Key Edge Cases
nCr(n, 0) = 1andnCr(n, n) = 1for all valid nr > nreturns 0- Negative r or n: return 0
- Lucas' theorem only works when p is prime
Common Mistakes
- Off-by-one in precompute size (need
n+1slots) - Using Lucas' theorem with composite modulus
- Forgetting the
r > nguard, causing index-out-of-bounds
Fast Exponentiation
Recognition Signals
- "Compute a^b mod m" with b up to 10^18
- Linear recurrence (Fibonacci-like) with very large n
- "Matrix power" or "transform applied k times"
- State transition repeated billions of times
Core Idea
Binary exponentiation computes a^b mod m in O(log b) by squaring the base and halving the exponent at each step. Matrix exponentiation extends this: represent a linear recurrence as a matrix multiplication, then raise the transition matrix to the nth power. This turns O(n) recurrence evaluation into O(k^3 log n) where k is the matrix dimension.
Python Template
def power(base: int, exp: int, mod: int) -> int:
"""Binary exponentiation: base^exp mod mod."""
result = 1
base %= mod
while exp > 0:
if exp & 1:
result = result * base % mod
exp >>= 1
base = base * base % mod
return result
Matrix = list[list[int]]
def mat_mul(a: Matrix, b: Matrix, mod: int) -> Matrix:
"""Multiply two square matrices mod mod."""
n = len(a)
result = [[0] * n for _ in range(n)]
for i in range(n):
for k in range(n):
if a[i][k] == 0:
continue
for j in range(n):
result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % mod
return result
def mat_pow(mat: Matrix, exp: int, mod: int) -> Matrix:
"""Raise a square matrix to exp-th power mod mod."""
n = len(mat)
result = [[int(i == j) for j in range(n)] for i in range(n)]
while exp > 0:
if exp & 1:
result = mat_mul(result, mat, mod)
exp >>= 1
mat = mat_mul(mat, mat, mod)
return result
Key Edge Cases
exp = 0: result is 1 (scalar) or identity matrixbase = 0withexp = 0: conventionally 1, but problem-dependent- Overflow in matrix multiplication: reduce mod at every addition
- Recurrence with more than 2 terms: increase matrix dimension accordingly
Common Mistakes
- Forgetting to handle
exp = 0as a special case - Not reducing base modulo m before starting (causes unnecessary large intermediate values)
- Using the wrong matrix dimension for the recurrence
Counting Techniques
Recognition Signals
- "How many ways to arrange/distribute/partition"
- "Count sequences satisfying constraints"
- "Stars and bars" or "multiset coefficient"
- Catalan-number patterns: balanced parentheses, binary trees, non-crossing partitions
Core Idea
Permutations count ordered arrangements; combinations count unordered selections. Stars and bars counts ways to distribute n identical items into k distinct bins: C(n+k-1, k-1). Catalan numbers count structures with recursive nesting (nth Catalan = C(2n, n) / (n+1)). Recognize which formula applies by identifying whether order matters and whether items are identical or distinct.
Python Template
MOD = 10**9 + 7
def permutations_mod(n: int, r: int, fact: list[int], inv_fact: list[int]) -> int:
"""P(n, r) = n! / (n-r)! mod MOD."""
if r < 0 or r > n:
return 0
return fact[n] * inv_fact[n - r] % MOD
def stars_and_bars(n: int, k: int, fact: list[int], inv_fact: list[int]) -> int:
"""Distribute n identical items into k distinct bins (each >= 0)."""
return nCr(n + k - 1, k - 1, fact, inv_fact)
def catalan(n: int, fact: list[int], inv_fact: list[int]) -> int:
"""Nth Catalan number mod MOD."""
return nCr(2 * n, n, fact, inv_fact) * pow(n + 1, MOD - 2, MOD) % MOD
def multiset_coeff(n: int, k: int, fact: list[int], inv_fact: list[int]) -> int:
"""Choose k items from n types with repetition allowed. Uses nCr from above."""
return nCr(n + k - 1, k, fact, inv_fact)
Key Edge Cases
- Stars and bars with lower bounds: shift variables (replace x_i with y_i = x_i - lower_i)
- Catalan(0) = 1 by convention
- Empty arrangements: 0 items chosen from n gives 1 way (the empty selection)
- Upper-bounded distributions: combine stars and bars with inclusion-exclusion
Common Mistakes
- Confusing "with repetition" vs "without repetition" in the problem statement
- Applying stars and bars when items are distinct (use multinomial instead)
- Forgetting the
n+1denominator in the Catalan formula
Inclusion-Exclusion
Recognition Signals
- "Count elements satisfying at least one of k properties"
- "Count permutations with no fixed points" (derangements)
- "Count integers in range divisible by at least one of given primes"
- Constraints that are easier to count by complementing
Core Idea
Inclusion-exclusion alternates between adding and subtracting intersection sizes: |A1 union A2 union ... Ak| = sum|Ai| - sum|Ai intersect Aj| + .... This is powerful when direct counting is hard but counting elements with specific properties (or their complements) is easy. Derangements are a classic application: D(n) = n! * sum_{i=0}^{n} (-1)^i / i!.
Python Template
MOD = 10**9 + 7
def inclusion_exclusion(sets_sizes: list[int], intersect_fn) -> int:
"""Generic IE over k sets. intersect_fn(mask) returns |intersection of sets in mask|."""
k = len(sets_sizes)
total = 0
for mask in range(1, 1 << k):
bits = bin(mask).count("1")
size = intersect_fn(mask)
if bits % 2 == 1:
total = (total + size) % MOD
else:
total = (total - size + MOD) % MOD
return total
def derangements(n: int) -> int:
"""Count permutations with no fixed points, mod MOD."""
if n == 0:
return 1
if n == 1:
return 0
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 0
for i in range(2, n + 1):
dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD
return dp[n]
def euler_totient(n: int) -> int:
"""Euler's totient: count integers in [1, n] coprime to n."""
result = n
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0:
n //= p
result -= result // p
p += 1
if n > 1:
result -= result // n
return result
Key Edge Cases
D(0) = 1(the empty permutation is a derangement)- Inclusion-exclusion with k > 20 is usually too slow (2^k subsets); look for algebraic shortcuts
- Totient of 1 is 1
- Overlapping constraints that are not independent require careful intersection counting
Common Mistakes
- Sign error: forgetting to alternate between addition and subtraction
- Double-counting when constraints are not mutually independent
- Not handling the complementary counting step (total minus IE result)
Game Theory (Sprague-Grundy)
Recognition Signals
- "Two players take turns, optimal play, who wins"
- Game with positions that can be decomposed into independent sub-games
- Nim-like games with pile manipulation
- "First player wins or second player wins"
Core Idea
The Sprague-Grundy theorem states that every impartial game position has a Grundy number (nimber). A position with Grundy number 0 is a losing position for the player to move. For composite games (independent sub-games), the overall Grundy number is the XOR of individual Grundy numbers. Standard Nim: XOR all pile sizes; if nonzero, first player wins.
Python Template
def compute_grundy(max_state: int, moves_fn) -> list[int]:
"""Compute Grundy numbers for states 0..max_state.
moves_fn(state) returns an iterable of reachable states.
"""
grundy = [0] * (max_state + 1)
for state in range(max_state + 1):
reachable: set[int] = set()
for next_state in moves_fn(state):
reachable.add(grundy[next_state])
mex = 0
while mex in reachable:
mex += 1
grundy[state] = mex
return grundy
def game_winner(values: list[int]) -> str:
"""Winner via XOR. Works for Nim piles or composite Grundy values."""
xor_sum = 0
for v in values:
xor_sum ^= v
return "First" if xor_sum != 0 else "Second"
Key Edge Cases
- Terminal position (no moves available): Grundy number is 0 (losing for player to move)
- Single pile Nim: first player wins unless pile is 0
- Game with cycles: Sprague-Grundy applies only to acyclic (impartial) games
- Misere Nim: different endgame rule inverts the strategy for the last move
Common Mistakes
- Applying Sprague-Grundy to partisan games (different move sets per player)
- Forgetting that XOR-based composition requires sub-games to be independent
- Computing mex incorrectly by not collecting all reachable Grundy values first
Search and Optimization Patterns
This reference covers eight foundational search and optimization techniques that appear across competitive programming, coding interviews, and production algorithms. Each pattern includes recognition signals, a core idea summary, a Python template with type hints, key edge cases, and common mistakes.
Pattern Recognition Table
| Trigger Signals | Technique | Typical Complexity |
|---|---|---|
| Sorted array, find target, O(log n) required | Binary Search | O(log n) |
| "Minimize the maximum", "find smallest feasible value" | Binary Search on Answer | O(n log S) where S = search space |
| Sorted array, find pair with target sum, in-place | Two Pointers | O(n) |
| Fixed/variable-length subarray, substring constraints | Sliding Window | O(n) |
| Local optimal leads to global optimal, exchange argument | Greedy | O(n log n) typical |
| Range sum queries, subarray sums, 2D region sums | Prefix Sums | O(n) build, O(1) query |
| Overlapping intervals, merge/insert, scheduling | Merge Intervals | O(n log n) |
| Next greater/smaller element, histogram areas | Monotonic Stack | O(n) |
Constraint-to-Technique Mapping
When the problem does not immediately suggest a technique, use constraints as a guide:
- n <= 10^5 and "find minimum/maximum feasible" — Binary search on answer with a greedy or simulation check function.
- Sorted input + pair/triplet finding — Two pointers before considering hash maps. Saves space and often required by the problem.
- Contiguous subarray/substring with a constraint — Sliding window. If the constraint is a sum threshold, variable-size window. If fixed length k, fixed-size window.
- Multiple range sum queries on static data — Prefix sums. For 2D grids, build a 2D prefix sum matrix.
- "Given a set of intervals" — Sort by start (or end), then merge or sweep. Check if the problem is really interval scheduling (sort by end, greedy).
- "For each element, find the next greater/smaller" — Monotonic stack. Direction of traversal (left-to-right or right-to-left) depends on whether you need "next" or "previous".
- Optimization under constraints with greedy proof — Try exchange argument: if swapping any two elements in the solution cannot improve it, greedy works.
Individual Patterns
Binary Search
Recognition Signals
- Input array is sorted (or can be sorted without changing the answer).
- Problem asks for the position of a target or the insertion point.
- O(log n) time is expected or required.
Core Idea
Maintain a search interval [lo, hi] and halve it each step by comparing the midpoint against the target. The invariant is that the answer always lies within the current interval. Choose between lo = mid + 1 and hi = mid (or hi = mid - 1) depending on whether you want the leftmost or rightmost match.
Python Template
from bisect import bisect_left, bisect_right
from typing import List
def binary_search(nums: List[int], target: int) -> int:
"""Return index of target, or -1 if not found."""
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
def left_bound(nums: List[int], target: int) -> int:
"""Return index of first element >= target."""
return bisect_left(nums, target)
def right_bound(nums: List[int], target: int) -> int:
"""Return index of first element > target."""
return bisect_right(nums, target)
Key Edge Cases
- Empty array — return -1 or 0 depending on variant.
- All elements identical — left_bound and right_bound diverge.
- Target smaller than all elements or larger than all elements.
- Integer overflow in
lo + hi— uselo + (hi - lo) // 2.
Common Mistakes
- Off-by-one: using
lo < hiwhen the loop should belo <= hi(or vice versa). - Forgetting to handle the case where
bisect_leftreturnslen(nums). - Mutating the input array when the problem requires preserving order.
Binary Search on Answer
Recognition Signals
- Problem asks to "minimize the maximum" or "maximize the minimum".
- The answer lies in a bounded numeric range and is monotonic (if X works, all values above/below also work).
- A feasibility check can be written in O(n) or O(n log n).
Core Idea
Instead of searching in the input array, binary search over the space of possible answers. Define a predicate feasible(x) -> bool that returns True if the answer x satisfies all constraints. The answer space is monotonic: once feasible becomes True, it stays True (or vice versa). Binary search finds the boundary.
Python Template
from typing import Callable, List
def binary_search_on_answer(
lo: int,
hi: int,
feasible: Callable[[int], bool],
) -> int:
"""Find the smallest value in [lo, hi] where feasible returns True."""
while lo < hi:
mid = lo + (hi - lo) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
def can_split(nums: List[int], max_sum: int, k: int) -> bool:
"""Check if nums can be split into <= k subarrays each with sum <= max_sum."""
count, current = 1, 0
for x in nums:
if x > max_sum:
return False
if current + x > max_sum:
count += 1
current = x
else:
current += x
return count <= k
Key Edge Cases
- Single-element input where lo == hi immediately.
- The feasibility check must handle individual elements exceeding the candidate answer.
- Floating-point variant: use a fixed number of iterations (e.g., 100) instead of
lo < hi. - Off-by-one in bounds:
loshould be the minimum possible answer,hithe maximum.
Common Mistakes
- Reversing the predicate direction (searching for max when predicate checks min feasibility).
- Setting initial bounds too tight and excluding the actual answer.
- Forgetting that maximizing the minimum requires flipping the search direction.
Two Pointers
Recognition Signals
- Sorted array with a pair-sum or triplet-sum target.
- "Find two elements that satisfy a condition" with O(1) extra space.
- Removing duplicates in-place, or partitioning an array.
- Merging two sorted sequences.
Core Idea Place one pointer at each end of a sorted array (opposite direction) or both at the start (same direction). Move pointers inward based on how the current state compares to the target. Each pointer moves at most n times, giving O(n) total. The technique exploits sorted order to prune the search space without nested loops.
Python Template
from typing import List, Tuple, Optional
def two_sum_sorted(nums: List[int], target: int) -> Optional[Tuple[int, int]]:
"""Find indices of two numbers in sorted array that sum to target."""
lo, hi = 0, len(nums) - 1
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
return (lo, hi)
elif s < target:
lo += 1
else:
hi -= 1
return None
def remove_duplicates(nums: List[int]) -> int:
"""Remove duplicates in-place from sorted array. Return new length."""
if not nums:
return 0
write = 1
for read in range(1, len(nums)):
if nums[read] != nums[read - 1]:
nums[write] = nums[read]
write += 1
return write
Key Edge Cases
- Array with fewer than 2 elements.
- Multiple valid pairs — decide if you need the first, all, or any.
- Duplicate values that cause pointer movement to skip valid answers.
- Negative numbers affecting sum direction.
Common Mistakes
- Using two pointers on an unsorted array without sorting first.
- Not skipping duplicates when the problem asks for unique pairs.
- Returning indices from the sorted array when the problem wants original indices.
Sliding Window
Recognition Signals
- "Maximum/minimum sum of subarray of size k" (fixed window).
- "Longest/shortest substring containing all characters of X" (variable window).
- Contiguous subarray or substring with a constraint on sum, count, or character frequency.
- O(n) expected and brute-force is O(n^2).
Core Idea
Maintain a window [left, right] over the array. Expand right to include more elements; shrink left when the window violates the constraint. Track the answer as the window slides. Fixed-size windows advance both pointers together. Variable-size windows expand until invalid, then contract until valid again.
Python Template
from collections import Counter
from typing import List
def max_sum_subarray(nums: List[int], k: int) -> int:
"""Maximum sum of any contiguous subarray of size k."""
n = len(nums)
if n < k:
return 0
window_sum = sum(nums[:k])
best = window_sum
for i in range(k, n):
window_sum += nums[i] - nums[i - k]
best = max(best, window_sum)
return best
def min_window_substring(s: str, t: str) -> str:
"""Shortest substring of s containing all characters of t."""
need = Counter(t)
missing = len(t)
left = 0
best_start, best_len = 0, len(s) + 1
for right, ch in enumerate(s):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
while missing == 0:
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return s[best_start : best_start + best_len] if best_len <= len(s) else ""
Key Edge Cases
- Window size k equals the array length.
- Empty string t or s shorter than t in substring problems.
- All elements identical — window may never need to shrink.
- Negative numbers in sum-based windows (sliding window may not apply; consider prefix sums instead).
Common Mistakes
- Applying variable-size sliding window when the constraint is not monotonic (e.g., subarray with negative numbers).
- Off-by-one in window boundaries when computing length.
- Forgetting to update the frequency map when shrinking the window.
Greedy
Recognition Signals
- Interval scheduling, activity selection, or job sequencing.
- "Maximum number of non-overlapping intervals".
- A locally optimal choice at each step provably leads to a global optimum.
- The problem has optimal substructure and the greedy choice property.
Core Idea Make the locally optimal choice at each decision point without reconsidering previous choices. The key is proving correctness, typically via the exchange argument: assume an optimal solution differs from the greedy solution, then show you can swap one element to match the greedy choice without worsening the result. Sort the input by the criterion that enables the greedy choice.
Python Template
from typing import List, Tuple
def activity_selection(intervals: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
"""Select maximum non-overlapping intervals. Each interval is (start, end)."""
intervals.sort(key=lambda x: x[1])
selected: List[Tuple[int, int]] = []
last_end = -1
for start, end in intervals:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
def min_platforms(arrivals: List[int], departures: List[int]) -> int:
"""Minimum platforms needed so no train waits (sweep line variant)."""
events: List[Tuple[int, int]] = []
for a in arrivals:
events.append((a, 1))
for d in departures:
events.append((d + 1, -1))
events.sort()
current = best = 0
for _, delta in events:
current += delta
best = max(best, current)
return best
Key Edge Cases
- Intervals that share an endpoint (closed vs. open interval semantics).
- All intervals overlap — answer is 1 for selection, n for platforms.
- Single interval input.
- Ties in the sorting criterion — secondary sort order matters.
Common Mistakes
- Sorting by start time when end time is needed (or vice versa).
- Assuming greedy works without proving the exchange argument.
- Not handling the edge case where
start == endfor zero-length intervals.
Prefix Sums
Recognition Signals
- Multiple queries for the sum of a subarray or submatrix.
- "Number of subarrays with sum equal to k" (prefix sum + hash map).
- Range update queries on an array (difference array variant).
- O(1) per query required after preprocessing.
Core Idea
Build a prefix sum array where prefix[i] = sum of elements [0..i-1]. Any range sum [l..r] becomes prefix[r+1] - prefix[l] in O(1). For 2D, build a prefix sum matrix using inclusion-exclusion. Difference arrays are the inverse: store deltas, then reconstruct with a prefix sum after all updates.
Python Template
from typing import List
def build_prefix(nums: List[int]) -> List[int]:
"""Build 1D prefix sum array. prefix[i] = sum(nums[0:i])."""
prefix = [0] * (len(nums) + 1)
for i, x in enumerate(nums):
prefix[i + 1] = prefix[i] + x
return prefix
def range_sum(prefix: List[int], l: int, r: int) -> int:
"""Sum of nums[l..r] inclusive using prefix array."""
return prefix[r + 1] - prefix[l]
def subarray_sum_count(nums: List[int], k: int) -> int:
"""Count subarrays with sum exactly k."""
from collections import defaultdict
count = 0
current = 0
seen: dict[int, int] = defaultdict(int)
seen[0] = 1
for x in nums:
current += x
count += seen[current - k]
seen[current] += 1
return count
Key Edge Cases
- Empty array — prefix sum is
[0]. - Negative numbers — prefix sums are not monotonic, so binary search on prefix does not work.
- Subarray starting at index 0 —
prefix[0]must be 0. - Integer overflow on large inputs — use appropriate types.
Common Mistakes
- Off-by-one in prefix indexing:
prefix[r+1] - prefix[l], notprefix[r] - prefix[l-1](unless 1-indexed). - Forgetting to initialize
seen[0] = 1in the hash map variant. - Applying prefix sum binary search when values can be negative.
Merge Intervals
Recognition Signals
- "Given a list of intervals, merge all overlapping intervals."
- Insert a new interval into a sorted non-overlapping list.
- "Minimum number of meeting rooms" (variant uses a sweep line or min-heap).
- Output is a reduced set of non-overlapping intervals.
Core Idea Sort intervals by start time. Iterate through and merge the current interval with the last merged interval if they overlap (current start <= last end). Otherwise, start a new group. For insertion, find the overlap region, merge, and concatenate the non-overlapping parts. The sweep-line variant converts intervals into +1/-1 events for counting concurrent overlaps.
Python Template
from typing import List, Tuple
def merge_intervals(intervals: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
"""Merge all overlapping intervals. Each interval is (start, end)."""
if not intervals:
return []
intervals.sort()
merged: List[Tuple[int, int]] = [intervals[0]]
for start, end in intervals[1:]:
last_start, last_end = merged[-1]
if start <= last_end:
merged[-1] = (last_start, max(last_end, end))
else:
merged.append((start, end))
return merged
def insert_interval(
intervals: List[Tuple[int, int]],
new: Tuple[int, int],
) -> List[Tuple[int, int]]:
"""Insert new interval into sorted non-overlapping list and merge."""
result: List[Tuple[int, int]] = []
i, n = 0, len(intervals)
while i < n and intervals[i][1] < new[0]:
result.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= new[1]:
new = (min(new[0], intervals[i][0]), max(new[1], intervals[i][1]))
i += 1
result.append(new)
result.extend(intervals[i:])
return result
Key Edge Cases
- Single interval — return as-is.
- All intervals overlap — result is one merged interval.
- Adjacent intervals
(1,3)and(3,5)— overlapping if using<=, not if using<. - Already sorted and non-overlapping input.
Common Mistakes
- Using
<instead of<=for overlap check (depends on whether endpoints are inclusive). - Forgetting to take
max(last_end, end)when merging (the new interval might be contained). - Sorting by end time when start time is needed for the merge algorithm.
Monotonic Stack
Recognition Signals
- "Next greater element" or "next smaller element" for each position.
- "Largest rectangle in histogram" or "maximal rectangle in binary matrix".
- Stock span, daily temperatures, or trapping rain water.
- O(n) solution needed where brute force is O(n^2).
Core Idea Maintain a stack that is always monotonically increasing or decreasing. When a new element violates the monotonic property, pop elements from the stack — each popped element has found its "next greater" (or "next smaller") in the current element. Every element is pushed and popped at most once, giving O(n) amortized time. The stack stores indices rather than values to enable distance calculations.
Python Template
from typing import List
def next_greater_element(nums: List[int]) -> List[int]:
"""For each element, find the next greater element to its right. -1 if none."""
n = len(nums)
result = [-1] * n
stack: List[int] = [] # indices, monotonically decreasing values
for i in range(n):
while stack and nums[stack[-1]] < nums[i]:
result[stack.pop()] = nums[i]
stack.append(i)
return result
def largest_rectangle_histogram(heights: List[int]) -> int:
"""Largest rectangle area in a histogram."""
stack: List[int] = [] # indices, monotonically increasing heights
max_area = 0
heights_ext = heights + [0] # sentinel to flush remaining bars
for i, h in enumerate(heights_ext):
while stack and heights_ext[stack[-1]] > h:
height = heights_ext[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
Key Edge Cases
- All elements in strictly increasing order — stack never pops until a sentinel.
- All elements equal — every element's "next greater" is -1.
- Single element — result is -1 for next greater, or the element itself for histogram area.
- Circular array variant — iterate through
2 * nindices using modulo.
Common Mistakes
- Storing values instead of indices on the stack (loses position information).
- Forgetting the sentinel value at the end to flush remaining stack elements.
- Confusing monotonically increasing vs. decreasing — increasing stack finds next smaller, decreasing finds next greater.
Competitive Programming Problem Solver
Solve competitive programming and LeetCode-style problems with clear educational explanations, step-by-step walkthroughs, and verified Python solutions.
CRITICAL: Complete ALL 4 phases. Do not stop after classification or skip the agent.
Phase 1: Parse Input
Goal: Extract and understand the problem statement.
If $ARGUMENTS is provided, parse the problem statement from it. Extract:
- Problem description and objective
- Input/output format
- Constraints (N, M, value ranges)
- Example test cases with expected outputs
- Any special conditions (modular arithmetic, multiple test cases, interactive)
If $ARGUMENTS is empty or unclear, use AskUserQuestion to request the problem:
AskUserQuestion:
question: "Please provide the problem statement. You can paste the full text, describe it in your own words, or provide a link."
options:
- label: "Paste problem text"
description: "Paste the full problem statement including constraints and examples"
- label: "Describe the problem"
description: "Describe what the problem asks in your own words"
If the problem statement is ambiguous or missing key information (constraints, examples), ask for clarification before proceeding.
Phase 2: Classify Problem
Goal: Determine the algorithmic category, technique, and difficulty.
Analyze the problem to determine:
2.1 Primary Category
Match to one of:
- Dynamic Programming — optimization over subsequences, counting ways, overlapping subproblems
- Graph Algorithms — connectivity, shortest paths, traversal, network problems
- Search and Optimization — binary search, two pointers, greedy, interval problems
- Data Structures — specialized structures needed (heap, trie, segment tree)
- Math and Combinatorics — number theory, counting, modular arithmetic, game theory
- String Algorithms — pattern matching, palindromes, hashing
2.2 Sub-pattern
Identify the specific technique within the category (e.g., "0/1 Knapsack", "Dijkstra", "Sliding Window").
2.3 Difficulty Estimate
- Easy — single technique, straightforward application
- Medium — requires insight or combining 2 techniques
- Hard — non-obvious technique, complex implementation, or 3+ techniques
- Competition — advanced techniques, mathematical reasoning, or creative construction
2.4 Constraint Analysis
Map input size to required time complexity:
| Input Size | Viable Complexity | Typical Approach |
|---|---|---|
| N ≤ 15 | O(2^N), O(N!) | Bitmask DP, backtracking |
| N ≤ 20 | O(2^N × N) | Bitmask DP |
| N ≤ 100 | O(N^3) | Floyd-Warshall, interval DP |
| N ≤ 500 | O(N^3) | Matrix DP, dense graph algorithms |
| N ≤ 3,000 | O(N^2) | Standard DP (LCS, edit distance) |
| N ≤ 10,000 | O(N^2) or O(N√N) | Careful O(N^2), sqrt decomposition |
| N ≤ 100,000 | O(N log N) | Sorting, binary search, segment tree |
| N ≤ 1,000,000 | O(N) or O(N log N) | Linear scan, prefix sums, two pointers |
| N ≤ 10^8 | O(N) | Simple linear pass |
| N ≤ 10^9+ | O(log N) or O(√N) | Binary search, math formula |
2.5 Secondary Categories
Note if the problem combines techniques (e.g., "Binary Search + DP", "Graph + Greedy").
Present the classification summary to the user before proceeding.
Phase 3: Load References and Spawn Agent
Goal: Provide the solver agent with domain-specific algorithmic knowledge.
3.1 Load Reference Skills
Based on the primary category, load the corresponding reference skill:
- Dynamic Programming →
Read ${CLAUDE_PLUGIN_ROOT}/skills/dp-patterns/SKILL.md - Graph Algorithms →
Read ${CLAUDE_PLUGIN_ROOT}/skills/graph-algorithms/SKILL.md - Search and Optimization →
Read ${CLAUDE_PLUGIN_ROOT}/skills/search-and-optimization/SKILL.md - Data Structures →
Read ${CLAUDE_PLUGIN_ROOT}/skills/data-structures/SKILL.md - Math and Combinatorics →
Read ${CLAUDE_PLUGIN_ROOT}/skills/math-and-combinatorics/SKILL.md - String Algorithms →
Read ${CLAUDE_PLUGIN_ROOT}/skills/string-algorithms/SKILL.md
If a secondary category was identified, load that reference skill as well (maximum 2 reference skills).
3.2 Spawn Problem Solver Agent
Use the Task tool to spawn the problem-solver agent:
Task:
subagent_type: "agent-alchemy-cs-tools:problem-solver"
prompt: |
## Problem Statement
[full problem text with all constraints, I/O format, and examples]
## Classification
- **Category:** [primary category]
- **Sub-pattern:** [specific technique]
- **Difficulty:** [level]
- **Complexity Target:** [required time complexity based on constraints]
- **Secondary Category:** [if applicable]
## Reference Material
[paste the content from the loaded reference skill(s)]
Produce a complete solution following your structured output format.
Phase 4: Present Solution
Goal: Format and present the solution with follow-up options.
Take the agent's structured output and present it to the user. The output includes:
- Classification summary
- Key insight (the "aha" moment)
- Step-by-step approach
- Verified Python solution code
- Time and space complexity analysis with derivation
- Walkthrough tracing through an example
- Edge cases
- Common mistakes
- Alternative approaches
After presenting the solution, offer follow-up actions:
AskUserQuestion:
question: "What would you like to do next?"
options:
- label: "Verify with test cases"
description: "Run the solution through comprehensive test cases including edge cases and stress tests"
- label: "Explain in more detail"
description: "Get a deeper explanation of the approach, technique, or a specific part of the solution"
- label: "Show alternative approach"
description: "See a different way to solve this problem with trade-off analysis"
- label: "Done"
description: "Solution is satisfactory, no further action needed"
If the user selects "Verify with test cases", suggest they use /verify with the problem and solution.
If "Explain in more detail", provide additional explanation of the requested aspect.
If "Show alternative approach", re-spawn the agent with instructions to use a different technique.
String Algorithm Patterns
This reference covers seven foundational string algorithms used in competitive programming and technical interviews. Each pattern includes recognition signals, a core idea explanation, a Python template, and notes on edge cases and common mistakes. Use the pattern recognition table to match problem constraints to the right technique, then drill into the individual pattern section.
Pattern Recognition Table
| Trigger Signals | Technique | Typical Complexity |
|---|---|---|
| Find pattern in text, exact match, prefix function | KMP | O(N + M) |
| Longest common prefix at each position, string period | Z-function | O(N) |
| Multiple pattern search, rolling hash, substring fingerprint | Rabin-Karp | O(N + M) average |
| Longest palindromic substring, count palindromes | Manacher's | O(N) |
| Fast substring comparison, equality checks in O(1) | String Hashing | O(N) preprocess, O(1) query |
| Lexicographic ordering of suffixes, LCP queries, substring counting | Suffix Array | O(N log N) build |
| Dictionary of patterns matched against text, multi-pattern search | Aho-Corasick | O(N + M + Z) |
Where N = text length, M = pattern length (or total pattern lengths), Z = number of matches.
Constraint-to-Technique Mapping
- Single pattern, exact match, N up to 10^6: KMP or Z-function
- All prefix-suffix overlaps: KMP failure function gives overlap chain
- String periodicity or repetition: Z-function (period = smallest i where z[i] + i == N)
- Multiple patterns, moderate count (< 100): Rabin-Karp with rolling hash
- Multiple patterns, large dictionary (10^3+): Aho-Corasick automaton
- Palindrome queries: Manacher's for longest; hashing + binary search for arbitrary checks
- Substring equality or comparison in O(1): Polynomial string hashing with double hash
- Lexicographic queries, distinct substrings, LCP: Suffix array + LCP array
KMP (Knuth-Morris-Pratt)
Recognition Signals
- Find all occurrences of a pattern in a text
- Compute the longest proper prefix that is also a suffix (failure/border array)
- Pattern matching without backtracking on the text pointer
Core Idea
KMP preprocesses the pattern into a failure (prefix) function that records, for each position, the length of the longest proper prefix that is also a suffix. On mismatch, the failure function tells us where to resume comparison without re-scanning text characters, guaranteeing linear time.
Python Template
def kmp_search(text: str, pattern: str) -> list[int]:
"""Return all starting indices where pattern occurs in text."""
n, m = len(text), len(pattern)
if m == 0:
return []
# Build failure function
fail = [0] * m
k = 0
for i in range(1, m):
while k > 0 and pattern[k] != pattern[i]:
k = fail[k - 1]
if pattern[k] == pattern[i]:
k += 1
fail[i] = k
# Search
matches: list[int] = []
k = 0
for i in range(n):
while k > 0 and pattern[k] != text[i]:
k = fail[k - 1]
if pattern[k] == text[i]:
k += 1
if k == m:
matches.append(i - m + 1)
k = fail[k - 1]
return matches
Key Edge Cases
- Empty pattern or empty text (return empty list)
- Pattern longer than text
- Overlapping matches (e.g., pattern "aa" in text "aaaa" yields [0, 1, 2])
- Pattern equals text exactly (single match at index 0)
Common Mistakes
- Off-by-one in failure function construction (loop must start at index 1, not 0)
- Forgetting to reset
k = fail[k - 1]after a full match to allow overlapping matches - Confusing 0-indexed vs 1-indexed failure arrays across reference implementations
Z-function
Recognition Signals
- Compute the longest substring starting at each position that matches a prefix
- Detect string periods or smallest repeating units
- Alternative to KMP for single-pattern matching
Core Idea
The Z-array for a string S stores at each index i > 0 the length of the longest substring starting at i that matches a prefix of S. Construction runs in O(N) using a sliding window [l, r] tracking the rightmost Z-box. For pattern matching, concatenate pattern + separator + text and look for Z-values equal to the pattern length. Periodicity detection: the smallest period p satisfies z[p] + p == N.
Python Template
def z_function(s: str) -> list[int]:
"""Compute the Z-array for string s."""
n = len(s)
z = [0] * n
z[0] = n
l, r = 0, 0
for i in range(1, n):
if i < r:
z[i] = min(r - i, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] > r:
l, r = i, i + z[i]
return z
def z_search(text: str, pattern: str) -> list[int]:
"""Find all occurrences of pattern in text using Z-function."""
combined = pattern + "$" + text
z = z_function(combined)
m = len(pattern)
return [i - m - 1 for i in range(m + 1, len(combined)) if z[i] == m]
Key Edge Cases
- Single-character strings (Z[0] = N by definition, rest are trivial)
- Strings of all identical characters (every Z[i] = N - i)
- Separator character must not appear in pattern or text
Common Mistakes
- Forgetting to set z[0] = n (by convention, z[0] equals the full string length)
- Using a separator character that exists in the input alphabet
- Incorrect window update: the condition is
i + z[i] > r, not>=
Rabin-Karp
Recognition Signals
- Multiple pattern search in a single text
- Substring fingerprinting or equality via hashing
- Problems where average-case O(N + M) suffices and worst-case O(NM) is acceptable
Core Idea
Rabin-Karp computes a polynomial rolling hash for each text window matching the pattern length. The hash slides in O(1) by subtracting the outgoing character's contribution and adding the incoming one. Hash matches are confirmed by character comparison. For multi-pattern search, store all pattern hashes in a set.
Python Template
def rabin_karp(text: str, pattern: str, base: int = 131, mod: int = 10**18 + 9) -> list[int]:
"""Return all starting indices where pattern occurs in text."""
n, m = len(text), len(pattern)
if m > n:
return []
# Precompute highest power
power = pow(base, m - 1, mod)
# Hash the pattern and first window
p_hash = 0
t_hash = 0
for i in range(m):
p_hash = (p_hash * base + ord(pattern[i])) % mod
t_hash = (t_hash * base + ord(text[i])) % mod
matches: list[int] = []
for i in range(n - m + 1):
if t_hash == p_hash and text[i:i + m] == pattern:
matches.append(i)
if i + m < n:
t_hash = (t_hash - ord(text[i]) * power) % mod
t_hash = (t_hash * base + ord(text[i + m])) % mod
return matches
Key Edge Cases
- Hash collisions requiring the string comparison fallback
- Very long patterns where power computation must use modular exponentiation
- Negative hash values in languages with signed modular arithmetic (Python handles correctly)
Common Mistakes
- Forgetting the confirmation step after a hash match (false positives)
- Using a small modulus that causes frequent collisions
- Off-by-one in the sliding window loop bounds
Manacher's Algorithm
Recognition Signals
- Find the longest palindromic substring
- Count total palindromic substrings
- Compute palindrome radii at every center (both odd and even length)
Core Idea
Manacher's algorithm finds the maximum palindrome radius centered at each position in O(N). It processes odd-length and even-length palindromes separately. A center c and right boundary r track the rightmost palindrome; for each new position i, the mirror 2c - i provides an initial radius estimate that is then expanded, avoiding redundant comparisons.
Python Template
def manacher(s: str) -> tuple[list[int], list[int]]:
"""Return (odd, even) palindrome radius arrays.
odd[i] = max radius of odd palindrome centered at i (includes center).
even[i] = max radius of even palindrome centered between i-1 and i.
"""
n = len(s)
odd = [0] * n
l, r = 0, 0
for i in range(n):
odd[i] = max(0, min(r - i, odd[l + r - i])) if i < r else 0
while i - odd[i] >= 0 and i + odd[i] < n and s[i - odd[i]] == s[i + odd[i]]:
odd[i] += 1
if i + odd[i] > r:
l, r = i - odd[i] + 1, i + odd[i]
even = [0] * n
l, r = 0, 0
for i in range(n):
even[i] = max(0, min(r - i, even[l + r - i - 1])) if i < r else 0
while i - even[i] - 1 >= 0 and i + even[i] < n and s[i - even[i] - 1] == s[i + even[i]]:
even[i] += 1
if i + even[i] > r:
l, r = i - even[i], i + even[i]
return odd, even
Key Edge Cases
- Single-character string (always a palindrome of length 1)
- All characters identical (every substring is a palindrome)
- Even-length palindromes require careful boundary indexing
- Empty string input
Common Mistakes
- Mixing up odd and even palindrome handling (different mirror formulas)
- Incorrect mirror index when using the transformed-string variant
- Forgetting boundary checks during expansion (i - radius >= 0)
String Hashing
Recognition Signals
- Compare arbitrary substrings for equality in O(1)
- Fast fingerprint for substrings (search, duplicate detection, binary search + comparison)
Core Idea
Polynomial hashing assigns each string a fingerprint: H(s) = sum of s[i] * base^i mod p. By precomputing prefix hashes and powers, any substring hash is extracted in O(1). Double hashing (two independent base-mod pairs) reduces collision probability to ~1/p^2, reliable for N up to 10^6.
Python Template
class StringHasher:
"""Double polynomial hash for O(1) substring comparison."""
def __init__(self, s: str, base1: int = 131, mod1: int = 10**18 + 9,
base2: int = 137, mod2: int = 10**18 + 7) -> None:
n = len(s)
self.mod1, self.mod2 = mod1, mod2
self.h1 = [0] * (n + 1)
self.h2 = [0] * (n + 1)
self.p1 = [1] * (n + 1)
self.p2 = [1] * (n + 1)
for i in range(n):
self.h1[i + 1] = (self.h1[i] * base1 + ord(s[i])) % mod1
self.h2[i + 1] = (self.h2[i] * base2 + ord(s[i])) % mod2
self.p1[i + 1] = self.p1[i] * base1 % mod1
self.p2[i + 1] = self.p2[i] * base2 % mod2
def query(self, l: int, r: int) -> tuple[int, int]:
"""Return double hash of s[l:r+1] (inclusive on both ends)."""
length = r - l + 1
h1 = (self.h1[r + 1] - self.h1[l] * self.p1[length]) % self.mod1
h2 = (self.h2[r + 1] - self.h2[l] * self.p2[length]) % self.mod2
return (h1, h2)
Key Edge Cases
- Substrings of length 0 or 1
- Hash values wrapping around the modulus (ensure non-negative results)
- Comparing substrings from different strings (build separate hashers)
Common Mistakes
- Using a single hash (high collision risk at N > 10^5)
- Choosing a base smaller than the alphabet size
- Off-by-one in substring index conventions (inclusive vs exclusive bounds)
Suffix Array
Recognition Signals
- Lexicographic ordering of all suffixes, count distinct substrings
- Longest common prefix (LCP) queries between suffixes
- Problems involving sorted suffix structure or substring searching
Core Idea
A suffix array is a sorted array of all suffix starting indices. Construction in O(N log^2 N) uses iterative doubling: sort suffixes by their first 1, 2, 4, ... characters using previous rank as key. The LCP array (Kasai's algorithm, O(N)) stores the longest common prefix between consecutive sorted suffixes. Together they enable distinct substring counting (N*(N+1)/2 - sum(LCP)) and binary search over suffixes.
Python Template
def build_suffix_array(s: str) -> list[int]:
"""Build suffix array in O(N log^2 N) via iterative doubling."""
n = len(s)
sa = list(range(n))
rank = [ord(c) for c in s]
tmp = [0] * n
k = 1
while k < n:
def compare(a: int, b: int) -> int:
if rank[a] != rank[b]:
return rank[a] - rank[b]
ra = rank[a + k] if a + k < n else -1
rb = rank[b + k] if b + k < n else -1
return ra - rb
from functools import cmp_to_key
sa.sort(key=cmp_to_key(compare))
tmp[sa[0]] = 0
for i in range(1, n):
tmp[sa[i]] = tmp[sa[i - 1]] + (1 if compare(sa[i - 1], sa[i]) < 0 else 0)
rank[:] = tmp
if rank[sa[-1]] == n - 1:
break
k *= 2
return sa
def build_lcp_array(s: str, sa: list[int]) -> list[int]:
"""Build LCP array using Kasai's algorithm in O(N)."""
n = len(s)
rank = [0] * n
for i in range(n):
rank[sa[i]] = i
lcp = [0] * n
k = 0
for i in range(n):
if rank[i] == 0:
k = 0
continue
j = sa[rank[i] - 1]
while i + k < n and j + k < n and s[i + k] == s[j + k]:
k += 1
lcp[rank[i]] = k
k = max(k - 1, 0)
return lcp
Key Edge Cases
- Single-character strings
- Strings with all identical characters (suffix array is reverse order)
- Appending a sentinel character ('$') for algorithms requiring unique termination
Common Mistakes
- Forgetting the boundary check
a + k < nwhen comparing second-half ranks - Using O(N^2 log N) naive sort instead of rank-based doubling
Aho-Corasick
Recognition Signals
- Search for multiple patterns simultaneously in a single text
- Dictionary matching: given a set of words, find all occurrences in a text
- Large pattern dictionary (hundreds or thousands of patterns)
Core Idea
Aho-Corasick builds a trie from all patterns, then adds failure links connecting each node to the longest proper suffix that is also a trie prefix. Output lists along failure chains ensure all matching patterns are reported. Text is processed character by character through the automaton in O(N + M + Z) total time.
Python Template
from collections import deque
class AhoCorasick:
"""Multi-pattern matching automaton."""
def __init__(self) -> None:
self.goto: list[dict[str, int]] = [{}]
self.fail: list[int] = [0]
self.output: list[list[int]] = [[]]
def add_pattern(self, pattern: str, index: int) -> None:
"""Add a pattern with its identifier to the automaton."""
state = 0
for ch in pattern:
if ch not in self.goto[state]:
self.goto[state][ch] = len(self.goto)
self.goto.append({})
self.fail.append(0)
self.output.append([])
state = self.goto[state][ch]
self.output[state].append(index)
def build(self) -> None:
"""Construct failure links using BFS."""
queue: deque[int] = deque()
for ch, s in self.goto[0].items():
queue.append(s)
while queue:
u = queue.popleft()
for ch, v in self.goto[u].items():
queue.append(v)
f = self.fail[u]
while f and ch not in self.goto[f]:
f = self.fail[f]
self.fail[v] = self.goto[f].get(ch, 0)
if self.fail[v] == v:
self.fail[v] = 0
self.output[v] = self.output[v] + self.output[self.fail[v]]
def search(self, text: str) -> list[tuple[int, int]]:
"""Return list of (end_position, pattern_index) for all matches."""
state = 0
results: list[tuple[int, int]] = []
for i, ch in enumerate(text):
while state and ch not in self.goto[state]:
state = self.fail[state]
state = self.goto[state].get(ch, 0)
for pat_idx in self.output[state]:
results.append((i, pat_idx))
return results
Key Edge Cases
- Patterns that are prefixes of other patterns
- Overlapping pattern matches at the same text position
- Empty patterns in the dictionary (filter before insertion)
Common Mistakes
- Forgetting to merge output lists along failure links (misses suffix-state patterns)
- Not guarding against failure links pointing back to the same node
- Building the automaton before all patterns are added
Solution Verifier
Verify competitive programming and LeetCode solutions for correctness through static analysis, automated test case generation, and execution.
CRITICAL: Complete ALL 4 phases. Do not stop after static analysis.
Phase 1: Parse Input
Goal: Extract the problem statement and solution code.
Parse $ARGUMENTS to extract:
- Problem statement — the full problem description with constraints, I/O format, and examples
- Solution code — the user's Python solution (inline code, file path, or pasted)
If both are in $ARGUMENTS, separate them. The problem statement typically comes first, followed by the solution code in a code block or after a separator.
If the solution is a file path, read it:
Read [file_path]
If the problem statement is missing, ask for it:
AskUserQuestion:
question: "Please provide the problem statement for verification. I need it to generate test cases and validate correctness."
options:
- label: "Paste problem text"
description: "Paste the full problem statement with constraints and examples"
- label: "Describe the problem"
description: "Describe what the problem asks — I'll generate test cases from that"
If the solution code is missing, ask for it:
AskUserQuestion:
question: "Please provide your solution code to verify."
options:
- label: "Paste code"
description: "Paste your Python solution code"
- label: "Provide file path"
description: "Give the path to your solution file"
If the solution is not Python, note this to the user and proceed with analysis (the verifier agent will handle language adaptation).
Phase 2: Spawn Verifier Agent
Goal: Delegate verification to the specialized agent.
Use the Task tool to spawn the solution-verifier agent:
Task:
subagent_type: "agent-alchemy-cs-tools:solution-verifier"
prompt: |
## Problem Statement
[full problem text with all constraints, I/O format, and examples]
## Solution Code
```python
[the user's solution code]
```
Perform full verification following your structured process:
1. Static analysis for logic errors and edge case handling
2. Generate test cases (basic, edge, stress)
3. Write and execute test harness
4. Compile report with verdict
Phase 3: Receive Results
Goal: Collect and validate the agent's findings.
The agent returns a structured report containing:
- Static analysis findings with severity ratings
- Test results table (pass/fail per test case)
- Overall verdict (CORRECT / INCORRECT / PARTIALLY CORRECT / TLE RISK)
- Bug analysis for failures (root cause, affected lines, fix suggestion)
- Performance assessment (algorithm complexity vs constraint requirements)
- Improvement suggestions
Review the report for completeness. If the agent encountered infrastructure issues (test harness errors, not solution bugs), note this to the user.
Phase 4: Present Report
Goal: Present the verification results with follow-up options.
Present the report to the user with clear formatting:
- Verdict — the overall result prominently displayed
- Static Analysis — findings table if there are any Critical or Warning findings
- Test Results — the pass/fail table showing all test cases
- Bug Analysis — for each failure: root cause, affected lines, and specific fix suggestion
- Performance Assessment — whether the solution meets time/space requirements
- Improvement Suggestions — code quality and optimization recommendations
After presenting the report, offer follow-up actions:
AskUserQuestion:
question: "What would you like to do next?"
options:
- label: "Fix bugs and re-verify"
description: "I'll apply the suggested fixes and run verification again"
- label: "Show corrected solution"
description: "Generate a complete corrected solution using /solve"
- label: "Add more test cases"
description: "Generate additional test cases targeting specific scenarios"
- label: "Done"
description: "Verification complete, no further action needed"
If the user selects "Fix bugs and re-verify":
- Apply the fix suggestions from the bug analysis
- Re-run Phase 2-4 with the corrected code
If "Show corrected solution":
- Suggest using
/solvewith the same problem statement to get a fresh, verified solution
If "Add more test cases":
- Ask what scenarios to target (specific edge cases, larger inputs, adversarial cases)
- Re-spawn the verifier with additional test requirements
Agents 2
Problem Solver
You are an expert competitive programmer and educator. You solve algorithmic problems and produce clear, educational solutions in Python.
What You Receive
When spawned, you receive:
- Problem statement with constraints, I/O format, and examples
- Classification (category, sub-pattern, difficulty, constraint analysis)
- Reference material from domain-specific algorithmic reference skills
Solution Process
Follow these steps in order:
Step 1: Validate Classification
Confirm or refine the provided classification. If the problem is better solved with a different technique than suggested, explain why and adjust.
Step 2: Identify the Key Insight
Determine the core observation that makes the problem solvable efficiently. This is the "aha" moment — the single most important idea. Express it in 1-3 sentences.
Step 3: Design the Approach
Describe the algorithm in 3-7 numbered steps. Each step should be a concrete action, not a vague description. Reference the technique from the classification.
Step 4: Write the Solution
Write clean Python code following these standards:
- Type hints on function signatures
- Meaningful variable names (not single letters except for loop indices)
- Comments explaining non-obvious logic (the "why", not the "what")
- Efficient implementation matching the stated complexity
- Standard library only — no external packages
- Prefer iterative over recursive when both have the same complexity (avoids Python's 1000 recursion limit)
- Use
sys.stdinfor fast I/O in competition-style problems - Separate the core algorithm into a function from I/O handling
Step 5: Verify Against Examples
Run the solution against ALL provided examples using Bash:
python3 -c "
<solution code here>
" <<< "<example input>"
If any example fails, debug and fix before continuing. Do not output an unverified solution.
Step 6: Analyze Complexity
Derive time and space complexity with clear reasoning. Tie the analysis to the input constraints to show why it's sufficient.
Step 7: Walkthrough
Trace through one example step-by-step, showing the state of key variables at each iteration or decision point. Use a table or numbered steps.
Step 8: Edge Cases and Mistakes
Identify edge cases the solution handles and common mistakes programmers make with this problem type.
Output Format
Structure your response exactly as follows:
## Classification
- **Category:** [primary category]
- **Sub-pattern:** [specific technique name]
- **Difficulty:** [Easy / Medium / Hard / Competition]
- **Complexity Target:** [required time complexity based on constraints]
## Key Insight
[1-3 sentences explaining the core observation that unlocks the solution]
## Approach
1. [First concrete step]
2. [Second concrete step]
...
## Solution
\`\`\`python
[clean, commented Python code]
\`\`\`
## Complexity Analysis
- **Time:** O(...) — [derivation explanation]
- **Space:** O(...) — [derivation explanation]
## Walkthrough
[Step-by-step trace through Example 1 showing variable states]
## Edge Cases
- **[case description]:** [how the solution handles it]
- ...
## Common Mistakes
- **[mistake]:** [why it's wrong and how to avoid it]
- ...
## Alternative Approaches
- **[approach name]:** [1-2 sentence description, complexity, when to prefer it]
- ...
Guidelines
- If the problem has multiple valid answers, note this explicitly
- If the problem requires special I/O handling (interactive, multiple test cases, large input), include appropriate I/O code
- When multiple approaches exist, implement the most efficient that fits the constraints
- For problems with MOD = 10^9 + 7, always apply modular arithmetic correctly
- For problems with large inputs (N > 10^5), use
sys.stdin.readlineinstead ofinput() - Never use
globalvariables; prefer function-scoped solutions - If the reference material contains a relevant template, adapt it to the specific problem rather than copying verbatim
Solution Verifier
You are a solution verification specialist for competitive programming. You rigorously test solutions through static analysis and dynamic testing, then produce a clear verdict with actionable feedback.
What You Receive
When spawned, you receive:
- Problem statement with constraints, I/O format, and examples
- Solution code (Python) to verify
Verification Process
Follow these 5 steps in order:
Step 1: Static Analysis
Read the solution code and analyze:
- Algorithm identification: What technique does the solution use? What is its time and space complexity?
- Logic errors: Off-by-one errors, wrong comparison operators, uninitialized variables, incorrect base cases
- Edge case handling: Does it handle empty input, single element, all-same values, maximum N?
- Overflow risks: Integer overflow in intermediate calculations (less common in Python but possible with floats)
- Recursion depth: Does it exceed Python's default 1000 limit? Does it set
sys.setrecursionlimit? - Infinite loops: Are loop termination conditions correct? Can
whileloops get stuck? - Off-by-one: Array indexing, range bounds, boundary conditions
- I/O correctness: Does it match the expected input/output format?
Record findings with severity: Critical (will cause wrong answer), Warning (may cause issues), Info (style/optimization).
Step 2: Generate Test Cases
Create test cases in three categories:
Basic tests: All examples from the problem statement. These MUST be included.
Edge case tests (at least 3):
- Empty or minimal input (N=0, N=1)
- All elements identical
- Sorted input (ascending and descending)
- Maximum/minimum values in constraints
- Boundary values (N at constraint limits but small enough to verify)
- Single valid answer vs. multiple valid answers
Stress tests (at least 2):
- Random inputs near constraint limits (generate with Python
randommodule) - Worst-case inputs for the algorithm (e.g., sorted input for quicksort, dense graphs for BFS)
- For stress tests with large N, generate a brute-force reference solution for small inputs (N <= 20) and compare outputs
Step 3: Write Test Harness
Write a temporary Python test file to /tmp/cs_verify_test.py that:
- Defines the user's solution as a callable function (wrap it if needed)
- Runs each test case, capturing stdout
- Compares actual output against expected output
- Measures execution time per test (using
time.perf_counter) - For stress tests without known expected output, compares against brute-force solution
- Reports results in a structured format
Handle common issues:
- Solutions that read from stdin: redirect input via
subprocessor string injection - Solutions that call
sys.exit(): wrap in subprocess - Solutions with global state: reset between test cases
Step 4: Execute Tests
Run the test harness:
python3 /tmp/cs_verify_test.py
Capture and parse:
- Pass/fail status per test
- Actual vs. expected output for failures
- Execution time per test
- Any runtime errors (exceptions, segfaults, TLE)
If the test harness itself has errors, fix and re-run. Do not report test infrastructure failures as solution bugs.
Step 5: Compile Report
Synthesize all findings into the structured output format below.
After completing the report, clean up temporary files:
rm -f /tmp/cs_verify_test.py
Output Format
Structure your response exactly as follows:
## Static Analysis
| # | Finding | Severity | Line | Description |
|---|---------|----------|------|-------------|
| 1 | [short name] | Critical/Warning/Info | [line #] | [description] |
| ... | ... | ... | ... | ... |
## Test Results
| # | Category | Test Name | Input (truncated) | Expected | Actual | Time | Result |
|---|----------|-----------|-------------------|----------|--------|------|--------|
| 1 | Basic | Example 1 | [input] | [expected] | [actual] | 0.001s | PASS/FAIL |
| ... | ... | ... | ... | ... | ... | ... | ... |
**Passed:** X/Y tests
## Verdict: [CORRECT / INCORRECT / PARTIALLY CORRECT / TLE RISK]
[1-2 sentence summary of the verdict rationale]
## Bug Analysis
*(Only include if there are failures)*
For each failing test:
### Bug [N]: [short description]
- **Failing test(s):** [test names]
- **Root cause:** [explanation of why the solution produces wrong output]
- **Affected line(s):** [line numbers in the solution]
- **Fix suggestion:** [specific code change to fix the bug]
## Performance Assessment
- **Algorithm complexity:** O(...) [what the solution actually implements]
- **Constraint requirement:** O(...) [what the problem constraints demand]
- **Verdict:** [Meets requirements / Risk of TLE / Will TLE]
- **Details:** [any performance concerns]
## Improvement Suggestions
- [suggestion 1 — algorithmic or code quality]
- [suggestion 2]
- ...
Verdict Criteria
- CORRECT: All tests pass, complexity meets constraints, no critical static analysis findings
- INCORRECT: One or more tests produce wrong output
- PARTIALLY CORRECT: Some edge cases fail but core logic is sound
- TLE RISK: Solution is correct but complexity may exceed time limits for large inputs
Guidelines
- Always test the provided examples first — if those fail, the solution has a fundamental bug
- For stress tests, use a fixed random seed (
random.seed(42)) for reproducibility - If the solution has syntax errors, report them immediately without attempting to run
- Time individual test executions; flag any test approaching 1 second as a TLE risk
- When generating brute-force reference solutions, keep them simple and obviously correct
- If the problem has multiple valid outputs, check if the solution's output is among the valid ones (don't just compare strings)
- Report the most impactful issues first (Critical before Warning before Info)
Sponsors
Details
- Marketplace
- sequenzia/agent-alchemy
- Source
- claude/cs-tools
- Category
- Community
- License
- MIT