FIFO
Two traversals, and the twenty-four problems that are secretly just those two traversals. Every lecture is wrapped: primed by an intro, checked by drills, then applied to the sheet problems it unlocks.
This is not a list of problems. It is 22 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
26 PROBLEMS · 15 LINK TO LEETCODE · THE REST ARE CONCEPTS THE DRILLS COVER
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here.
Almost every problem in this deck is BFS or DFS wearing a costume. The statement tells you which one — and getting that right is most of the work.
Islands, provinces, friend circles — anything asking how many groups.
Outer loop + DFS or BFSO(V + E)Shortest path where each move costs the same. Never DFS for this.
BFS, layer by layerO(V + E)Rotting oranges, nearest 1, fire spreading — many starting points at once.
Multi-source BFSO(V + E)Undirected needs the parent skip; directed needs the recursion stack.
DFS (parent / on-stack)O(V + E)Course schedule, build order, alien dictionary — X must come before Y.
Topological sort · Kahn'sO(V + E)Two teams, two colours, no conflict between members of the same side.
Bipartite check by colouringO(V + E)A graph is nodes, and the pairs of nodes that are joined. Everything else — directed, weighted, cyclic, connected — is a modifier bolted onto that one idea. This lecture is vocabulary, and the vocabulary is what makes every later problem statement readable.
WHAT EXACTLY IS A GRAPH, AND WHAT ARE THE WORDS FOR ITS PARTS?
In an undirected graph with E edges, what do all the node degrees add up to?
Every edge has two endpoints, and contributes 1 to the degree of each. Sum over all nodes and you have counted every edge twice — so the total is 2E. This is also why an undirected adjacency list holds 2E entries, not E.
A connected undirected graph has N nodes and exactly N−1 edges. What is it?
Connected + N−1 edges = tree. Add any edge and you create exactly one cycle; remove any edge and it splits in two. Recognising this instantly matters because tree problems drop the visited array in favour of a simple parent check.
Why does 0-indexed vs 1-indexed bite harder in graph problems than in array problems?
You allocate two N-sized structures up front. Size them wrong and node N either never gets visited or writes past the end — and neither shows up as an obvious crash on the sample case. Read the constraints for the indexing before you allocate.
You are being handed edges and asked anything at all about connectivity. Before you write a line, settle three things: directed or not, weighted or not, 0- or 1-indexed.
This is the vocabulary problem. The only real work is reading the input format correctly and sizing your structures to match. Getting N and the indexing right here prevents a whole class of silent bugs later.
int V, E; cin >> V >> E; // 1-indexed nodes → size V+1, not V vector<int> adj[V + 1]; for (int i = 0; i < E; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); // omit if DIRECTED }
V, E = map(int, input().split()) # 1-indexed nodes -> size V+1, not V adj = [[] for _ in range(V + 1)] for _ in range(E): u, v = map(int, input().split()) adj[u].append(v) adj[v].append(u) # drop this line if DIRECTED
If nodes are 1-indexed, declare adj[V+1]. Declaring adj[V] and then touching node V writes off the end — it usually will not crash, it will just corrupt something adjacent and fail on a case you cannot reproduce.
Two ways to answer the only question a traversal ever asks: who are my neighbours? A matrix answers in O(1) but costs O(N²) memory. A list costs O(2E) and answers in O(degree). At the sheet's constraints, one of these is simply dead.
HOW DO YOU STORE A GRAPH SO YOUR CODE CAN ASK 'WHO ARE MY NEIGHBOURS?'
Space taken by an adjacency list for an undirected graph with N nodes and E edges?
N buckets, plus two entries per edge because u lands in v's list and v lands in u's. That 2E is the whole reason the list wins: at N = 10⁵ and E = 10⁵ a list holds ~3×10⁵ ints while a matrix would demand 10¹⁰ cells.
This builds a DIRECTED graph. One line does not belong. Which?
for (auto &e : edges) { adj[e.first].push_back(e.second); adj[e.second].push_back(e.first); }
Pushing both ways is the undirected build. In a directed graph u→v does not imply v→u, and adding the reverse edge quietly destroys every algorithm downstream — topological sort finds no valid order, cycle detection fires on every pair. One line, total collapse.
Constraints say N = 10⁵ and E = 2×10⁵. Which representation, and why?
10⁵ squared is 10¹⁰ cells. At one byte each that is 10 GB against a typical 256 MB limit. The list needs ~4×10⁵ ints. Read the constraint, then pick the structure — the same move as the complexity ladder, applied to memory.
Constraints tell you which representation is even legal. N above ~10⁴ kills the matrix outright — O(N²) memory is the deciding factor, not lookup speed.
A matrix answers is u joined to v? in O(1) but costs O(N²) memory. A list answers who are u's neighbours? in O(degree) and costs O(2E). Traversals only ever ask the second question, which is why the list wins almost everywhere on this sheet.
// ADJACENCY LIST — the default choice vector<int> adj[N + 1]; adj[u].push_back(v); adj[v].push_back(u); // undirected only // WEIGHTED — store the weight alongside vector<pair<int,int>> wadj[N + 1]; wadj[u].push_back({v, w}); // ADJACENCY MATRIX — only when N is small vector<vector<int>> m(N, vector<int>(N, 0)); m[u][v] = m[v][u] = 1;
# ADJACENCY LIST - the default choice adj = [[] for _ in range(n + 1)] adj[u].append(v) adj[v].append(u) # undirected only # WEIGHTED - store the weight alongside wadj = [[] for _ in range(n + 1)] wadj[u].append((v, w)) # ADJACENCY MATRIX - only when n is small m = [[0] * n for _ in range(n)] m[u][v] = m[v][u] = 1
For a directed graph push one way only. Adding the reverse edge out of habit silently converts the problem into a different one — topological sort then finds no valid ordering and cycle detection fires on every single edge.
The picture in the problem statement may be several graphs wearing a trenchcoat. Nothing guarantees you can reach every node from node 1 — and that single fact is why every traversal you will write is wrapped in a loop over all nodes.
WHY DOES EVERY GRAPH TRAVERSAL START WITH A LOOP OVER ALL NODES?
Why wrap BFS/DFS in a for-loop over every node instead of just calling it on node 0?
A single traversal only ever reaches one component. If the graph is in three pieces, one call visits one piece and returns, and you silently answer for a third of the input. The outer loop is the cheapest insurance in graph code.
This counts connected components. What breaks it?
int count = 0; for (int i = 0; i < N; i++) { vector<int> vis(N, 0); // fresh each iteration if (!vis[i]) { dfs(i, adj, vis); count++; } }
Declaring vis inside the loop throws away everything the previous traversal learned. Every node then passes the !vis[i] test, you fire N traversals, and a graph with 2 components reports N. The visited array must outlive the loop — that is the entire point of it.
A 7-node graph has edges 1-2, 2-3, 5-6. Nodes 4 and 7 have no edges. How many components?
{1,2,3}, {5,6}, {4}, {7} — four. An isolated node with zero edges is still a component, and forgetting that is the classic off-by-two on Number of Provinces. Every node belongs to exactly one component, always.
The statement says a graph but never promises it is one piece. Any phrase like groups, islands, provinces or separate is asking you to count components.
Fire a traversal from every node that no previous traversal reached. Each firing consumes exactly one component, so the number of firings is the number of components. One shared visited array does all the bookkeeping.
int countComponents(int V, vector<int> adj[]) { vector<int> vis(V, 0); // OUTSIDE the loop int count = 0; for (int i = 0; i < V; i++) { if (!vis[i]) { dfs(i, adj, vis); count++; // one firing = one component } } return count; }
def count_components(V, adj): vis = [0] * V # OUTSIDE the loop count = 0 for i in range(V): if not vis[i]: dfs(i, adj, vis) count += 1 # one firing = one component return count
Declaring vis inside the outer loop resets everything each iteration, so every node looks unvisited and the count comes back as V. The visited array must outlive the loop — that is the entire reason it exists.
Visit everything one hop from the source, then everything two hops away, then three. BFS explores in rings. That ring structure is not a side effect — it is why BFS hands you shortest paths for free on an unweighted graph.
HOW DO YOU VISIT A GRAPH IN LAYERS, OUTWARD FROM A SOURCE?
In BFS, at what moment is a node marked visited?
Mark on push. If you wait until pop, a node can sit in the queue while a second neighbour reaches it and pushes it again — the same node enters twice, gets processed twice, and on a dense graph the queue blows past O(V). Marking at push time is what makes the visited array an admission ticket rather than a receipt.
Mid-traversal the queue reads [4, 3, 5] front-to-back. You pop once and node 4 pushes nothing new. What is at the front now?
A queue is FIFO. 3 entered before 5, so 3 leaves before 5 — regardless of which node discovered them. This is the single line between BFS and DFS: swap the queue for a stack and the same code becomes depth-first.
One line here breaks the traversal. Which is it?
// BFS inner loop for (auto it : adj[node]) { if (!vis[it]) { q.push(it); vis[it] = 1; // ← moved below the push? } }
Trick question — this code is fine. Both lines run before the loop moves on, so ordering within the if-block changes nothing. The real bug is marking visited after the pop, in the outer loop — a different place entirely. Knowing which rearrangements are harmless is as useful as knowing which are fatal.
BFS is O(V + E), not O(V × E). Why is the E term additive?
Each node is popped exactly once, and popping it scans its adjacency list once. Sum those lists over every node and you have counted each undirected edge twice — 2E total, across the entire traversal, not per node. That is why the terms add. The same argument gives DFS the same bound.
Step it and watch the code line light up beside the graph. Then turn on PREDICT and call the next pop yourself before the deck shows you.
Anything about levels, layers, minimum steps or shortest path on an unweighted graph. If every edge costs the same, BFS is already the shortest-path algorithm — you do not need Dijkstra.
The queue holds the frontier: everything discovered but not yet expanded. Draining it in FIFO order means you finish distance-k nodes before you touch any distance-(k+1) node. That ordering is what makes the first time you reach a node also the shortest way to reach it.
vector<int> bfs(int V, vector<int> adj[]) { vector<int> vis(V, 0), order; queue<int> q; q.push(0); vis[0] = 1; // mark ON PUSH while (!q.empty()) { int node = q.front(); q.pop(); order.push_back(node); for (auto it : adj[node]) { if (!vis[it]) { vis[it] = 1; q.push(it); } } } return order; }
from collections import deque def bfs(V, adj): vis = [0] * V order = [] q = deque([0]) vis[0] = 1 # mark ON PUSH while q: node = q.popleft() order.append(node) for it in adj[node]: if not vis[it]: vis[it] = 1 q.append(it) return order
Mark visited on push, not on pop. Marking at pop lets a node get pushed by two different neighbours before it is ever popped — it then enters the queue twice, is processed twice, and on a dense graph the queue grows past O(V).
Go as deep as you can, and only back up when you are stuck. DFS is BFS with the queue swapped for a stack — and you rarely write that stack, because the call stack already is one. Same O(V + E), completely different shape.
HOW DO YOU WALK A GRAPH BY GOING AS DEEP AS POSSIBLE BEFORE BACKING UP?
In the recursive DFS, where does vis[node] = 1 go?
On entry. Mark it after the loop and a cycle sends you straight back into a node still marked unvisited — infinite recursion, stack overflow. The visited mark exists to say I am already handling this, which must be true the moment you arrive, not once you leave.
On the deck's graph, DFS from node 1 takes neighbours in ascending order: 1, 2, 4, 7 … which node is fifth?
DFS commits. At 7 it does not look sideways at 8 or upward at 5 — it takes 11 and keeps descending until the branch is exhausted. Full order: 1 2 4 7 11 12 8 5 9 10 6 3 13.
Now compare BFS on this same graph: 1 2 3 4 5 6 7 8 9 10 11 12 13 — dead in order, because the nodes are numbered level by level. Node 3 is second under BFS and twelfth under DFS. That gap is the whole difference between the two.
Why is recursive DFS risky at N = 10⁵ when BFS at the same N is fine?
A 10⁵-node path graph drives recursion 10⁵ frames deep. The call stack is typically ~1–8 MB and blows well before that; BFS's queue lives on the heap and is fine. Same complexity, different memory region — which is exactly when you rewrite DFS with an explicit stack.
The same graph, the same code mirror. Watch the stack grow on the way down and unwind on the way back — then compare the visit order against BFS.
Anything about paths, reachability, connected regions, or where you need to finish exploring one branch fully before starting another — cycle detection and topological sort are both DFS underneath.
Go deep, back up only when stuck. The recursion's call stack is the stack, which is why DFS code is so much shorter than BFS. Same O(V + E) cost, completely different visit order.
void dfs(int node, vector<int> adj[], vector<int>& vis, vector<int>& order) { vis[node] = 1; // mark ON ENTRY order.push_back(node); for (auto it : adj[node]) { if (!vis[it]) { dfs(it, adj, vis, order); } } // returning here pops the frame — the backtrack }
def dfs(node, adj, vis, order): vis[node] = 1 # mark ON ENTRY order.append(node) for it in adj[node]: if not vis[it]: dfs(it, adj, vis, order) # returning here pops the frame - the backtrack
At V = 10⁵ a path-shaped graph drives recursion 10⁵ frames deep and overflows the call stack, while BFS at the same size is fine because its queue lives on the heap. Same complexity, different memory region — that is when you rewrite DFS with an explicit stack.
The first real sheet problem, and it is unit 03 with a counter bolted on. A province is a connected component. The only genuinely new thing is the input format: you are handed an adjacency matrix, not a list.
HOW MANY SEPARATE PIECES IS THIS GRAPH IN?
What exactly does the province counter count?
Each time the outer loop finds a still-unvisited node, that node belongs to a component nothing has reached yet — so you fire a traversal and add one. The count of traversals is the count of components. This is the same skeleton you will reuse for Number of Islands.
N = 3 and isConnected = [[1,1,0],[1,1,0],[0,0,1]]. How many provinces?
Nodes 0 and 1 are joined; node 2 is alone. That is two provinces. The diagonal 1s are self-loops and carry no information — reading them as real edges is the usual way people talk themselves into answering 3.
At N ≤ 200, why is scanning the matrix row directly acceptable instead of building an adjacency list?
N² at N = 200 is 40,000 — nothing. Read the constraint first and the representation question answers itself. At N = 10⁵ the same code would be 10¹⁰ and you would have no choice but to convert.
Provinces, groups, circles of friends — plus the input arrives as an N × N matrix rather than an edge list. That matrix shape is the giveaway.
A province is just a connected component wearing a different word. Run the component-counting skeleton; the only adjustment is that neighbours come from scanning row i of the matrix instead of reading a list.
int findCircleNum(vector<vector<int>>& isConnected) { int n = isConnected.size(), count = 0; vector<int> vis(n, 0); for (int i = 0; i < n; i++) { if (!vis[i]) { dfs(i, isConnected, vis); count++; } } return count; } void dfs(int node, vector<vector<int>>& m, vector<int>& vis) { vis[node] = 1; for (int j = 0; j < m.size(); j++) { if (m[node][j] && !vis[j]) dfs(j, m, vis); } }
def findCircleNum(isConnected): n = len(isConnected) vis = [0] * n count = 0 for i in range(n): if not vis[i]: dfs(i, isConnected, vis) count += 1 return count def dfs(node, m, vis): vis[node] = 1 for j in range(len(m)): if m[node][j] and not vis[j]: dfs(j, m, vis)
The diagonal is always 1 — every node is trivially connected to itself. That is not an edge and carries no information; reading it as one is how a 2-province answer becomes 3.
The walkthrough for #06 Number of Provinces. Watch it, then go straight back and write it yourself.
Nobody hands you an adjacency list here — just a grid of characters. The grid is the graph. Every cell is a node, and its four neighbours are its edges. Once you see that, half the matrix problems on this sheet collapse into traversals you already know.
WHAT IF NOBODY GIVES YOU A GRAPH — JUST A GRID?
How many nodes and roughly how many edges does an m × n grid graph have?
One node per cell gives mn nodes. Each cell has up to 4 neighbours, so counting each edge once gives just under 2mn. That is why grid BFS is O(m×n) — V + E with both terms proportional to mn.
This neighbour check has a fatal ordering problem. Where?
int nr = r + dr[k], nc = c + dc[k]; if (!vis[nr][nc] && grid[nr][nc] == '1') { if (nr >= 0 && nr < m && nc >= 0 && nc < n) { // ... visit } }
You read vis[nr][nc] before confirming nr and nc are in range. At the grid's edge that reads memory you do not own — sometimes a crash, often silently wrong, and it will pass the sample case. Bounds first, always.
A 3×3 grid is 1 0 1 / 0 0 0 / 1 0 1. How many islands, 4-directionally?
Each corner 1 is isolated — diagonals do not connect in 4-directional movement, so nothing links them. Four islands. Switch to 8-directional and the same grid gives 4 still, since the centre is 0; but on a diagonal line of 1s the two conventions diverge sharply.
Why does grid traversal usually skip building an explicit adj[] structure?
(r±1, c) and (r, c±1) gives you every neighbour arithmetically. Materialising an adjacency list would cost O(mn) extra memory to store what a two-line delta array already computes. The grid is its own adjacency structure.
A grid of characters and a question about connected regions. No adjacency list is given and none is needed — the grid already encodes every edge.
Treat each cell as a node whose neighbours are the four cells around it. Then this is exactly component counting from unit 03, with the outer loop running over cells instead of nodes. Sinking each island as you find it makes the grid its own visited array.
int numIslands(vector<vector<char>>& grid) { int m = grid.size(), n = grid[0].size(), count = 0; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (grid[i][j] == '1') { sink(grid, i, j); count++; } return count; } void sink(vector<vector<char>>& g, int r, int c) { // bounds FIRST, then the value test if (r < 0 || r >= g.size() || c < 0 || c >= g[0].size()) return; if (g[r][c] != '1') return; g[r][c] = '0'; // repaint = visited sink(g, r+1, c); sink(g, r-1, c); sink(g, r, c+1); sink(g, r, c-1); }
def numIslands(grid): m, n = len(grid), len(grid[0]) count = 0 for i in range(m): for j in range(n): if grid[i][j] == '1': sink(grid, i, j) count += 1 return count def sink(g, r, c): # bounds FIRST, then the value test if r < 0 or r >= len(g) or c < 0 or c >= len(g[0]): return if g[r][c] != '1': return g[r][c] = '0' # repaint = visited sink(g, r + 1, c); sink(g, r - 1, c) sink(g, r, c + 1); sink(g, r, c - 1)
Bounds check before the grid access, never after. Writing if (!vis[nr][nc] && inRange(nr,nc)) reads out of bounds first — it often will not crash, it will just read garbage and pass your sample case.
The walkthrough for #07 Number of Islands. Watch it, then go straight back and write it yourself.
The paint-bucket tool, and it is DFS with one twist: the match condition is the starting colour, not a fixed value. Repainting doubles as the visited mark, which is why this one often needs no separate visited array at all.
HOW DOES A PAINT BUCKET TOOL ACTUALLY WORK?
Why must you capture the starting colour into a variable before recursing?
The moment you paint the source, image[sr][sc] holds the new colour. Every later comparison against it would then match nothing, and the fill would stop after one cell. Read the old colour once, up front.
One input hangs this solution forever. Which?
If new equals old, repainting changes nothing, so the cell still matches on the next visit and you bounce between neighbours until the stack dies. The one-line fix is if (oldColor == newColor) return image; at the top. The repaint-as-visited-mark trick only works if the repaint is actually visible.
Flood Fill and Number of Islands are nearly the same code. What is the real difference?
Same traversal, different driver. Islands wraps it in the component loop and counts firings; Flood Fill is handed its source and fires once. Recognising that the inner traversal is identical is exactly the pattern-transfer these problems are testing.
A starting cell plus a rule about spreading to same-valued neighbours. The match condition is relative to the source, not a fixed constant.
Identical traversal to Number of Islands, different driver: you are handed the source instead of searching for one, and you fire exactly once. Repainting doubles as the visited mark, so no separate array is needed.
vector<vector<int>> floodFill(vector<vector<int>>& img, int sr, int sc, int color) { int old = img[sr][sc]; if (old == color) return img; // ← the guard fill(img, sr, sc, old, color); return img; } void fill(vector<vector<int>>& g, int r, int c, int old, int nw) { if (r < 0 || r >= g.size() || c < 0 || c >= g[0].size()) return; if (g[r][c] != old) return; g[r][c] = nw; fill(g,r+1,c,old,nw); fill(g,r-1,c,old,nw); fill(g,r,c+1,old,nw); fill(g,r,c-1,old,nw); }
def floodFill(img, sr, sc, color): old = img[sr][sc] if old == color: return img # the guard fill(img, sr, sc, old, color) return img def fill(g, r, c, old, nw): if r < 0 or r >= len(g) or c < 0 or c >= len(g[0]): return if g[r][c] != old: return g[r][c] = nw fill(g, r + 1, c, old, nw); fill(g, r - 1, c, old, nw) fill(g, r, c + 1, old, nw); fill(g, r, c - 1, old, nw)
If newColor == oldColor the repaint changes nothing, so every cell still matches on revisit and you recurse until the stack dies. One line at the top fixes it — and this is the case that hangs rather than fails loudly.
The walkthrough for #08 Flood Fill Algorithm. Watch it, then go straight back and write it yourself.
Everything rots at once, not one orange at a time. The trick is one line: push every source into the queue before the first pop. Then a BFS level is a unit of time, and the answer is just how many levels you ran.
WHAT IF THE SPREAD STARTS FROM MANY PLACES AT ONCE?
What makes a BFS 'multi-source'?
All sources go in at level 0, so they expand in lockstep. Running a separate BFS per source and taking minimums gives the same answer but costs O(sources × mn) instead of O(mn) — on a grid that is mostly rotten, that is the difference between passing and timing out.
Queue holds 3 rotten oranges at time 0. After processing exactly those three and pushing their fresh neighbours, what time is it?
Time advances per level, not per pop. Those three were all level 0; draining them completes one round of spreading, so it is now minute 1. Incrementing time inside the pop loop instead of around it is the single most common wrong answer on this problem.
A solution returns 4 on a grid where one fresh orange is walled off. What did it forget?
BFS happily terminates having reached everything it can reach. An unreachable fresh orange is invisible to it. You must count fresh up front, decrement on each rot, and check the counter is zero before returning the time — otherwise you answer for a subset of the grid.
Which other sheet problem is the same multi-source technique?
01 Matrix is this exact shape: seed the queue with every zero cell, BFS outward, and each level is a distance. Seeing Rotten Oranges and 01 Matrix as one technique instead of two problems is the whole reason they sit next to each other on the sheet.
Something spreads from several places simultaneously and you are asked for elapsed time. Minutes, rounds or steps until everything is covered means multi-source BFS.
Seed the queue with every rotten orange before the first pop, and they all expand in lockstep. One BFS level is one minute. Count fresh oranges up front so you can tell the difference between finished and stuck.
int orangesRotting(vector<vector<int>>& g) { int m = g.size(), n = g[0].size(), fresh = 0, time = 0; queue<pair<int,int>> q; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { if (g[i][j] == 2) q.push({i, j}); // ALL sources first if (g[i][j] == 1) fresh++; } int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1}; while (!q.empty() && fresh) { int sz = q.size(); // one level = one minute while (sz--) { auto [r, c] = q.front(); q.pop(); for (int d = 0; d < 4; d++) { int nr = r+dr[d], nc = c+dc[d]; if (nr<0||nr>=m||nc<0||nc>=n||g[nr][nc]!=1) continue; g[nr][nc] = 2; fresh--; q.push({nr, nc}); } } time++; } return fresh ? -1 : time; }
from collections import deque def orangesRotting(g): m, n = len(g), len(g[0]) fresh, time = 0, 0 q = deque() for i in range(m): for j in range(n): if g[i][j] == 2: q.append((i, j)) # ALL sources first if g[i][j] == 1: fresh += 1 dirs = ((-1, 0), (1, 0), (0, -1), (0, 1)) while q and fresh: for _ in range(len(q)): # one level = one minute r, c = q.popleft() for dr, dc in dirs: nr, nc = r + dr, c + dc if nr < 0 or nr >= m or nc < 0 or nc >= n: continue if g[nr][nc] != 1: continue g[nr][nc] = 2 fresh -= 1 q.append((nr, nc)) time += 1 return -1 if fresh else time
Increment time per level, not per pop, and check for leftover fresh oranges at the end. A walled-off orange is invisible to BFS — without the fresh counter you confidently return a time for a grid that never fully rots.
The walkthrough for #09 Rotten Oranges. Watch it, then go straight back and write it yourself.
You are walking, you meet a node you have already seen — and it is not the one you just came from. That is a cycle. The parent check is the entire algorithm, and forgetting it makes every single edge look like a loop.
HOW DO YOU KNOW A GRAPH LOOPS BACK ON ITSELF?
What is the exact condition that reports a cycle in an undirected graph?
In an undirected graph every edge is stored both ways, so from node v you always see your parent u sitting there visited. Treating that as a cycle reports one on a plain two-node edge. Visited AND not the parent is the real condition.
Nodes 1–2–3 in a line, DFS from 1. At node 2 you look at neighbour 1, which is visited. Cycle?
1 is exactly where you came from. Skip it and carry on to 3. If you report a cycle here you would report one on every edge of every tree — which is the bug the parent parameter exists to prevent.
A cycle checker returns false on a graph that clearly contains a cycle. What is most likely wrong?
Same trap as unit 03, wearing a different hat. One traversal reaches one component. If the cycle lives in a piece you never started from, you never see it. Every cycle-detection solution on this sheet is wrapped in the loop over all nodes.
Why does this parent trick fail on a directed graph?
In a directed graph you can legitimately reach an already-finished node without any cycle — a diamond does this. What matters is whether the node is still on the current recursion path, which is why unit 15 introduces a second pathVis array. Same question, genuinely different machinery.
Same canvas, same code mirror, new rule. Watch the parent get skipped harmlessly — then watch the edge that isn't a parent turn the whole thing red.
Does this graph contain a cycle? on an undirected graph. Also hiding inside is this a tree? — a tree is a connected acyclic graph.
Walk outward carrying each node's parent. Meeting a visited node is normal — it is usually just the parent you came from. Meeting a visited node that is not your parent means two different paths reached it, which is a cycle.
bool bfsCycle(int src, vector<int> adj[], vector<int>& vis) { vis[src] = 1; queue<pair<int,int>> q; // {node, parent} q.push({src, -1}); while (!q.empty()) { auto [node, parent] = q.front(); q.pop(); for (auto it : adj[node]) { if (!vis[it]) { vis[it] = 1; q.push({it, node}); } else if (it != parent) return true; } } return false; } // caller: for (i) if (!vis[i] && bfsCycle(i,...)) return true;
from collections import deque def bfs_cycle(src, adj, vis): vis[src] = 1 q = deque([(src, -1)]) # (node, parent) while q: node, parent = q.popleft() for it in adj[node]: if not vis[it]: vis[it] = 1 q.append((it, node)) elif it != parent: return True return False # caller: any(not vis[i] and bfs_cycle(i, adj, vis) for i in range(V))
Run it from every unvisited node, not just node 0. A cycle sitting in a second disconnected component is completely invisible to a single traversal, and this returns a confident false.
Same question as #10, and the recursive shape is usually shorter to write under time pressure. Reach for DFS unless V is large enough to threaten the call stack.
Identical rule — visited and not my parent — but the parent rides along as a function argument instead of inside a queue. The whole difference between #10 and #11 is where the parent is stored.
bool dfsCycle(int node, int parent, vector<int> adj[], vector<int>& vis) { vis[node] = 1; for (auto it : adj[node]) { if (!vis[it]) { // MUST propagate — not just call it if (dfsCycle(it, node, adj, vis)) return true; } else if (it != parent) { return true; } } return false; }
def dfs_cycle(node, parent, adj, vis): vis[node] = 1 for it in adj[node]: if not vis[it]: # MUST propagate - not just call it if dfs_cycle(it, node, adj, vis): return True elif it != parent: return True return False
You must propagate the recursive result. Writing dfs(it, node, ...) and ignoring what it returns discards the discovery entirely and the function always answers false — a bug that reads as perfectly sensible code.
Distance to the nearest X, for every single cell. The naive read is one BFS per cell; the right read is one BFS from every X at once. Unit 09's technique, pointed at a different question.
HOW DO YOU FIND EVERY CELL'S DISTANCE TO THE NEAREST TARGET, ALL AT ONCE?
Reverse the obvious approach. What should you BFS *from*?
BFS from each 1 costs O((mn)²) — one traversal per cell. BFS from all zeros at once answers every cell in a single O(mn) pass, because the first time the wave reaches a cell is by definition its nearest zero. Reversing the direction of the search is the whole trick.
A cell is first reached on the third BFS level. What is its answer?
Level is distance in an unweighted BFS. Third level means three steps from the nearest source, so the answer is 3 — and it does not matter which zero got there, because they all expanded in lockstep and the first arrival is necessarily the closest.
A solution initialises dist[][] to 0 everywhere and returns wrong answers. Why?
If everything starts at 0 you cannot tell distance zero from not yet reached, so the visited test never fires and cells get overwritten by later, longer paths. Use −1 or INT_MAX as the sentinel and only write a cell once.
Distance to the nearest 0 for every cell. Whenever a problem asks for a distance from all cells to a set of targets, reverse it and BFS outward from the targets.
One BFS per 1 is O((mn)²). Seed the queue with every 0 at once and a single pass answers the whole grid, because the first wave to reach a cell came from its nearest zero by construction.
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) { int m = mat.size(), n = mat[0].size(); vector<vector<int>> dist(m, vector<int>(n, -1)); queue<pair<int,int>> q; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (mat[i][j] == 0) { dist[i][j] = 0; q.push({i, j}); } int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1}; while (!q.empty()) { auto [r, c] = q.front(); q.pop(); for (int d = 0; d < 4; d++) { int nr = r+dr[d], nc = c+dc[d]; if (nr<0||nr>=m||nc<0||nc>=n) continue; if (dist[nr][nc] != -1) continue; // already answered dist[nr][nc] = dist[r][c] + 1; q.push({nr, nc}); } } return dist; }
from collections import deque def updateMatrix(mat): m, n = len(mat), len(mat[0]) dist = [[-1] * n for _ in range(m)] q = deque() for i in range(m): for j in range(n): if mat[i][j] == 0: dist[i][j] = 0 q.append((i, j)) dirs = ((-1, 0), (1, 0), (0, -1), (0, 1)) while q: r, c = q.popleft() for dr, dc in dirs: nr, nc = r + dr, c + dc if nr < 0 or nr >= m or nc < 0 or nc >= n: continue if dist[nr][nc] != -1: continue # already answered dist[nr][nc] = dist[r][c] + 1 q.append((nr, nc)) return dist
Initialise distances to −1, not 0. With 0 you cannot separate distance zero from not yet reached, the visited test never fires, and cells get overwritten by longer paths arriving later.
The walkthrough for #12 Distance of Nearest Cell Having 1. Watch it, then go straight back and write it yourself.
Some regions are safe because they touch the border; everything else is trapped. The move is to invert the question — instead of hunting for surrounded regions, mark everything reachable from the boundary and let the rest fall out.
HOW DO YOU FIND THE REGIONS THAT DON'T TOUCH THE EDGE?
Why start the traversal from the border rather than from each interior region?
Deciding is this region surrounded? from the inside means exploring the whole region and proving no cell escapes. Starting from the border computes the complement in one pass — mark the safe ones, and surrounded is simply everything you did not mark.
A 4×4 grid of all O's. After the boundary pass, how many O's remain unmarked?
The four interior cells each touch a border cell, so the flood reaches everything. Zero get flipped. A region only counts as surrounded if no cell in it can walk to an edge — connectivity is what matters, not position.
A solution flips cells to 'X' during the boundary traversal itself. What breaks?
The boundary traversal is finding the cells that must survive. Flipping them is exactly backwards. Mark them with a placeholder like '#', then in a final sweep turn every remaining 'O' into 'X' and every '#' back into 'O'.
Number of Enclaves uses this identical boundary pass. What is the only real difference?
Same seed, same traversal, different final step: Surrounded Regions flips what it did not reach, Enclaves counts it. Two sheet problems, one technique — which is why the deck shows the second as a diff of the first.
A region is safe only if it touches the boundary. Any problem phrased as surrounded, trapped or cannot escape is asking you to seed from the border.
Do not hunt for surrounded regions. Invert it: flood from every border 'O', mark everything you reach as safe, and whatever is still 'O' at the end was by definition unreachable from the edge.
void solve(vector<vector<char>>& b) { int m = b.size(), n = b[0].size(); // 1. seed from the border only for (int i = 0; i < m; i++) { if (b[i][0] == 'O') mark(b, i, 0); if (b[i][n-1] == 'O') mark(b, i, n-1); } for (int j = 0; j < n; j++) { if (b[0][j] == 'O') mark(b, 0, j); if (b[m-1][j] == 'O') mark(b, m-1, j); } // 2. everything still 'O' was unreachable → flip it for (auto& row : b) for (auto& ch : row) ch = (ch == '#') ? 'O' : 'X'; } void mark(vector<vector<char>>& b, int r, int c) { if (r<0||r>=b.size()||c<0||c>=b[0].size()||b[r][c]!='O') return; b[r][c] = '#'; // safe, not flipped mark(b,r+1,c); mark(b,r-1,c); mark(b,r,c+1); mark(b,r,c-1); }
def solve(b): m, n = len(b), len(b[0]) # 1. seed from the border only for i in range(m): if b[i][0] == 'O': mark(b, i, 0) if b[i][n - 1] == 'O': mark(b, i, n - 1) for j in range(n): if b[0][j] == 'O': mark(b, 0, j) if b[m - 1][j] == 'O': mark(b, m - 1, j) # 2. everything still 'O' was unreachable -> flip it for i in range(m): for j in range(n): b[i][j] = 'O' if b[i][j] == '#' else 'X' def mark(b, r, c): if r < 0 or r >= len(b) or c < 0 or c >= len(b[0]): return if b[r][c] != 'O': return b[r][c] = '#' # safe, not flipped mark(b, r + 1, c); mark(b, r - 1, c) mark(b, r, c + 1); mark(b, r, c - 1)
Do not flip cells during the boundary traversal — that traversal is finding the ones that must survive. Mark them with a placeholder and flip the others afterwards, or you invert the answer perfectly.
The walkthrough for #13 Surrounded Regions. Watch it, then go straight back and write it yourself.
Land cells from which you cannot walk off the grid. Identical shape to #13 — seed from the boundary — with the last step swapped from flipping to counting.
Flood from every border land cell and sink everything reachable. Whatever land survives is enclaved, so the answer is simply the count of remaining 1s.
// Δ FROM #13 — same boundary flood, different ending int numEnclaves(vector<vector<int>>& g) { int m = g.size(), n = g[0].size(); for (int i = 0; i < m; i++) { sink(g, i, 0); sink(g, i, n-1); } for (int j = 0; j < n; j++) { sink(g, 0, j); sink(g, m-1, j); } int count = 0; // ← #13 flips here; we COUNT for (auto& row : g) for (int v : row) count += v; return count; } void sink(vector<vector<int>>& g, int r, int c) { if (r<0||r>=g.size()||c<0||c>=g[0].size()||g[r][c]!=1) return; g[r][c] = 0; sink(g,r+1,c); sink(g,r-1,c); sink(g,r,c+1); sink(g,r,c-1); }
# delta FROM #13 - same boundary flood, different ending def numEnclaves(g): m, n = len(g), len(g[0]) for i in range(m): sink(g, i, 0); sink(g, i, n - 1) for j in range(n): sink(g, 0, j); sink(g, m - 1, j) # #13 flips here; we COUNT return sum(sum(row) for row in g) def sink(g, r, c): if r < 0 or r >= len(g) or c < 0 or c >= len(g[0]): return if g[r][c] != 1: return g[r][c] = 0 sink(g, r + 1, c); sink(g, r - 1, c) sink(g, r, c + 1); sink(g, r, c - 1)
A single land cell sitting on the border is not an enclave, even though it looks isolated — it is already off the grid. Seed from every border cell, not just from border regions that look large.
The walkthrough for #14 Number of Enclaves. Watch it, then go straight back and write it yourself.
Counting islands is unit 07. Counting distinct shapes needs one more idea: turn each island into a signature that is independent of where it sits on the grid, then drop the signatures into a set.
HOW DO YOU TELL TWO ISLANDS APART BY SHAPE, NOT POSITION?
What makes two islands 'the same' in this problem?
Translation only — no rotation, no reflection. So the signature must survive a shift but nothing else, which is exactly what subtracting the base cell achieves. Equal cell counts is far too weak: an L-shape and a line of 3 both have three cells.
A solution stores absolute (row, col) pairs as the signature. What goes wrong?
An island at rows 0–1 and the same shape at rows 5–6 share no coordinates at all. Every island then looks unique and the answer equals the plain island count. Subtract the base cell from every coordinate so both collapse to the same relative form.
Why must the traversal visit neighbours in a fixed order?
If you store the cells as an ordered vector, the order is part of the signature. Two identical shapes explored in different neighbour orders hash differently and get double-counted. Fix the direction order once and use it everywhere — or sort the signature before storing.
The word distinct next to a shape-counting question. You are no longer counting regions, you are deduplicating them by form.
Traverse each island as usual, but record every cell's position relative to the island's first cell. That normalised list is a shape signature independent of position — drop them all in a set and take its size.
int countDistinctIslands(vector<vector<int>>& g) { int m = g.size(), n = g[0].size(); vector<vector<int>> vis(m, vector<int>(n, 0)); set<vector<pair<int,int>>> shapes; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (g[i][j] && !vis[i][j]) { vector<pair<int,int>> shape; dfs(g, vis, i, j, i, j, shape); // pass the BASE cell shapes.insert(shape); } return shapes.size(); } void dfs(vector<vector<int>>& g, vector<vector<int>>& vis, int r, int c, int br, int bc, vector<pair<int,int>>& shape) { if (r<0||r>=g.size()||c<0||c>=g[0].size()) return; if (!g[r][c] || vis[r][c]) return; vis[r][c] = 1; shape.push_back({r - br, c - bc}); // ← RELATIVE, not absolute dfs(g,vis,r+1,c,br,bc,shape); dfs(g,vis,r-1,c,br,bc,shape); dfs(g,vis,r,c+1,br,bc,shape); dfs(g,vis,r,c-1,br,bc,shape); }
def countDistinctIslands(g): m, n = len(g), len(g[0]) vis = [[0] * n for _ in range(m)] shapes = set() for i in range(m): for j in range(n): if g[i][j] and not vis[i][j]: shape = [] dfs(g, vis, i, j, i, j, shape) # pass the BASE cell shapes.add(tuple(shape)) return len(shapes) def dfs(g, vis, r, c, br, bc, shape): if r < 0 or r >= len(g) or c < 0 or c >= len(g[0]): return if not g[r][c] or vis[r][c]: return vis[r][c] = 1 shape.append((r - br, c - bc)) # RELATIVE, not absolute dfs(g, vis, r + 1, c, br, bc, shape); dfs(g, vis, r - 1, c, br, bc, shape) dfs(g, vis, r, c + 1, br, bc, shape); dfs(g, vis, r, c - 1, br, bc, shape)
Storing absolute coordinates makes every island unique and the answer collapses to the plain island count. Subtract the base cell — and keep the neighbour order fixed, since the signature is a sequence and order is part of it.
The walkthrough for #15 Number of Distinct Islands. Watch it, then go straight back and write it yourself.
Can you split the nodes into two teams so that no edge stays inside a team? Colour as you traverse, always the opposite of where you came from. The only thing that can defeat you is an odd-length cycle.
CAN THIS GRAPH BE SPLIT INTO TWO GROUPS WITH NO EDGE INSIDE EITHER?
What exactly proves a graph is NOT bipartite?
Even cycles colour perfectly — alternate around and it closes cleanly. It is the odd cycle that fails, and it surfaces as an edge whose two ends already carry the same colour. Any cycle is far too broad a test.
A triangle: nodes 1-2, 2-3, 3-1. Colour 1 as A. What happens?
A triangle is the smallest odd cycle. Walking round gives A, B, A — then the closing edge 3–1 puts two A's together. Any odd cycle forces this collision once you go all the way round, which is precisely why odd cycles and non-bipartiteness are the same statement.
A solution initialises the colour array to 0 and treats 0 as 'uncoloured'. What breaks?
0 is one of the two real colours. Using it as the sentinel means a node coloured 0 is indistinguishable from an untouched one — the clash test never fires and every graph reports bipartite. Use −1 for uncoloured.
The graph is disconnected. What must you remember?
The same outer loop as always. A graph is bipartite only if every component is, so an odd cycle hiding in a component you never started from returns a confident, wrong 'true'.
Two sets, gold and ink. Every neighbour takes the opposite colour; a clash would mean an odd cycle.
Two groups, two teams, no two adjacent items together. Any question about splitting nodes in half so that every edge crosses the divide.
Colour the source, then give every neighbour the opposite colour and keep going. If you ever meet a neighbour already wearing your own colour, the graph contains an odd cycle and no valid split exists.
bool isBipartite(vector<vector<int>>& adj) { int n = adj.size(); vector<int> color(n, -1); // −1 = uncoloured for (int i = 0; i < n; i++) { if (color[i] != -1) continue; // every component queue<int> q; color[i] = 0; q.push(i); while (!q.empty()) { int node = q.front(); q.pop(); for (int it : adj[node]) { if (color[it] == -1) { color[it] = 1 - color[node]; q.push(it); } else if (color[it] == color[node]) return false; } } } return true; }
from collections import deque def isBipartite(adj): n = len(adj) color = [-1] * n # -1 = uncoloured for i in range(n): if color[i] != -1: continue # every component color[i] = 0 q = deque([i]) while q: node = q.popleft() for it in adj[node]: if color[it] == -1: color[it] = 1 - color[node] q.append(it) elif color[it] == color[node]: return False return True
Use −1 for uncoloured, never 0 — 0 is one of the two real colours, and using it as the sentinel means the clash test never fires and every graph reports bipartite. Then remember to run it on every component.
The walkthrough for #16 Bipartite Graph. Watch it, then go straight back and write it yourself.
The parent trick from unit 10 does not work here. In a directed graph you can legitimately reach an already-visited node without any cycle. What matters is whether that node is still on the path you are currently walking.
WHY ISN'T THE PARENT CHECK ENOUGH ONCE EDGES HAVE DIRECTION?
What is the cycle condition in a directed graph?
Visited and still on the path. Plain 'visited' catches harmless revisits of finished branches; the parent check is meaningless once edges have direction. Only a node still sitting on your current path means you have walked in a circle.
Edges 1→2, 1→3, 2→4, 3→4. DFS from 1 reaches 4 twice. Is there a cycle?
This is the diamond, and it is acyclic. When the 3→4 branch runs, node 4 is already finished and its pathVis is back to 0. This is exactly the case that makes a plain visited check report a cycle that does not exist.
A solution sets pathVis[node] = 1 but never unsets it. What happens?
pathVis is meant to describe the current path only. Never unsetting it makes it a duplicate of vis[], and the diamond above immediately reports a false cycle. pathVis[node] = 0 just before returning is the line that makes the whole thing work.
Which later problems rest on directed cycle detection?
A topological order exists if and only if the directed graph is acyclic, so Course Schedule is literally 'is there a cycle in the prerequisite graph?'. This unit is the foundation the entire topo section is built on.
Directed edges plus a cycle question — or anything about prerequisites, dependencies or build order, all of which are cycle questions wearing a costume.
Plain 'visited' is not enough: reaching a finished node is harmless. You need a second array saying this node is on the path I am walking right now. Visited AND on the current path means you have looped.
bool dfs(int node, vector<int> adj[], vector<int>& vis, vector<int>& pathVis) { vis[node] = 1; pathVis[node] = 1; // now ON the current path for (auto it : adj[node]) { if (!vis[it]) { if (dfs(it, adj, vis, pathVis)) return true; } else if (pathVis[it]) { return true; // visited AND still on path → cycle } } pathVis[node] = 0; // ← leaving: off the path again return false; }
def dfs(node, adj, vis, path_vis): vis[node] = 1 path_vis[node] = 1 # now ON the current path for it in adj[node]: if not vis[it]: if dfs(it, adj, vis, path_vis): return True elif path_vis[it]: return True # visited AND on path -> cycle path_vis[node] = 0 # leaving: off the path again return False
Reset pathVis to 0 before returning. Leave it set and pathVis just duplicates vis — a plain diamond (1→2, 1→3, 2→4, 3→4) then reports a cycle that does not exist.
An ordering where every arrow points forwards. Do a DFS, and as each node finishes push it onto a stack — because a node only finishes after everything it depends on. Reverse the finish order and you have the answer.
HOW DO YOU LINE UP TASKS SO EVERY PREREQUISITE COMES FIRST?
In the DFS version, when is a node pushed onto the stack?
On the way out. A node finishes only once everything reachable from it has finished, so it belongs before all of them in the final order. The stack reverses the finish sequence, which turns that into exactly the topological order.
Which graphs have a topological order at all?
A cycle means A waits on B which waits on A — no ordering can satisfy both. Topological order exists if and only if the graph is a DAG, which is why 'does a valid order exist?' and 'is there a cycle?' are the same question, and why Course Schedule is solvable this way.
Edges 1→2, 1→3, 3→2. Which of these is a valid topological order?
1 must precede both; 3 must precede 2. 1, 3, 2 satisfies every arrow. Note 1, 2, 3 would fail on the 3→2 edge — a common slip when people order by node number instead of by dependency.
A directed acyclic graph plus any word about ordering, scheduling, dependencies or build sequence.
DFS, and push each node onto a stack as it finishes. A node finishes only after everything it points to has finished, so it belongs before all of them — and the stack hands that back reversed, which is the order.
vector<int> topoSort(int V, vector<int> adj[]) { vector<int> vis(V, 0); stack<int> st; for (int i = 0; i < V; i++) if (!vis[i]) dfs(i, adj, vis, st); vector<int> order; while (!st.empty()) { order.push_back(st.top()); st.pop(); } return order; } void dfs(int node, vector<int> adj[], vector<int>& vis, stack<int>& st) { vis[node] = 1; for (auto it : adj[node]) if (!vis[it]) dfs(it, adj, vis, st); st.push(node); // ← ON THE WAY OUT }
def topoSort(V, adj): vis = [0] * V st = [] for i in range(V): if not vis[i]: dfs(i, adj, vis, st) return st[::-1] def dfs(node, adj, vis, st): vis[node] = 1 for it in adj[node]: if not vis[it]: dfs(it, adj, vis, st) st.append(node) # ON THE WAY OUT
Push after the neighbour loop, not before. Pushing on entry gives discovery order, which is not a topological order and will pass a linear-chain test case while failing anything that branches.
The BFS answer to the same question, and often the more useful one. Count how many arrows point at each node; anything at zero has no unmet prerequisites and can go now. Remove it, decrement its targets, repeat.
HOW DO YOU BUILD A TOPOLOGICAL ORDER WITHOUT RECURSION — AND DETECT CYCLES FOR FREE?
Which nodes start in the queue?
Indegree 0 means nothing has to happen first, so those are exactly the tasks you can start immediately. Seeding only node 0 breaks the moment node 0 has a prerequisite, and there is usually more than one valid starting point.
When exactly is a neighbour pushed?
Decrementing to 2 means two prerequisites remain — pushing then would place the task before its dependencies. Push only on hitting zero, which also guarantees each node is pushed exactly once.
Kahn's finishes with only 5 of 8 nodes in the order. What does that mean?
Nodes on a cycle each wait on another node in that cycle, so their indegrees never fall to zero and they are never pushed. order.size() < V is a complete cycle test — no extra bookkeeping, which is why Kahn's is usually the cleaner answer for Course Schedule.
A solution builds indegrees by counting adj[i].size() for each i. What is wrong?
adj[i].size() is how many arrows leave i. Indegree is how many arrive, which means iterating every list and incrementing the target. Confusing the two inverts the algorithm and it produces a reverse-ish order that passes small tests.
Same eight nodes, now directed low→high so the graph is a DAG. The row below is live indegree; gold means zero and ready.
Same DAG-ordering question as #18, but you also want cycle detection for free or you would rather avoid recursion depth entirely.
Count arrows arriving at each node. Anything at zero is ready now — emit it, remove its outgoing edges, and anything that drops to zero becomes ready. Peel the graph layer by layer.
vector<int> topoSort(int V, vector<int> adj[]) { vector<int> indeg(V, 0); for (int i = 0; i < V; i++) for (auto it : adj[i]) indeg[it]++; // arrivals! queue<int> q; for (int i = 0; i < V; i++) if (indeg[i] == 0) q.push(i); vector<int> order; while (!q.empty()) { int node = q.front(); q.pop(); order.push_back(node); for (auto it : adj[node]) if (--indeg[it] == 0) q.push(it); // only at zero } return order; // order.size() < V → cycle }
from collections import deque def topoSort(V, adj): indeg = [0] * V for i in range(V): for it in adj[i]: indeg[it] += 1 # arrivals! q = deque(i for i in range(V) if indeg[i] == 0) order = [] while q: node = q.popleft() order.append(node) for it in adj[node]: indeg[it] -= 1 if indeg[it] == 0: q.append(it) # only at zero return order # len(order) < V -> cycle
Indegree counts arrows arriving. Using adj[i].size() measures out-degree instead and inverts the whole algorithm — it still produces an order-shaped array, so it passes small symmetric tests.
Detect a cycle in a directed graph, when you would rather not manage two recursion arrays. Kahn's gives it away as a byproduct.
Run Kahn's and count what comes out. Nodes on a cycle each wait on another node in that cycle, so their indegrees never fall to zero and they are never emitted. A short order means a cycle.
// Δ FROM #19 — same Kahn's, one extra counter bool isCyclic(int V, vector<int> adj[]) { vector<int> indeg(V, 0); for (int i = 0; i < V; i++) for (auto it : adj[i]) indeg[it]++; queue<int> q; for (int i = 0; i < V; i++) if (indeg[i] == 0) q.push(i); int placed = 0; while (!q.empty()) { int node = q.front(); q.pop(); placed++; // ← count instead of collect for (auto it : adj[node]) if (--indeg[it] == 0) q.push(it); } return placed != V; // short → cycle }
# delta FROM #19 - same Kahn's, one extra counter from collections import deque def isCyclic(V, adj): indeg = [0] * V for i in range(V): for it in adj[i]: indeg[it] += 1 q = deque(i for i in range(V) if indeg[i] == 0) placed = 0 while q: node = q.popleft() placed += 1 # count instead of collect for it in adj[node]: indeg[it] -= 1 if indeg[it] == 0: q.append(it) return placed != V # short -> cycle
This is the directed test only. On an undirected graph every edge contributes indegree both ways and the count is meaningless — undirected cycles need the parent check from #10 and #11 instead.
Course Schedule is topological sort with the question rephrased. I asks whether an order exists; II asks for the order itself. Same Kahn's run — one returns a bool, the other returns the array.
CAN YOU FINISH ALL THE COURSES — AND IN WHAT ORDER?
LeetCode gives prerequisites[i] = [a, b] meaning you must take b before a. Which edge?
b must come first, so the arrow runs b → a. Getting this backwards builds the reversed graph, which is still a DAG — so it does not crash, it just silently returns a reversed order and fails on the hidden tests. Read the direction twice.
What is the actual difference between Course Schedule I and II?
One run, two return statements. I answers order.size() == V; II answers order, or an empty array when that check fails. Recognising them as one problem is worth more than solving both separately.
Course Schedule II returns a partial order on a cyclic input. What is missing?
Kahn's happily emits whatever it could place before stalling. Without the size check you hand back a partial ordering that looks plausible. Short order means cycle, and the contract says return empty.
Can you finish all the courses? Prerequisite pairs are directed edges, and the question is exactly is this graph acyclic?
Build the graph with an edge from prerequisite to course, run Kahn's, and check whether every course made it into the order. A valid schedule exists if and only if the graph is a DAG.
bool canFinish(int n, vector<vector<int>>& pre) { vector<vector<int>> adj(n); vector<int> indeg(n, 0); for (auto& p : pre) { adj[p[1]].push_back(p[0]); // b → a, NOT a → b indeg[p[0]]++; } queue<int> q; for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i); int done = 0; while (!q.empty()) { int c = q.front(); q.pop(); done++; for (int nx : adj[c]) if (--indeg[nx] == 0) q.push(nx); } return done == n; }
from collections import deque def canFinish(n, pre): adj = [[] for _ in range(n)] indeg = [0] * n for a, b in pre: adj[b].append(a) # b -> a, NOT a -> b indeg[a] += 1 q = deque(i for i in range(n) if indeg[i] == 0) done = 0 while q: c = q.popleft() done += 1 for nx in adj[c]: indeg[nx] -= 1 if indeg[nx] == 0: q.append(nx) return done == n
prerequisites[i] = [a, b] means b before a, so the edge is b → a. Building a → b gives the reversed graph, which is still acyclic — so it does not crash, it just quietly answers the wrong question.
The walkthrough for #21 Course Schedule I. Watch it, then go straight back and write it yourself.
Identical setup to #21, but the return type changes from bool to vector<int> — it wants the actual schedule.
The same Kahn's run. Collect the popped nodes instead of counting them, and if the collected order is shorter than numCourses a cycle made the schedule impossible, so return empty.
// Δ FROM #21 — collect instead of count, plus a size guard vector<int> findOrder(int n, vector<vector<int>>& pre) { vector<vector<int>> adj(n); vector<int> indeg(n, 0); for (auto& p : pre) { adj[p[1]].push_back(p[0]); indeg[p[0]]++; } queue<int> q; for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i); vector<int> order; // ← was: int done = 0 while (!q.empty()) { int c = q.front(); q.pop(); order.push_back(c); // ← was: done++ for (int nx : adj[c]) if (--indeg[nx] == 0) q.push(nx); } if (order.size() != n) return {}; // cycle → empty return order; }
# delta FROM #21 - collect instead of count, plus a size guard from collections import deque def findOrder(n, pre): adj = [[] for _ in range(n)] indeg = [0] * n for a, b in pre: adj[b].append(a) indeg[a] += 1 q = deque(i for i in range(n) if indeg[i] == 0) order = [] # was: done = 0 while q: c = q.popleft() order.append(c) # was: done += 1 for nx in adj[c]: indeg[nx] -= 1 if indeg[nx] == 0: q.append(nx) return order if len(order) == n else [] # cycle -> empty
Do not forget the final size check. Kahn's emits whatever it managed to place before stalling, so on a cyclic input you return a plausible-looking partial schedule instead of the empty array the contract demands.
The walkthrough for #22 Course Schedule II. Watch it, then go straight back and write it yourself.
A node is safe if every path out of it ends at a terminal — that is, if it can never wander into a cycle. The clean way to see it: reverse every edge and run Kahn's. Whatever gets placed is safe.
WHICH NODES CAN NEVER LEAD YOU INTO A CYCLE?
What makes a node safe?
Every path, not merely one. A node with two outgoing edges where one ends safely and the other enters a cycle is unsafe — you might take the bad branch. That universal quantifier is what makes the reverse-Kahn framing so clean.
Why reverse the edges before running Kahn's?
Kahn's peels from indegree 0, but safety propagates backwards from terminals. Reversing turns 'outdegree 0' into 'indegree 0', so the standard algorithm now peels exactly the safe nodes, in the right direction, with no modification.
A solution returns the correct safe nodes but fails the judge. Most likely cause?
Kahn's emits nodes in peel order, not numeric order. The problem explicitly asks for ascending output, so a final sort is required — a one-line omission that makes a correct algorithm fail every test.
Safe, terminal, or never gets stuck in a loop. You are being asked which nodes have no path into a cycle.
Safety spreads backwards from terminals, and Kahn's peels forwards from indegree 0. Reverse every edge and the two line up: terminals become seeds, and everything Kahn's manages to place is safe.
vector<int> eventualSafeNodes(vector<vector<int>>& graph) { int n = graph.size(); vector<vector<int>> rev(n); vector<int> indeg(n, 0); for (int u = 0; u < n; u++) for (int v : graph[u]) { rev[v].push_back(u); // REVERSE the edge indeg[u]++; // = outdegree originally } queue<int> q; for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i); // terminals vector<int> safe; while (!q.empty()) { int node = q.front(); q.pop(); safe.push_back(node); for (int nx : rev[node]) if (--indeg[nx] == 0) q.push(nx); } sort(safe.begin(), safe.end()); // ← required return safe; }
from collections import deque def eventualSafeNodes(graph): n = len(graph) rev = [[] for _ in range(n)] indeg = [0] * n for u in range(n): for v in graph[u]: rev[v].append(u) # REVERSE the edge indeg[u] += 1 # = outdegree originally q = deque(i for i in range(n) if indeg[i] == 0) # terminals safe = [] while q: node = q.popleft() safe.append(node) for nx in rev[node]: indeg[nx] -= 1 if indeg[nx] == 0: q.append(nx) return sorted(safe) # required
The judge wants the answer in ascending order, and Kahn's emits in peel order. Forgetting the final sort fails every test with a perfectly correct set of safe nodes.
The walkthrough for #23 Find Eventual Safe States. Watch it, then go straight back and write it yourself.
You are given words in a mystery alphabet's dictionary order and asked to recover the alphabet. The leap: compare adjacent words, find the first differing character, and that is one directed edge. Then topologically sort.
HOW DO YOU RECOVER AN ALPHABET FROM A SORTED WORD LIST?
Comparing 'wrt' and 'wrf', how many edges do you extract?
Sorted order only tells you about the first position where they differ; everything after it is unconstrained. So 'wrt' < 'wrf' yields t → f and nothing more. Extracting edges from later positions invents constraints that do not exist.
Input is ['abc', 'ab']. What must the code do?
In any lexicographic order the shorter prefix comes first. Seeing 'abc' before 'ab' means the input is inconsistent, and the answer is empty. This is the edge case that separates accepted from wrong answer — it produces no differing character, so a naive loop silently skips it.
After building the edges, what does a cycle in the graph mean?
A cycle says x before y before … before x, which no alphabet can satisfy. Kahn's detects it the usual way: fewer letters placed than letters present. Same cycle test as Course Schedule, different dressing.
Words given in the dictionary order of an unknown alphabet. The sortedness is the input; the alphabet is the output.
Adjacent words are the only source of information. The first position where two adjacent words differ gives exactly one ordering constraint — one directed edge. Collect them all, then topologically sort the letters.
string alienOrder(vector<string>& words) {
int K = 26;
vector<vector<int>> adj(K);
vector<int> indeg(K, 0), seen(K, 0);
for (auto& w : words)
for (char ch : w) seen[ch - 'a'] = 1;
for (int i = 0; i + 1 < words.size(); i++) {
string& a = words[i]; string& b = words[i+1];
int len = min(a.size(), b.size()), j = 0;
while (j < len && a[j] == b[j]) j++;
if (j == len) {
if (a.size() > b.size()) return ""; // prefix violation
} else {
adj[a[j]-'a'].push_back(b[j]-'a');
indeg[b[j]-'a']++;
}
}
// then standard Kahn's over the 'seen' letters;
// if fewer letters emerge than seen, a cycle exists → return ""
}def alienOrder(words): adj = {c: set() for w in words for c in w} indeg = {c: 0 for c in adj} for a, b in zip(words, words[1:]): for x, y in zip(a, b): if x != y: if y not in adj[x]: adj[x].add(y) indeg[y] += 1 break # FIRST difference only else: if len(a) > len(b): return '' # prefix violation # then standard Kahn's over the letters in `indeg`; # if fewer letters emerge than seen, a cycle exists -> return ''
['abc', 'ab'] is invalid input, not a no-op. A prefix must precede its extension, so this ordering is impossible and the answer is empty — but it produces no differing character, so a naive loop skips it and returns a confident wrong alphabet.
The walkthrough for #24 Alien Dictionary. Watch it, then go straight back and write it yourself.
There is no graph in the input at all — just words. The unlock is realising that each word is a node and a one-letter change is an edge. Once you see that, 'shortest transformation' is plain BFS.
WHAT IF THE GRAPH ISN'T GIVEN — ONLY THE RULE FOR MOVING BETWEEN STATES?
How are a word's neighbours generated?
Comparing against every word is O(N·L) per node. Generating 26 × L candidates and testing set membership is O(26·L) — independent of dictionary size. That swap is what makes the solution pass at large N.
Why erase a word from the set the moment you enqueue it?
The set doubles as the visited structure. Skip the erase and a word gets reached from several predecessors at the same level, each pushing it again — the queue balloons and the search degenerates. Same 'mark on push' rule as unit 04, wearing different clothes.
Why is plain BFS enough here, rather than Dijkstra?
Dijkstra exists for varying edge weights. When every step costs the same, BFS's level structure already yields shortest paths at lower cost. Reaching for Dijkstra on a unit-weight graph is a real interview tell.
A start state, an end state, a rule for legal moves, and the word shortest. No graph is given — you are expected to see one.
Each word is a node; two words are joined if they differ in exactly one letter. Every move costs the same, so BFS gives the shortest chain. Generate neighbours on demand rather than materialising the graph.
int ladderLength(string begin, string end, vector<string>& list) { unordered_set<string> st(list.begin(), list.end()); if (!st.count(end)) return 0; queue<string> q; q.push(begin); st.erase(begin); int steps = 1; while (!q.empty()) { int sz = q.size(); while (sz--) { string w = q.front(); q.pop(); if (w == end) return steps; for (int i = 0; i < w.size(); i++) { char orig = w[i]; for (char c = 'a'; c <= 'z'; c++) { w[i] = c; if (st.count(w)) { st.erase(w); // visited mark q.push(w); } } w[i] = orig; } } steps++; } return 0; }
from collections import deque def ladderLength(begin, end, wordList): st = set(wordList) if end not in st: return 0 q = deque([begin]) st.discard(begin) steps = 1 while q: for _ in range(len(q)): w = q.popleft() if w == end: return steps for i in range(len(w)): for c in 'abcdefghijklmnopqrstuvwxyz': nx = w[:i] + c + w[i + 1:] if nx in st: st.discard(nx) # visited mark q.append(nx) steps += 1 return 0
Erase each word from the set as you enqueue it. Skip that and the same word is pushed by every neighbour that reaches it, the queue explodes, and a correct algorithm becomes a TLE.
The walkthrough for #25 Word Ladder I. Watch it, then go straight back and write it yourself.
Word Ladder II wants every shortest chain, not merely the length. That changes the bookkeeping completely: you can no longer erase a word the instant you see it, because several equally-short paths may legitimately pass through it.
HOW DO YOU RETURN EVERY SHORTEST PATH, NOT JUST ONE?
Why can't you erase a word from the set immediately, as in Word Ladder I?
I needs one path, so first-arrival-wins is fine. II needs all of them, and a word reachable from two predecessors at the same depth lies on two distinct shortest chains. Erase it on first sight and you silently drop half the answers. Delete only after the whole level finishes.
How is the actual list of paths reconstructed?
Storing whole paths in the queue works but explodes in memory. Keeping a parent map and walking backwards from the target reconstructs every chain on demand — the same technique used to print a Dijkstra path.
Why stop BFS at the first level where the end word appears?
BFS explores in strict distance order, so the first level containing the target holds every shortest chain. Continuing deeper can only find longer ones, which do not qualify — and costs the time that turns this solution into a TLE.
Same transformation rule as #25, but it asks for all shortest sequences rather than the length. All shortest paths is a different problem.
Run the same BFS, but record every word's parents instead of erasing on sight — several shortest chains may share a node. Delete a level's words only once that whole level is done, then backtrack from the end.
// Δ FROM #25 — parents instead of a bare visited erase vector<vector<string>> findLadders(string begin, string end, vector<string>& list) { unordered_set<string> st(list.begin(), list.end()); unordered_map<string, vector<string>> parents; queue<string> q; q.push(begin); bool found = false; while (!q.empty() && !found) { int sz = q.size(); unordered_set<string> levelUsed; // erase AFTER the level while (sz--) { string w = q.front(); q.pop(); for (int i = 0; i < w.size(); i++) { string nx = w; char orig = w[i]; for (char c = 'a'; c <= 'z'; c++) { nx[i] = c; if (nx == w || !st.count(nx)) continue; if (!levelUsed.count(nx)) { levelUsed.insert(nx); q.push(nx); } parents[nx].push_back(w); // ALL parents if (nx == end) found = true; } } } for (auto& w : levelUsed) st.erase(w); } // backtrack from `end` through `parents` to emit every chain }
# delta FROM #25 - parents instead of a bare visited erase from collections import deque, defaultdict def findLadders(begin, end, wordList): st = set(wordList) parents = defaultdict(list) q = deque([begin]) found = False while q and not found: level_used = set() # erase AFTER the level for _ in range(len(q)): w = q.popleft() for i in range(len(w)): for c in 'abcdefghijklmnopqrstuvwxyz': nx = w[:i] + c + w[i + 1:] if nx == w or nx not in st: continue if nx not in level_used: level_used.add(nx) q.append(nx) parents[nx].append(w) # ALL parents if nx == end: found = True st -= level_used # backtrack from `end` through `parents` to emit every chain
Erasing per word instead of per level silently drops valid answers. A word reachable from two predecessors at the same depth lies on two distinct shortest chains; first-arrival-wins keeps only one, and the output looks plausible but is incomplete.
The walkthrough for #26 Word Ladder II. Watch it, then go straight back and write it yourself.
Every one of these produces a plausible wrong answer rather than a crash. That is what makes them expensive — the judge tells you no, and the code looks fine.
In BFS a node must be marked the moment it is pushed. Mark it on pop and the same node is enqueued once per incoming edge — the answers stay right while the queue grows toward O(E).
Undirected cycle detection skips only the parent, not every visited neighbour. Skip them all and you never detect a cycle at all; the function just returns false forever.
A directed graph needs two marks: visited ever, and on the current recursion path. Using visited alone reports a cycle for any diamond shape, which is not a cycle.
In grid problems check 0 <= r < m before reading grid[r][c]. The other order reads out of bounds — which in C++ usually does not crash, it just returns nonsense.
Multi-source BFS means pushing every source before the first pop. Push them one at a time inside the loop and you have computed distance from whichever source happened to go first.
If the statement numbers nodes 1..V, declare adj[V+1]. Declaring adj[V] and touching node V writes off the end — silently, most of the time.
This is the slide to reopen the night before — every traversal, its cost, and the sentence in the statement that selects it.
Twenty-two units, 26 sheet problems, and underneath them two traversals. If you remember one thing: decide whether the question is about layers or about reachability, and the algorithm picks itself.
Decks 2 covers Dijkstra, Bellman-Ford and Floyd-Warshall. Deck 3 — MST, disjoint set and strongly connected components — is not built yet.
This deck is a fixed 1280 × 720 stage — hand-built animated visualisers, code mirrored beside the graph, problems laid out two columns wide. It scales as one piece, so on this screen the text would land at about 4px. That is not worth shipping to you.
Your progress is saved on this device, so anything you tick on the laptop will be here too.