~20 minutes · Day 54 · topological sort · Python
Tonight you meet Course Schedule: given courses and prerequisite pairs, decide whether every course can be finished. This is a classic interview graph question because the data sounds like school planning, but the hidden issue is sharper: can these directed requirements be ordered without looping forever?
A dependency order exists iff the directed graph has no cycle — detect it with three-color DFS or Kahn's in-degree peeling.
That one sentence is the pattern. A prerequisite pair creates a directed edge: pre -> course. A valid course order is a topological ordering, and topological order exists exactly for a directed acyclic graph. Course Schedule only asks whether an order exists, not what the order is (problem statement).
For Kahn's algorithm, use two small structures:
graph[pre] stores the courses unlocked after finishing pre.indeg[course] stores how many prerequisites still block that course.A queue holds courses with indeg == 0: they are safe to take now. Python's collections.deque gives efficient pops from the left, which is exactly what a queue needs.
Each node's in-degree is the count of prerequisites still blocking it; Kahn's algorithm peels any node whose in-degree has dropped to 0.
The brute force idea is to keep scanning all courses, looking for one whose prerequisites are all finished. When you find one, remove it and scan everything again. This works, but each pass can re-check many edges. In the worst case it can take O(VE) time for V courses and E prerequisite pairs.
Kahn's algorithm keeps the same idea but stops re-scanning. Instead of asking, slowly, “which courses are unblocked now?”, it maintains the exact count of remaining blockers for every course.
from collections import deque
def can_finish(n, prerequisites):
graph, indeg = [[] for _ in range(n)], [0] * n
for course, pre in prerequisites:
graph[pre].append(course); indeg[course] += 1 # pre unlocks course
q, taken = deque(i for i in range(n) if indeg[i] == 0), 0
while q:
pre = q.popleft(); taken += 1 # peel one free node
for course in graph[pre]:
indeg[course] -= 1 # remove one blocker
if indeg[course] == 0: q.append(course)
return taken == n # cycle leaves nodes blocked
Think of the queue as the front edge of the order. Every time you take a course, its outgoing edges disappear. If that makes another course's in-degree zero, that course joins the queue. If a cycle exists, every course inside the cycle still waits for another course inside the same cycle, so the queue eventually dries up too early.
Shaded cells hold in-degree 0 and get taken this round; taking them drops their neighbours' counts, and peeled nodes vanish from later rounds.
A build system has tasks A, B, and C. If A needs B, B needs C, and C needs A, can the build ever start?
Before opening the reveal: model the graph. What are the nodes, what are the edges, and what happens to the initial zero-in-degree queue?
The nodes are tasks. The edges are prerequisite arrows. Every task has one incoming blocker, so the zero-in-degree queue starts empty. Kahn's peel takes zero nodes, which is less than three, so a directed cycle exists and no dependency order exists.
| Approach | Time | Space |
|---|---|---|
| Brute force (re-scan blockers each round) | O(VE) | O(V + E) |
| Topological peel (track every in-degree) | O(V + E) | O(V + E) |
The memory stores the graph and the in-degree array. The win is that every node enters the queue at most once, and every edge is processed once.
1. What does in-degree count here?
2. Which course enters Kahn's queue first?
3. Spot the bug in this graph build:
for course, pre in prerequisites:
graph[course].append(pre)
indeg[course] += 14. Which task is this pattern?
Solve Course Schedule on LeetCode, logging it in your Notion tracker with the cycle - predict -> attempt -> compare -> encode:
Watch NeetCode - Course Schedule after your attempt, as the compare step. Do not use it before the first serious try.
Stuck or curious? Ask your teacher (the agent) - that's what it's for.