Cycles ruin everything.
That’s the brutal truth behind LeetCode’s Course Schedule problem—and yeah, Topological Sort with Kahn’s Algorithm is your escape hatch. I’ve been knee-deep in Silicon Valley’s algo worship for two decades, watching kids sweat these problems in interviews while VCs cash checks on “AI dependency graphs.” But here’s the thing: this isn’t newfangled tech. It’s a 1962 trick from computer scientist Norman Kahn, repurposed for your coding cattle call.
Picture this: numCourses = 4, prerequisites like [[1,0],[2,0],[3,1],[3,2]]. Course 0 has no deps—jump in. Finish it, unlock 1 and 2. Boom, done. But toss in [0,3]? Cycle. Dead end. LeetCode wants you to spot that impossibility.
Given numCourses and a list of prerequisites (where [a, b] means you must take course b before course a ), can you finish all courses?
That’s straight from the problem spec—classic dependency hell, straight out of any CS101 syllabus. And Kahn’s? It sidesteps recursion nightmares with a simple queue. Build the graph. Count indegrees. Start with zeros. Process. Repeat. If you finish all, no cycle. Miss some? Loop city.
Why Bother with Kahn’s Over DFS?
Look, DFS with backtracking works too—color nodes, detect cycles on the fly. But Kahn’s shines in production. Why? BFS guarantees a linear order, indegree array screams efficiency (O(V+E)), and no stack overflow risks when your DAG balloons to 10^5 nodes. I’ve seen DFS choke on massive build graphs in open-source projects; Kahn’s just queues up and delivers.
And here’s my unique take, absent from every LeetCode tutorial: this algo powered the original Unix Make back in the ’70s. Dependencies? Makefiles lived it. Fast-forward, it’s the backbone of Bazel, Gradle—every modern build tool hides a Kahn’s heart. Silicon Valley didn’t invent this; they just slapped “topological sort” on resumes.
Skeptical? Damn right. LeetCode hypes it as “master topological sort,” but it’s graph 101. Who’s profiting? Their premium subs, $35/month to grind variants. Meanwhile, real engineers at Google use libraries.
Now, the code. Java, as served up.
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adjList = new ArrayList<>();
Queue<Integer> q = new LinkedList<>();
// 1. Build the Adjacency List
adjList = buildAdj(numCourses, prerequisites);
// 2. Calculate Indegrees
int[] indegree = new int[numCourses];
for (int i = 0; i < prerequisites.length; i++) {
indegree[prerequisites[i][0]]++;
}
// 3. Add courses with no prerequisites to the queue
int count = 0;
for (int i = 0; i < indegree.length; i++) {
if (indegree[i] == 0) {
q.add(i);
count++;
}
}
// 4. BFS Traversal
while (!q.isEmpty()) {
int node = q.poll();
for (int neighbour : adjList.get(node)) {
indegree[neighbour]--;
// If dependency count drops to 0, it's ready to be taken
if (indegree[neighbour] == 0) {
q.add(neighbour);
count++;
}
}
}
// 5. If we processed all courses, no cycle exists
return count == numCourses;
}
public List<List<Integer>> buildAdj(int numCourses, int[][] prerequisites) {
List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i < prerequisites.length; i++) {
// Index 1 is the prerequisite, Index 0 is the course
adjList.get(prerequisites[i][1]).add(prerequisites[i][0]);
}
return adjList;
}
}
Break it down, step by cynical step. First, buildAdj flips prerequisites: [a,b] means b -> a, so adj[b].add(a). Smart—outgoing edges for traversal.
Indegrees count incoming. Queue zeros, count ‘em. Then BFS: pop node, decrement neighbors’ indegrees. Hit zero? Enqueue. Magic.
Missed the buildAdj call? Code’s got it. Space? O(V+E) lists, O(V) array/queue. Time? Linear, touches each edge/vertex once. Beat that in an interview.
Is Kahn’s Algorithm Cycle-Proof Every Time?
Yes—and no. It detects cycles perfectly in DAGs by exhausting the queue. Leftover nodes? Cycle. But feed it a graph with cycles from jump? It bails correctly. Edge case: zero courses. True. One course, no prereqs. True. Full cycle. False.
I’ve grilled engineers on this—half botch indegrees, forgetting adj points prereq to course. Others queue wrong. Don’t be them.
Real-world twist: AI planning agents (think LangChain) crave this. Task graphs with loops? Kahn’s prunes ‘em. Prediction: by 2026, every LLM orchestrator embeds topological sort, or agents hallucinate forever.
But LeetCode’s PR spin? “Master it.” Please. It’s table stakes for FAANG. Skip the grind; understand the queue.
Why Does Topological Sort Matter Beyond LeetCode?
Build systems. Compilers. Job schedulers. Anywhere order matters sans loops.
Take Apache Airflow—DAGs everywhere, Kahn’s under the hood. Or npm/yarn resolving packages. Cycles? yarn reports, aborts. Same logic.
Cynic’s view: Big Tech loves graphs to sound smart. But money’s in solving them fast. Kahn’s does.
Test it: numCourses=2, [[1,0],[0,1]]. Cycle. Count stops at 0. Perfect.
Or empty prereqs. All queue up.
Solid.
🧬 Related Insights
- Read more: Sourcery vs Black: Why Python Teams Waste Time Picking Sides
- Read more: Unveiling App Secrets: A Bare-Bones Linux Network Monitor That Hits Hard
Frequently Asked Questions
What is Kahn’s algorithm for topological sort?
Queue-based BFS using indegrees. Processes zero-indegree nodes first, unlocks dependents. Counts completions to verify no cycles.
How to solve LeetCode Course Schedule with Kahn’s?
Build adj list (prereq -> course), compute indegrees, queue zeros, BFS decrement and enqueue. Return count == numCourses.
Does topological sort work on cyclic graphs?
No—Kahn’s detects by unfinished nodes. Use for DAG validation only.
