← Back to all patterns

Course Schedule

Topological BFS (Kahn's Algorithm) Pattern · Interactive Visualizer & Interview Guide

Number of Islands teaches "find connected cells." Course Schedule teaches a different BFS mental model: keep taking only the courses that are currently unblocked. The queue holds ready courses, and the in-degree array tracks prerequisites still missing.
Core idea
A prerequisite pair [a, b] means take b before a. So draw the arrow b -> a. Then count how many arrows point into each course. Courses with indegree = 0 are immediately available.
Courses
Dependencies
Queue (ready right now)
Pop order
0
Processed
0
Still blocked
-
LC 207 verdict

Build graph + count prerequisites

Ready = indegree 0 Current = popped this step Done = already taken Blocked = waiting on prerequisites
How to open
"This is a dependency graph problem, not a grid problem. Each prerequisite pair means one course must happen before another, so I should think in terms of topological ordering."
How to define the graph
"For each pair [course, prereq], I add an edge prereq -> course. I also keep an indegree[] array where indegree[x] tells me how many prerequisites course x still needs."
How the BFS works
"I enqueue every course with indegree == 0 because those are the only courses I can take immediately. Then I repeatedly pop one, mark it as processed, and reduce the indegree of every dependent course. If a dependent course drops to 0, it just became ready, so I enqueue it."
How to finish LC 207
"For Course Schedule I, I only need a count. If I process all numCourses nodes, there was no cycle and the answer is true. If the queue becomes empty early, some courses are stuck in a cycle, so the answer is false."
How to finish LC 210
"Course Schedule II is the exact same algorithm. The only difference is that every time I pop a course, I append it to a result list. That pop order is a valid topological order. If I do not process all courses, I return an empty array."
LC 207 vs LC 210
Same graph. Same queue. Same indegree updates. LC 210 just records the pop order.

Course Schedule I (207)

  • Return type: boolean
  • Track: processed count
  • Success check: count == numCourses

Course Schedule II (210)

  • Return type: int[]
  • Track: result list + count
  • Success check: order.size() == numCourses
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        int[] indegree = new int[numCourses];

        for (int[] pair : prerequisites) {
            int course = pair[0];
            int prereq = pair[1];
            graph.get(prereq).add(course);
            indegree[course]++;
        }

        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        int processed = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            processed++;

            for (int next : graph.get(course)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        return processed == numCourses;
    }
}
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        int[] indegree = new int[numCourses];

        for (int[] pair : prerequisites) {
            int course = pair[0];
            int prereq = pair[1];
            graph.get(prereq).add(course);
            indegree[course]++;
        }

        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        int[] order = new int[numCourses];
        int idx = 0;

        while (!queue.isEmpty()) {
            int course = queue.poll();
            order[idx++] = course;

            for (int next : graph.get(course)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        return idx == numCourses ? order : new int[0];
    }
}

Use this when you hear dependency words

"prerequisites", "depends on", "must come before", "valid order", "finish all tasks", and "cycle" are strong topological-sort signals.

The queue means "ready now"

In ordinary BFS the queue holds locations to visit. Here the queue holds courses whose prerequisites are fully satisfied. That makes the queue semantics very easy to explain.

Cycle detection falls out naturally

If a cycle exists, every node in that cycle will keep indegree > 0 forever. The queue dries up before all nodes are processed, so you do not need separate cycle-path bookkeeping.

LC 210 becomes almost free

The BFS pop order is already a valid topological order. So once you understand LC 207, LC 210 is basically the same code plus one append.

Why not DFS? DFS can also solve topological sort and cycle detection, but it is usually harder to explain cleanly in interviews because you need recursion states such as unvisited / visiting / visited. Kahn's BFS is often simpler to reason about aloud.
What is the mental model? Stop thinking "traverse the graph." Think "keep removing the courses that are currently unblocked". That is what makes Course Schedule feel intuitive instead of abstract.
O(V + E)
Time: build graph once, process each edge once
O(V + E)
Space: adjacency list, indegree array, queue
V = number of courses. Every course enters the queue at most once and is popped at most once.
E = number of prerequisite pairs. Every edge is only used when its prerequisite course gets processed and decrements the dependent course's indegree.
Interview shortcut: "Each node is enqueued once, each directed edge is relaxed once, so both time and space are linear in the graph size."
Common mistake: saying O(n^2) just because prerequisites is a 2D array. That array is really an edge list, so the correct term is O(V + E).