Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Model courses as a directed graph where an edge b → a means 'b is a prerequisite of a'. A valid order is a topological sort. The canonical answer is Kahn's algorithm (BFS): compute every node's in-degree, start a queue with the zero-in-degree nodes, and repeatedly pop a node into the output while decrementing its neighbours' in-degrees, enqueuing any that hit zero. If you output fewer than numCourses nodes, the graph has a cycle → return []. O(V + E) time. DFS post-order reversal is the equivalent alternative.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise a dependency-ordering problem as a topological sort, build the graph with the correct edge direction, and handle the cycle case by returning an empty array rather than a partial order.
Where candidates slip
Reversing the edge direction (so the order comes out backwards), forgetting that a cycle must return [], or only seeding the queue with node 0 instead of all zero-in-degree nodes.
How to stand out
Name it as topological sort immediately, explain Kahn's in-degree intuition, show that 'output size < n ⇒ cycle' is free cycle detection, and mention the DFS post-order alternative and where each is preferable.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewOrder tasks under 'X before Y' rulesNeed the order, or just feasibility?Just yes/noNeed an orderExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Kahn's Algorithm — BFS Topological Sort (Optimal)
1Hint 1Explore hintHide hint
A course can be taken once all its prerequisites are done. In graph terms, that's a node whose in-degree (number of incoming prerequisite edges) has dropped to zero.
2Hint 2Explore hintHide hint
Compute every node's in-degree, then start a queue with all zero-in-degree nodes. Pop one into the answer, and 'finish' it by decrementing each neighbour's in-degree.
3Hint 3Explore hintHide hint
When a neighbour's in-degree hits zero, all its prerequisites are scheduled — enqueue it. If you end up scheduling fewer than numCourses nodes, the leftover nodes form a cycle → return [].
A · Core idea
Kahn's algorithm builds the schedule the way a student actually would: at any moment, take any course whose prerequisites are all already behind you.
In-degree is the readiness counter. For each course we count how many prerequisites point into it — that's its in-degree. A course with in-degree 0 has nothing blocking it, so it's immediately takeable. We seed the queue with every such course, because in general there can be many independent starting points, not just course 0. (Seeding only node 0 is a classic bug that breaks the moment two courses have no prerequisites.)
Finishing a course unblocks its dependents. When we pop a course u and append it to the order, we've 'completed' it. Every course v that listed u as a prerequisite now has one fewer thing blocking it, so we decrement indegree[v]. The instant indegree[v] reaches 0, all of v's prerequisites are scheduled, so v becomes takeable and we enqueue it. This ripple is what propagates the ordering outward from the roots.
Why the edge direction is prerequisite → course. The input [a, b] says 'take b before a'. So b enables a: the edge runs b → a, and it's a whose in-degree goes up. Getting this backwards produces a perfectly valid topological order of the reversed graph — which is exactly the wrong answer. State the direction out loud before you wire up the adjacency list.
Cycle detection comes for free. In a DAG every node eventually reaches in-degree 0 and gets scheduled, so the output has all numCourses nodes. But if there's a cycle, the nodes on that cycle perpetually block each other — none of them ever reaches in-degree 0, so they're never enqueued. The output ends up shorter than numCourses, and that single length check (order.size != numCourses) is all the cycle detection we need. Return an empty array in that case.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]Interactive diagram
Prerequisite DAG for example 2
initEdges point prerequisite → course. Kahn's peels from course 0 outward.
[0,1,2,3]C · Code with teaching comments
D · Why it works and complexityO(V + E) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
Kahn's algorithm is really 'peeling the graph from its sources'. The in-degree array is a set of countdown timers; finishing a node ticks down its successors, and a node fires the moment its timer hits zero. The leftover nodes that never fire are precisely the cycle — so ordering and cycle detection fall out of the same loop.
ComplexityO(V + E) time, O(V + E) space — Building the graph touches every edge once → O(E). Each node is enqueued and dequeued exactly once → O(V), and across all dequeues we examine each outgoing edge once more → O(E). Total O(V + E) time; the adjacency list and in-degree array are O(V + E) space.
E · Edge cases and pitfalls7numCourses = 1, prerequisites = [] — Course 0 has in-degree 0 → scheduled immediately → [0].Explore edge casesHide edge cases
Edge cases handled
numCourses = 1, prerequisites = []Course 0 has in-degree 0 → scheduled immediately → [0].prerequisites = [] (any n)Every course has in-degree 0 → all enqueued → any permutation, e.g. [0,1,…,n-1].a 2-cycle [[1,0],[0,1]]Both stay at in-degree 1, neither is ever enqueued → order is empty → return [].
Pitfalls
- Reversing the edge direction — produces a valid order of the reversed graph (i.e. wrong answer).
- Seeding the queue with only node 0 instead of all zero-in-degree nodes.
- Returning the partial order on a cycle instead of an empty array.
- Using a list with pop(0) as the queue — O(n) per pop; use a deque/LinkedList.
Approach 2 of 2
DFS Post-Order with 3-Color Cycle Detection
1Hint 1Explore hintHide hint
Topological order is the reverse of DFS finish times. So DFS the whole graph, push each node when you finish exploring all its descendants, then reverse the list.
2Hint 2Explore hintHide hint
To detect cycles, colour each node white (unvisited), grey (on the current recursion stack), or black (fully done).
3Hint 3Explore hintHide hint
If DFS ever reaches a grey node, you've looped back onto the current path — that's a cycle, so bail out and return [].
A · Core idea
DFS produces a topological order from the opposite end: instead of emitting sources first, it emits sinks first and reverses.
Finish order is reverse topological order. When a DFS from node u returns, every node reachable from u has already been fully explored and pushed. So if we append u after recursing into all its neighbours (post-order), the nodes with no outstanding dependents land earliest in the list. Appending in post-order and then reversing yields a valid topological order — every prerequisite ends up before the course that needs it.
The three colours encode recursion state. White means 'not yet visited'. Grey means 'currently on the recursion stack' — we entered it but haven't finished. Black means 'completely explored'. The distinction between grey and black is the whole trick: revisiting a black node is harmless (it's already placed), but reaching a grey node means we've walked an edge back to an ancestor on the current path — a back edge, which is the definition of a cycle in a directed graph.
Why a plain visited boolean isn't enough. A single 'visited' flag can't distinguish 'seen on this path' from 'seen on a previous, finished path'. Two separate DFS trees can legitimately share a node without any cycle. Only the grey state — 'still on the stack right now' — correctly flags a cycle. Conflating black with grey would report false cycles on diamond-shaped DAGs like example 2.
Bailing out on a cycle. The moment DFS hits a grey node we know the schedule is impossible, so we short-circuit all the way up and return an empty array. Otherwise, after every node is black, we reverse the post-order list and return it.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]dfs(0) → dfs(1)
1 → dfs(3); 3 has no neighbours → finish 3
post = [3][0,2,1,3]C · Code with teaching comments
Reference implementation previewprivate List<List<Integer>> adj; private int[] state; // 0=white, 1=grey, 2=black private List<Integer> order; private boolean hasCycle; Explore the full codeHide the full code
D · Why it works and complexityO(V + E) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
Kahn's builds the order front-to-back from the sources; DFS builds it back-to-front from the sinks. They're two views of the same partial order. The grey/black split is the directed-graph analogue of 'am I revisiting myself or just an old neighbour?' — the question that separates a cycle from a harmless re-encounter.
ComplexityO(V + E) time, O(V + E) space — DFS visits every node once (guarded by the colour state) and traverses every edge once → O(V + E). The recursion stack and the colour/order arrays are O(V + E) space.
E · Edge cases and pitfalls7self-dependency would-be [[0,0]] — Constraints forbid aᵢ == bᵢ, but if present, node 0's edge to itself hits a grey node → cycle → [].Explore edge casesHide edge cases
Edge cases handled
self-dependency would-be [[0,0]]Constraints forbid aᵢ == bᵢ, but if present, node 0's edge to itself hits a grey node → cycle → [].disconnected componentsThe outer loop restarts DFS on each unvisited (white) node so every component is ordered.single course, no prereqsdfs(0) finishes immediately; post-order [0] reversed is [0].
Pitfalls
- Using a single visited boolean instead of 3 colours — reports false cycles on diamond DAGs.
- Forgetting to reverse the post-order list — yields the exact reverse of a valid order.
- Not restarting DFS on every unvisited node — misses disconnected components.
- Deep recursion on a long chain (up to 2000 nodes) — usually fine, but Kahn's avoids the stack entirely.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int[] findOrder(int numCourses, int[][] prerequisites) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < numCourses; i++) { adj.add(new ArrayList<>()); }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Reversing the prerequisite edge direction
[a, b] means b is a prerequisite of a, so the edge must run b → a. Building a → b produces a topological order of the reversed graph — every prerequisite ends up AFTER the course that needs it.
Explore the code comparisonHide the code comparison
Reversing the prerequisite edge direction
[a, b] means b is a prerequisite of a, so the edge must run b → a. Building a → b produces a topological order of the reversed graph — every prerequisite ends up AFTER the course that needs it.
Don't write this
for course, prereq in prerequisites:
adj[course].append(prereq) # wrong direction
indegree[prereq] += 1Write this instead
for course, prereq in prerequisites:
adj[prereq].append(course) # prerequisite -> course
indegree[course] += 12Returning a partial order on a cycle
When a cycle exists, Kahn's schedules only the acyclic part, so the output is shorter than numCourses. Returning it ignores the impossibility; the spec requires an empty array.
Explore the code comparisonHide the code comparison
Returning a partial order on a cycle
When a cycle exists, Kahn's schedules only the acyclic part, so the output is shorter than numCourses. Returning it ignores the impossibility; the spec requires an empty array.
Don't write this
while (!queue.isEmpty()) {
int course = queue.poll();
order[idx++] = course;
for (int next : adj.get(course))
if (--indegree[next] == 0) queue.offer(next);
}
return order; // wrong: may be a partial orderWrite this instead
while (!queue.isEmpty()) {
int course = queue.poll();
order[idx++] = course;
for (int next : adj.get(course))
if (--indegree[next] == 0) queue.offer(next);
}
return idx == numCourses ? order : new int[]{};3Single visited flag in DFS misdetects cycles
A boolean 'visited' can't tell 'on the current recursion stack' from 'finished on an earlier path'. Two DFS trees can share a node legitimately; only the grey state flags a real back edge.
Explore the code comparisonHide the code comparison
Single visited flag in DFS misdetects cycles
A boolean 'visited' can't tell 'on the current recursion stack' from 'finished on an earlier path'. Two DFS trees can share a node legitimately; only the grey state flags a real back edge.
Don't write this
visited = [False] * n
def dfs(u):
if visited[u]:
return False # false cycle on a shared node!
visited[u] = True
for v in adj[u]:
if not dfs(v): return False
return TrueWrite this instead
state = [0] * n # 0=white, 1=grey, 2=black
def dfs(u):
state[u] = 1
for v in adj[u]:
if state[v] == 1: return False # back edge = cycle
if state[v] == 0 and not dfs(v): return False
state[u] = 2
return TrueRevise
Carry the pattern into the interview
Pattern to remember
Topological sort of a DAG (Kahn's BFS or DFS post-order)
Code pattern to memorize
indegree[v] = # prereqs of v
queue = all v with indegree 0
order = []
while queue:
u = queue.pop(); order.append(u)
for v in adj[u]:
indegree[v] -= 1
if indegree[v] == 0: queue.push(v)
return order if len(order) == n else [] # [] means a cycleRules to remember
- 1Edge direction is prerequisite → course:
[a, b]means takebbeforea, so add edgeb → aandindegree[a]++. - 2Start Kahn's queue with every zero-in-degree node, not just node 0.
- 3Append a node to the output the moment you pop it (its prerequisites are already placed).
- 4If the final order has fewer than numCourses nodes, a cycle exists → return an empty array.
- 5DFS variant: push each node in post-order, then reverse; a back-edge to a node still on the recursion stack is a cycle.
Use this pattern when
- Ordering tasks/courses under 'X must come before Y' dependency constraints
- Build systems, package install order, spreadsheet recalculation order
- Detecting whether a dependency graph is acyclic AND producing a valid sequence
- Any DAG where you need a linear order respecting all directed edges
Choose another pattern when
- You only need a yes/no 'is it possible?' → Course Schedule I (cycle detection alone)
- Edges are undirected → connectivity / spanning tree, not topo sort
- You need the SHORTEST path or longest chain → BFS/DP on the DAG, not just any topo order
Interview takeaway
Course Schedule II is the canonical topological-sort problem. Kahn's algorithm gives you ordering and cycle detection in one pass; DFS post-order is the same result from the other direction. Master both and you've unlocked Alien Dictionary, Parallel Courses, and build-dependency questions.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternTopological sort of a DAG. Kahn's BFS peels zero-in-degree sources and detects cycles by a short output; DFS post-order reversal does it from the sinks with 3-colour cycle detection. Same family as Course Schedule I, Alien Dictionary, Parallel Courses, and build-dependency ordering.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Course ScheduleJust decide feasibility (can all courses be finished?) — cycle detection without producing the order.
- Alien DictionaryComing soonDerive prerequisite edges from adjacent words' first differing character, then topologically sort the alphabet.
- Parallel CoursesComing soonTopological sort by levels (BFS layers) and count the number of semesters, not a single order.
- Minimum Height TreesComing soonPeel leaves layer by layer (an undirected analogue of Kahn's) until 1–2 centroid nodes remain.