Explain algorithm invariants and the changes that invalidate them
Compare the state, not just the code
These notes are for the second pass after a coding attempt. If two implementations look different, ask what each remembers and why that information is enough. For two-sum, both may remember earlier values. For a window, both must keep a boundary that never moves backward. Those invariants explain correctness better than matching lines.
Choose your attempted problem below, trace its smallest counterexample, and identify one changed requirement that needs different state. The shared helpers and standalone problem bundles sometimes have different return contracts, as the reference table explains.
Use these notes after attempting the problem set. The complete implementations are in algorithms.py (download file, source below); compare your invariant with the code before comparing line by line.
Read the supplied code · algorithms.py
"""Reference solutions. Try the exercises in README.md before opening this file."""
from collections import Counter, OrderedDict, deque
from heapq import heappop, heappush, nlargest
def two_sum(nums, target):
visited = {}
for j, value in enumerate(nums):
complement = target - value
if complement in visited:
return visited[complement], j
visited.setdefault(value, j)
return None
def longest_unique(text):
left = best = 0
last_seen = {}
for right, char in enumerate(text):
left = max(left, last_seen.get(char, -1) + 1)
best = max(best, right - left + 1)
last_seen[char] = right
return best
def subarray_sum(nums, target):
prefix_counts = {0: 1}
prefix = result = 0
for value in nums:
prefix += value
result += prefix_counts.get(prefix - target, 0)
prefix_counts[prefix] = prefix_counts.get(prefix, 0) + 1
return result
def lower_bound(nums, target):
lo, hi = 0, len(nums)
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def merge_intervals(intervals):
"""Closed intervals; touching endpoints merge. Does not mutate input."""
out = []
for start, end in sorted(intervals):
if start > end:
raise ValueError('reversed interval')
if out and start <= out[-1][1]:
out[-1][1] = max(out[-1][1], end)
else:
out.append([start, end])
return out
def top_k_frequent(nums, k):
if k < 0:
raise ValueError('k must be nonnegative')
counts = Counter(nums)
# Higher count wins; smaller value breaks ties deterministically.
return nlargest(k, counts, key=lambda value: (counts[value], -value))
def islands(grid):
"""Rectangular list of lists of '0'/'1'; input remains unchanged."""
if not grid:
return 0
cols = len(grid[0])
if any(len(row) != cols or any(x not in ('0', '1') for x in row) for row in grid):
raise ValueError('expected rectangular binary grid')
seen = set()
count = 0
for r, row in enumerate(grid):
for c, value in enumerate(row):
if value != '1' or (r, c) in seen:
continue
count += 1
seen.add((r, c))
queue = deque([(r, c)])
while queue:
x, y = queue.popleft()
for a, b in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
if 0 <= a < len(grid) and 0 <= b < cols and grid[a][b] == '1' and (a, b) not in seen:
seen.add((a, b)) # Mark on enqueue, not dequeue.
queue.append((a, b))
return count
def course_order(n, prerequisites):
"""Each pair is (course, prerequisite); [] means a cycle or no courses."""
if n < 0:
raise ValueError('negative course count')
adjacency = [set() for _ in range(n)]
degree = [0] * n
for course, prerequisite in prerequisites:
if not 0 <= course < n or not 0 <= prerequisite < n:
raise ValueError('course outside graph')
if course not in adjacency[prerequisite]:
adjacency[prerequisite].add(course)
degree[course] += 1
queue = deque(i for i, d in enumerate(degree) if d == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in adjacency[node]:
degree[neighbor] -= 1
if degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == n else []
def shortest_paths(n, edges, source):
"""Directed nonnegative weighted graph; unreachable distances are infinity."""
if not 0 <= source < n:
raise ValueError('invalid source')
graph = [[] for _ in range(n)]
for u, v, weight in edges:
if not 0 <= u < n or not 0 <= v < n or weight < 0:
raise ValueError('invalid edge')
graph[u].append((v, weight))
distance = [float('inf')] * n
distance[source] = 0
heap = [(0, source)]
while heap:
cost, node = heappop(heap)
if cost != distance[node]:
continue
for neighbor, weight in graph[node]:
candidate = cost + weight
if candidate < distance[neighbor]:
distance[neighbor] = candidate
heappush(heap, (candidate, neighbor))
return distance
class LRU:
"""Capacity in entries; None denotes a miss. Not thread-safe."""
def __init__(self, capacity):
if capacity < 0:
raise ValueError('negative capacity')
self.capacity = capacity
self.data = OrderedDict()
def get(self, key):
if key not in self.data:
return None
self.data.move_to_end(key)
return self.data[key]
def put(self, key, value):
if self.capacity == 0:
return
self.data[key] = value
self.data.move_to_end(key)
if len(self.data) > self.capacity:
self.data.popitem(last=False)
def min_coins(coins, amount):
if amount < 0 or any(c <= 0 for c in coins):
raise ValueError('nonnegative amount and positive coins required')
dp = [0] + [amount + 1] * amount
for total in range(1, amount + 1):
for coin in coins:
if coin <= total:
dp[total] = min(dp[total], dp[total-coin] + 1)
return -1 if dp[amount] > amount else dp[amount]
def daily_temperatures(temperatures):
answer = [0] * len(temperatures)
stack = []
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
previous = stack.pop()
answer[previous] = i - previous
stack.append(i)
return answer
def word_exists(board, word):
"""4-neighbor word search; do not reuse a cell or mutate the board."""
if not word:
return True
if not board:
return False
cols = len(board[0])
if any(len(row) != cols for row in board):
raise ValueError('ragged board')
def visit(r, c, index, used):
if not (0 <= r < len(board) and 0 <= c < cols) or (r, c) in used or board[r][c] != word[index]:
return False
if index == len(word) - 1:
return True
used.add((r, c))
found = any(visit(a, b, index+1, used) for a, b in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)))
used.remove((r, c))
return found
return any(visit(r, c, 0, set()) for r in range(len(board)) for c in range(cols))
class Trie:
END = object()
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for char in word:
node = node.setdefault(char, {})
node[self.END] = True
def contains(self, word):
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return self.END in node
Complement map
For two-sum, each index asks whether an earlier element completes its target. Look up the complement before inserting the current index, so a single value is not reused twice. The map remembers earlier work. With [3,3], the second 3 finds the first. If you need every valid pair, one stored index per value is no longer enough; change the output contract before changing the implementation.
Binary search
Keep uninspected elements in the half-open interval [lo, hi). The answer boundary remains in the inclusive range [lo, hi], so it can equal len(nums). If nums[mid] < target, every index through mid is too small, so lo=mid+1. Otherwise the first qualifying value can still be mid, so hi=mid. Each iteration shrinks the interval; termination at lo==hi yields the first index whose value is at least target, or n if none. Sorting an unsorted input first adds O(n log n) work and may lose original positions.
Interval merging
Sort by start. The only output interval the next interval can overlap is the last one: earlier outputs end before that last interval starts. If the next start is within the last closed interval, extend its end to the maximum. Otherwise append a new interval. For half-open intervals [start,end), a meeting ending at 10 does not conflict with one starting at 10; choose < rather than <= when that is the desired contract.
Top K with a heap
Count values, then maintain the K strongest candidates. The smallest retained candidate is the one to replace when a better item appears. This spends O(log K) per considered distinct value instead of sorting all u values. If K is almost u, sorting is simpler and can be competitive. Deterministic ties matter for reproducible tests. A heap is not a sorted list: only its root has the guaranteed extremal position.
BFS and Dijkstra
BFS uses a FIFO queue because all edges cost one step: discovering a node from the current distance layer gives its shortest unweighted distance. Mark nodes when enqueued, otherwise several parents can enqueue the same node. A grid is just a graph with implicit neighbor edges.
Dijkstra's smallest tentative distance becomes final under nonnegative edge weights. A later shorter route pushes a new heap entry; the old entry remains but is skipped when popped. Negative edges violate the reasoning. For non-unit positive weights, FIFO BFS does not generally yield minimum cost.
Dependency order
Indegree counts unfinished prerequisites. Only zero-indegree tasks can enter the ready queue. Completing a task decrements each outgoing dependent once. Deduplicate repeated prerequisite pairs, or counts and decrements can disagree. If fewer than V tasks finish, a cycle prevents completion. This answers “find an order,” not every scheduling optimization involving durations, priorities, or limited parallelism.
Dynamic programming
For coin change, define dp[x] as the minimum number of coins that sum to x. dp[0]=0 is the base case. Every nonempty solution ends with some coin c, leaving a smaller subproblem x-c. Therefore consider 1+dp[x-c] for each usable coin. Increasing x ensures dependencies are already computed. An unreachable sentinel must exceed any possible valid answer. Greedy largest-first fails for [1,3,4] and amount 6 because 4+1+1 is worse than 3+3.
Memory optimization must respect dependencies. Reducing an O(A) table without proving which older states are needed can silently change the algorithm. O(A×m) is pseudo-polynomial in the numeric amount, not polynomial in the number of bits used to encode A.
Monotonic stack
For daily temperatures, keep unresolved indices whose temperatures are non-increasing from bottom to top. A warmer value resolves every colder index at the top. Each index is pushed once and popped at most once, so the nested loop is O(n) amortized. Equal temperatures do not resolve one another because the question says strictly warmer. Store indices rather than only temperatures so you can compute the waiting distance.
Backtracking
Word search explores a choice, marks the cell used, recurses, then undoes the mark. The used set belongs to the current path, not all explored paths. A cell rejected in one attempted path may be valid in another. Check the final character before exploring beyond it. The number of paths can grow exponentially; pruning helps typical cases but does not turn the worst case into linear time. Test that no successful or failed search mutates the caller's board.
Trie
A trie stores shared prefixes as paths. Inserting app does not automatically insert ap; a terminal marker distinguishes a complete word from a prefix. Exact lookup walks one edge per character. Memory depends on stored prefixes and child representation. For autocomplete you also need ranking and a bound on returned candidates; a trie alone does not decide what suggestions are best.
LRU
Lookup and recency are different jobs. The dictionary points to an entry; a doubly linked list moves that entry without a scan. OrderedDict exposes the combination in Python. Every successful get and every put refreshes recency; overwrite must not increase size. Capacity zero is a legitimate boundary. TTL, byte limits, and multi-threaded access require additional policies and synchronization.
Choose the language intentionally
Python: know dictionary/set operations, deque.popleft, heapq, tuple ordering, and recursion limits. Repeated slicing copies data; a recursive function that looks logarithmic can allocate more than expected. Python strings iterate code points, which are not always displayed characters.
TypeScript: know Map/Set, explicit numeric comparators for sorting, Promise scheduling, AbortSignal, and runtime validation. Array.shift() can incur linear work; an index-based queue avoids repeated moves. Type stripping runs code but is not type checking. Static typing cannot validate network JSON or stop a logical race.
Retrieval test
For each pattern, write its invariant, a minimal counterexample to the naive approach, and a changed requirement that breaks your current solution. If you can only reproduce the reference code, repeat this exercise before adding another problem.