Topological Sort: Solving the 'Course Schedule' Problem

Course Schedule is a graph problem wearing a fairly polite disguise. On the surface, we are given a number of courses and a list of prerequisite pairs. The question sounds administrative enough:

• can we finish all the courses?

What the problem is actually asking is much sharper:

• does this directed dependency graph contain a cycle?

If it does, some course eventually depends on itself through a chain of prerequisites, and the whole plan breaks.

Why This is Really About Cycles

Suppose we have:

[  [1, 0],  [2, 1],  [0, 2],]

That means:

• course 1 needs 0
• course 2 needs 1
• course 0 needs 2

Now we are stuck in a loop:

0 -> 2 -> 1 -> 0

No clever scheduling fixes that. The data is contradictory.

That is why Course Schedule is not really about ordering in the everyday sense. It is about whether a valid ordering exists at all.

Two Strong Solutions

There are two standard ways to solve this properly:

• depth‑first search with explicit cycle detection
• topological sort using in‑degrees, usually called Kahn's algorithm

Both are valid. Both run in linear time relative to the graph size.

I am focusing on topological sort here because the problem is already phrased in terms of dependencies, and the in‑degree model turns that into a very clean bookkeeping exercise.

Building the Graph First

Whatever solution we choose, we need a graph representation.

For a pair [course, prerequisite], it is useful to create an edge:

prerequisite -> course

That means:

• if we finish the prerequisite, we unlock the course that depended on it

This direction also makes the in‑degree interpretation very natural:

• inDegree[course] tells us how many prerequisites are still outstanding

A Practical TypeScript Solution with Kahn's Algorithm

export const canFinish = (  courseCount: number,  prerequisites: number[][]): boolean => {  const adjacencyList = Array.from({ length: courseCount }, () => {    return [] as number[];  });  const inDegrees = new Array<number>(courseCount).fill(0);  for (const [course, prerequisite] of prerequisites) {    adjacencyList[prerequisite].push(course);    inDegrees[course] += 1;  }  const queue: number[] = [];  for (let course = 0; course < courseCount; course += 1) {    if (inDegrees[course] === 0) {      queue.push(course);    }  }  let head = 0;  let completedCourses = 0;  while (head < queue.length) {    const course = queue[head];    head += 1;    completedCourses += 1;    for (const nextCourse of adjacencyList[course]) {      inDegrees[nextCourse] -= 1;      if (inDegrees[nextCourse] === 0) {        queue.push(nextCourse);      }    }  }  return completedCourses === courseCount;};

Why This Queue Tells Us Whether a Schedule Exists

Kahn's algorithm works by repeatedly asking:

• which courses currently have no prerequisites left?

Those courses can be taken now, so we put them in the queue.

Each time we remove one from the queue, we pretend we have completed it. That means every course it unlocks has one fewer outstanding prerequisite.

If one of those newly unlocked courses reaches in‑degree 0, it joins the queue too.

So the algorithm keeps peeling away courses that are currently available. If we eventually peel away all of them, the graph had no cycle.

If we get stuck with courses still remaining but nothing left with in‑degree 0, then the remaining courses must depend on one another in a cycle.

A Quick Example Makes the Failure Case Obvious

Take:

courseCount = 4prerequisites = [  [1, 0],  [2, 1],  [3, 2],]

Here the in‑degrees start as:

• 0 ‑> 0
• 1 ‑> 1
• 2 ‑> 1
• 3 ‑> 1

So the queue starts with [0].

Process 0:

• 1 drops to in‑degree 0

Process 1:

• 2 drops to in‑degree 0

Process 2:

• 3 drops to in‑degree 0

Process 3:

• all courses completed

That is a valid schedule.

Now imagine the cyclic version:

courseCount = 2prerequisites = [  [1, 0],  [0, 1],]

Both courses start with in‑degree 1. The queue starts empty. Nothing can be taken first, which is exactly the point. The dependency loop has already made the schedule impossible before we even begin.

The Dfs Alternative is Also Strong

The other common answer is depth‑first search with three states:

• unvisited
• visiting
• visited

If a DFS ever reaches a node that is already marked visiting, we have found a back‑edge and therefore a cycle.

That is a very solid solution. It is often written like this:

export const canFinish = (  courseCount: number,  prerequisites: number[][]): boolean => {  const adjacencyList = Array.from({ length: courseCount }, () => {    return [] as number[];  });  const state = new Array<number>(courseCount).fill(0);  for (const [course, prerequisite] of prerequisites) {    adjacencyList[prerequisite].push(course);  }  const hasCycle = (course: number): boolean => {    if (state[course] === 1) {      return true;    }    if (state[course] === 2) {      return false;    }    state[course] = 1;    for (const nextCourse of adjacencyList[course]) {      if (hasCycle(nextCourse)) {        return true;      }    }    state[course] = 2;    return false;  };  for (let course = 0; course < courseCount; course += 1) {    if (hasCycle(course)) {      return false;    }  }  return true;};

Which Solution is Best?

I think Kahn's algorithm is the better lead explanation for this particular problem.

Why?

• the question is about whether we can complete everything
• in‑degrees tell us directly what is available to complete next
• the "processed all courses or got stuck early" rule is very easy to reason about

DFS cycle detection is equally valid algorithmically, and some people prefer it because the cycle test is explicit. I would still choose Kahn's algorithm as the main answer here because it matches the dependency story of the problem more naturally.

That said, if the interview or codebase already leans heavily on DFS reasoning, the DFS version is not second‑rate. It is just a different mental model:

• Kahn asks which nodes are available now
• DFS asks whether following dependencies ever loops back into the current path

Why I Use a Head Pointer for the Queue in JavaScript

This is the same small practical choice that comes up in breadth‑first traversal pieces elsewhere on the site. Using shift() works, but it reindexes the array each time.

A head pointer keeps the queue cheap and explicit:

• queue[head] is the next course to process
• increment head when it has been consumed

It is still simple, but it avoids unnecessary churn.

Common Mistakes

Pointing the Graph Edges the Wrong Way

If [course, prerequisite] means "course depends on prerequisite", then the useful edge for topological processing is:

prerequisite -> course

Thinking the Problem Needs the Actual Course Order

It does not. We only need to know whether one exists. Kahn's algorithm still works because the processed count tells us that.

Forgetting That an Empty Initial Queue Can Already Prove Failure

If every node has a prerequisite, there may be no valid starting point at all.

The Graph Lesson Underneath It

Course Schedule is one of the friendlier ways to learn that many dependency questions are really acyclic‑graph questions. Once we see that, the problem becomes much less about courses and much more about structure.

That is why the same mental model turns up in:

• build systems
• job scheduling
• package dependencies
• content pipelines

The nouns change. The cycle problem stays the same.

The Part to Keep

• This is a cycle‑detection problem in a directed graph.
• Kahn's algorithm solves it by repeatedly removing courses with zero outstanding prerequisites.
• DFS cycle detection is also good, but topological sort is the clearest fit for the dependency framing here.

Course Schedule is a strong graph problem because the algorithm is not pretending to be clever. It is just patiently removing what can be done next and noticing whether anything impossible is left behind.