1-Page Interview Reference
Master Complexity & Template Cheat Sheet
A rapid, 1-click copyable summary of time/space complexities, input constraint rules of thumb, and canonical algorithm templates across all 13 modules.
1. Input Size (`N`) → Target Time Complexity Rule of Thumb
| Operation / Pattern | Time | Space | Notes |
|---|---|---|---|
| N <= 10..12 | O(N!) or O(2^N) | O(N) | Backtracking: Permutations, N-Queens |
| N <= 20 | O(2^N) or O(N * 2^N) | O(N) | Subsets, Bitmask DP |
| N <= 500 | O(N^3) | O(N^2) | Floyd-Warshall, Interval/Partition DP |
| N <= 2,000..5,000 | O(N^2) | O(N) or O(N^2) | 2D DP (LCS, Edit Distance), 3Sum |
| N <= 10^5 | O(N log N) or O(N) | O(N) or O(1) | Sorting, Heap, Binary Search, Two Pointers, Sliding Window |
| N <= 10^9 | O(log N) or O(1) | O(1) | Binary Search on Answer, Bit Manipulation, Math |
2. Data Structure Operations Summary
| Operation / Pattern | Time | Space | Notes |
|---|---|---|---|
| Hash Map / Hash Set | O(1) avg | O(N) | Lookup, insert, delete |
| Binary Search (Sorted / Answer Space) | O(log N) | O(1) | Halves search space each step |
| Monotonic Stack / Deque | O(N) | O(N) | Each element pushed & popped at most once |
| Binary Heap (Priority Queue) | O(log N) push/pop | O(N) | O(1) peek min/max; Top-K takes O(N log K) |
| Trie (Prefix Tree) | O(L) | O(Total Chars) | L = word length; fast prefix matching |
| Graph BFS / DFS / Kahn's Topo Sort | O(V + E) | O(V + E) | Adjacency list + visited set |
| Dijkstra's Shortest Path | O(E log V) | O(V + E) | Non-negative edge weights + Min-Heap |
| Disjoint Set Union (Union-Find) | O(alpha(N)) ≈ O(1) | O(N) | Path compression + union by rank/size |
3. Copy-Ready Universal Templates (4 Languages)
A. Sliding Window (Variable Size — Expand Right, Shrink Left)
Open Module →left = 0
for right, x in enumerate(nums):
# 1. Add nums[right] to window state
while window_is_invalid():
# 2. Remove nums[left] from window state
left += 1
best = max(best, right - left + 1)B. Binary Search on Answer Space (First Feasible Value)
Open Module →left, right = min_possible, max_possible
while left < right:
mid = left + (right - left) // 2
if can_finish(mid):
right = mid # mid works; try smaller
else:
left = mid + 1 # mid too small; go higher
return leftC. Disjoint Set Union (Union-Find with Path Compression)
Open Submodule →class DSU:
def __init__(self, n: int):
self.parent = list(range(n))
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a: int, b: int) -> bool:
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
self.parent[pa] = pb
return TrueD. Dijkstra's Shortest Path (Min-Heap)
Open Submodule →import heapq
def dijkstra(n: int, adj: list[list[tuple[int, int]]], src: int) -> list[int]:
dist = [float("inf")] * n
dist[src] = 0
pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in adj[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
return dist