21  Course Schedule

Rank 19 · Pattern: topological sorting with indegrees · Target: \(O(V+E)\) time

21.1 Problem definition

Given a number of courses and a collection of prerequisite pairs, return whether it is possible to complete every course while respecting all prerequisites.

21.2 Clarifying questions

1. What does each pair in prerequisites mean?
2. What range of course IDs is valid?
3. Can duplicate prerequisite pairs occur?
4. Should I return only feasibility or an actual course order?
5. Can there be zero courses or no prerequisite pairs?

21.3 Sample answers

1. A pair [course, prerequisite] means the prerequisite must be completed before the course.
2. For numCourses courses, every ID is in 0..numCourses - 1.
3. No. Each directed dependency appears at most once.
4. Return only a boolean indicating whether all courses can be completed.
5. Yes. Zero courses and an empty prerequisite array are valid and feasible.

21.4 Special data structures: adjacency list, indegree, queue

nextCourses is an adjacency list. At index p, it stores courses unlocked after prerequisite p. For prerequisite pairs [[1,0],[2,0],[3,1],[3,2]], the directed graph is:

%%{init: {
  "theme": "base",
  "flowchart": {
    "htmlLabels": false
  },
  "themeVariables": {
    "primaryColor": "#ffffff",
    "secondaryColor": "#ffffff",
    "tertiaryColor": "#ffffff",
    "primaryTextColor": "#222222",
    "primaryBorderColor": "#555555",
    "lineColor": "#555555",
    "edgeLabelBackground": "#ffffff"
  }
}}%%
flowchart TB
  C0["course 0"]
  C1["course 1"]
  C2["course 2"]
  C3["course 3"]

  C0 --> C1
  C0 --> C2
  C1 --> C3
  C2 --> C3

  classDef course fill:#ffffff,stroke:#555555,stroke-width:1.5px,color:#222222;
  class C0,C1,C2,C3 course;

The indegree collection stores the number of incoming prerequisite edges not yet removed, and a FIFO queue contains courses whose indegree is zero.

Java

Use List<List<Integer>>, an int[], and ArrayDeque<Integer> with offer/poll.

Python

Use a list of lists, a zero-filled integer list, and collections.deque with append/popleft.

Rust

Use Vec<Vec<usize>>, Vec<usize>, and VecDeque<usize>. Prerequisite pairs are fixed-size [usize; 2] values in a borrowed slice.

21.5 Approach and invariant

This is Kahn’s topological-sort algorithm:

1. Build outgoing adjacency lists and indegrees.
2. Enqueue every zero-indegree course.
3. Complete a ready course and decrement each dependent course’s indegree.
4. Enqueue a dependent when its indegree reaches zero.
5. All courses are possible exactly when the completed count is numCourses.

Invariant: prerequisitesLeft[c] equals the number of incoming edges to c from courses not yet completed; the queue contains ready courses whose count is zero.

%%{init: {
  "theme": "base",
  "flowchart": {
    "htmlLabels": false
  },
  "themeVariables": {
    "primaryColor": "#ffffff",
    "secondaryColor": "#ffffff",
    "tertiaryColor": "#ffffff",
    "primaryTextColor": "#222222",
    "primaryBorderColor": "#555555",
    "lineColor": "#555555",
    "edgeLabelBackground": "#ffffff"
  }
}}%%
flowchart TB
  A["Build adjacency lists and indegrees"]
  B["Queue every course with indegree zero"]
  C["Poll and count one ready course"]
  D["Decrease the indegree of each dependent course"]
  E["Queue every dependent that reaches indegree zero"]
  F{"Is the ready queue empty?"}
  G["NO: process the next ready course"]
  H{"YES: does completed equal the course count?"}
  I["YES: return true; every course is feasible"]
  J["NO: return false; a cycle blocks the remainder"]

  A --> B
  B --> C
  C --> D
  D --> E
  E --> F
  F --> G
  G --> C
  F --> H
  H --> I
  H --> J

  classDef plain fill:#ffffff,stroke:#555555,stroke-width:1.5px,color:#222222;
  class A,B,C,D,E,F,G,H,I,J plain;

21.6 Minimal solution

Java

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class CourseScheduleSolution {
    static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> nextCourses = new ArrayList<>();
        for (int course = 0; course < numCourses; course++) {
            nextCourses.add(new ArrayList<>());
        }

        int[] prerequisitesLeft = new int[numCourses];
        for (int[] pair : prerequisites) {
            int course = pair[0];
            int prerequisite = pair[1];
            nextCourses.get(prerequisite).add(course);
            prerequisitesLeft[course]++;
        }

        Queue<Integer> ready = new ArrayDeque<>();
        for (int course = 0; course < numCourses; course++) {
            if (prerequisitesLeft[course] == 0) {
                ready.offer(course);
            }
        }

        int completed = 0;
        while (!ready.isEmpty()) {
            int prerequisite = ready.poll();
            completed++;
            for (int course : nextCourses.get(prerequisite)) {
                prerequisitesLeft[course]--;
                if (prerequisitesLeft[course] == 0) {
                    ready.offer(course);
                }
            }
        }
        return completed == numCourses;
    }

    @Test public void acceptsZeroCourses() {
        assertTrue(canFinish(0, new int[0][2]));
    }

    @Test public void acceptsIndependentCourses() {
        assertTrue(canFinish(3, new int[0][2]));
    }

    @Test public void acceptsSingleDependency() {
        assertTrue(canFinish(2, new int[][] {{1, 0}}));
    }

    @Test public void acceptsDependencyChain() {
        assertTrue(canFinish(4, new int[][] {{1, 0}, {2, 1}, {3, 2}}));
    }

    @Test public void acceptsDiamondDependencies() {
        assertTrue(canFinish(4, new int[][] {{1, 0}, {2, 0}, {3, 1}, {3, 2}}));
    }

    @Test public void rejectsSimpleCycle() {
        assertFalse(canFinish(2, new int[][] {{1, 0}, {0, 1}}));
    }

    @Test public void rejectsSelfDependency() {
        assertFalse(canFinish(1, new int[][] {{0, 0}}));
    }

    @Test public void rejectsCycleDespiteDisconnectedCourse() {
        assertFalse(canFinish(3, new int[][] {{1, 0}, {0, 1}}));
    }

    public static void main(String[] args) {
        JUnitCore.main("CourseScheduleSolution");
    }
}

Python

import unittest
from collections import deque


def can_finish(num_courses, prerequisites):
    next_courses = [[] for _ in range(num_courses)]
    prerequisites_left = [0] * num_courses

    for course, prerequisite in prerequisites:
        next_courses[prerequisite].append(course)
        prerequisites_left[course] += 1

    ready = deque(
        course
        for course, count in enumerate(prerequisites_left)
        if count == 0
    )

    completed = 0
    while ready:
        prerequisite = ready.popleft()
        completed += 1
        for course in next_courses[prerequisite]:
            prerequisites_left[course] -= 1
            if prerequisites_left[course] == 0:
                ready.append(course)

    return completed == num_courses


class CourseScheduleTests(unittest.TestCase):
    def test_accepts_zero_courses(self):
        self.assertTrue(can_finish(0, []))

    def test_accepts_independent_courses(self):
        self.assertTrue(can_finish(3, []))

    def test_accepts_single_dependency(self):
        self.assertTrue(can_finish(2, [[1, 0]]))

    def test_accepts_dependency_chain(self):
        self.assertTrue(can_finish(4, [[1, 0], [2, 1], [3, 2]]))

    def test_accepts_diamond_dependencies(self):
        self.assertTrue(can_finish(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))

    def test_rejects_simple_cycle(self):
        self.assertFalse(can_finish(2, [[1, 0], [0, 1]]))

    def test_rejects_self_dependency(self):
        self.assertFalse(can_finish(1, [[0, 0]]))

    def test_rejects_cycle_despite_disconnected_course(self):
        self.assertFalse(can_finish(3, [[1, 0], [0, 1]]))


if __name__ == "__main__":
    unittest.main()

Rust

use std::collections::VecDeque;

pub fn can_finish(num_courses: usize, prerequisites: &[[usize; 2]]) -> bool {
    let mut next_courses = vec![Vec::new(); num_courses];
    let mut prerequisites_left = vec![0; num_courses];

    for &[course, prerequisite] in prerequisites {
        next_courses[prerequisite].push(course);
        prerequisites_left[course] += 1;
    }

    let mut ready = VecDeque::new();
    for (course, &count) in prerequisites_left.iter().enumerate() {
        if count == 0 {
            ready.push_back(course);
        }
    }

    let mut completed = 0;
    while let Some(prerequisite) = ready.pop_front() {
        completed += 1;
        for &course in &next_courses[prerequisite] {
            prerequisites_left[course] -= 1;
            if prerequisites_left[course] == 0 {
                ready.push_back(course);
            }
        }
    }

    completed == num_courses
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn accepts_zero_courses() {
        assert!(can_finish(0, &[]));
    }

    #[test]
    fn accepts_independent_courses() {
        assert!(can_finish(3, &[]));
    }

    #[test]
    fn accepts_single_dependency() {
        assert!(can_finish(2, &[[1, 0]]));
    }

    #[test]
    fn accepts_dependency_chain() {
        assert!(can_finish(4, &[[1, 0], [2, 1], [3, 2]]));
    }

    #[test]
    fn accepts_diamond_dependencies() {
        assert!(can_finish(4, &[[1, 0], [2, 0], [3, 1], [3, 2]]));
    }

    #[test]
    fn rejects_simple_cycle() {
        assert!(!can_finish(2, &[[1, 0], [0, 1]]));
    }

    #[test]
    fn rejects_self_dependency() {
        assert!(!can_finish(1, &[[0, 0]]));
    }

    #[test]
    fn rejects_cycle_despite_disconnected_course() {
        assert!(!can_finish(3, &[[1, 0], [0, 1]]));
    }
}

21.7 High-value tests

Courses / prerequisites	Expected	Purpose
3 / []	true	independent vertices
2 / [[1,0]]	true	one edge
2 / [[1,0],[0,1]]	false	simple cycle
diamond DAG shown above	true	converging dependencies
cycle plus disconnected course	false	partial completion is insufficient
self-edge [0,0]	false	self-cycle

21.8 Complexity and correctness

Graph construction and traversal each touch every vertex and edge a constant number of times: \(O(V+E)\) time and \(O(V+E)\) space.

Only a zero-indegree course can appear next in a valid order. Removing it and its outgoing edges preserves the indegree invariant. A directed acyclic graph always has a zero-indegree vertex, so the process removes all vertices. If vertices remain when the queue empties, the remaining subgraph has no zero-indegree vertex and therefore contains a directed cycle.

21.9 If the interviewer pushes

• Return an actual course order by appending each polled course; return empty if count is short.
• DFS with three colors (unvisited, visiting, done) detects a back edge and uses the same \(O(V+E)\) bounds.
• Deduplicate repeated prerequisite pairs if the input can contain them; otherwise duplicate edges inflate indegrees consistently but represent a questionable contract.
• For frequent updates, maintaining a topological order dynamically is a more advanced problem.

21.10 TDD interview script

Confirm that [course, prerequisite] means a directed edge from prerequisite to course, IDs are valid, pairs are unique, only feasibility is returned, and zero courses or edges are allowed. Then write this test list:

1. Zero courses
2. Independent courses
3. One dependency
4. Dependency chain
5. Diamond dependencies
6. Two-node cycle
7. Self-cycle
8. Cycle beside a disconnected course

Add one focused red–green–refactor cycle per graph. Keep tiny fixtures that make edge direction visible, confirm the intended failure, add the next graph-building or queue rule, and rerun the complete example. Assert only feasibility, not one particular topological order.

From book/src, run:

Java

./java/run.sh CourseScheduleSolution

Python

./python/run.sh course_schedule_solution

Rust

./rust/run.sh course_schedule_solution

Narrate Kahn’s algorithm in terms of work remaining: the indegree is the number of prerequisites not yet completed, and only courses with zero remaining prerequisites enter the ready queue.

21.10.1 Pseudocode

create an outgoing adjacency list for every course
prerequisitesLeft = zero-filled array

for each [course, prerequisite]:
    add course to prerequisite's outgoing list
    prerequisitesLeft[course]++

queue every course with zero prerequisitesLeft
completed = 0

while queue is not empty:
    prerequisite = dequeue
    completed++
    for each course unlocked by prerequisite:
        prerequisitesLeft[course]--
        if it becomes zero:
            enqueue course

return completed == numCourses

The invariant is: each indegree equals the number of incoming edges from unfinished courses, and the queue contains courses that are currently ready.

21.10.2 TDD sequence

Step	Test code added	Production code added or changed
1. Empty graph	acceptsZeroCourses	Initialize empty graph structures and compare completed count with zero.
2. Independent vertices	acceptsIndependentCourses	Create one adjacency bucket per course, enqueue every zero-indegree vertex, and count each completion.
3. One directed edge	acceptsSingleDependency	Build prerequisite-to-course adjacency and increment the dependent course’s indegree. Decrement it when its prerequisite completes.
4. Cascading readiness	acceptsDependencyChain	Enqueue a dependent exactly when its indegree reaches zero, allowing readiness to propagate.
5. Converging prerequisites	acceptsDiamondDependencies	Retain the full indegree count; a course with two prerequisites becomes ready only after both edges are removed.
6. Simple cycle	rejectsSimpleCycle	Return false when the queue empties before completed == numCourses.
7. Self-cycle	rejectsSelfDependency	Treat a self-edge as ordinary indegree; it leaves no ready vertex and is rejected.
8. Partial progress	rejectsCycleDespiteDisconnectedCourse	Compare the final count with all courses, not merely whether at least one course was completed.

The sequence grows graph construction and topological processing separately. The diamond and disconnected-cycle regressions target the two most common counting errors: unlocking too early and accepting partial completion.