LeetCode 207 – Course Schedule

Course Schedule is a cycle-detection problem in a directed graph wearing a scheduling problem's clothes, and the first job is to notice that. Once the question is restated as "does this directed graph have a cycle?" there are two standard answers, and the interesting part is that the DFS one needs three node states rather than the two you would expect.

The problem

There are numCourses courses. Each pair [a, b] means you must take b before a. Return whether it is possible to finish all of them.

2, [[1,0]]           -> true     take 0, then 1

2, [[1,0],[0,1]]     -> false    0 needs 1, 1 needs 0

3, [[1,0],[2,1]]     -> true     0 -> 1 -> 2

2, []                -> true     no prerequisites at all
1, [[0,0]]           -> false    a course requiring itself

Build the graph with an edge b → a — "b unlocks a" — and the question becomes whether that graph is acyclic. Nothing else about scheduling matters.

Two standard answers

Kahn's is easier to get right and produces the ordering for free, which is what Course Schedule II asks for. Prefer it unless asked for the recursion.

Kahn: count what is left

Track each course's in-degree — how many prerequisites it still needs. Start a queue with every course whose in-degree is zero. Taking a course decrements the in-degree of everything it unlocks, and anything reaching zero joins the queue.

3 courses, [[1,0],[2,1]]      edges 0→1, 1→2

in-degree:  0:0  1:1  2:1
queue [0]   take 0  -> 1 drops to 0, enqueue
queue [1]   take 1  -> 2 drops to 0, enqueue
queue [2]   take 2

taken 3 of 3 -> true

The termination condition is the elegant part: if the number of courses taken is less than numCourses, the remainder is exactly the set of courses stuck in a cycle. You never look for the cycle — you notice what is left.

Java

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> unlocks = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) unlocks.add(new ArrayList<>());

        int[] inDegree = new int[numCourses];

        // [a, b] means b must come first, so the edge points b -> a.
        for (int[] pair : prerequisites) {
            unlocks.get(pair[1]).add(pair[0]);
            inDegree[pair[0]]++;
        }

        Deque<Integer> ready = new ArrayDeque<>();
        for (int course = 0; course < numCourses; course++) {
            if (inDegree[course] == 0) ready.add(course);
        }

        int taken = 0;
        while (!ready.isEmpty()) {
            int course = ready.poll();
            taken++;

            for (int nextCourse : unlocks.get(course)) {
                if (--inDegree[nextCourse] == 0) ready.add(nextCourse);
            }
        }

        // Anything not taken is stuck in a cycle -- no need to find it.
        return taken == numCourses;
    }
}

Getting the edge direction right is the one modelling decision, and reversing it produces a graph whose cycles are the same — so it still gives the right answer here, and the wrong order in problem 210. Fix the direction now and both work.

--inDegree[nextCourse] == 0 decrements and tests in one step, which is the idiom to recognise. The queue only ever receives a course at the exact moment its last prerequisite is satisfied, so no course is enqueued twice.

Python

from collections import defaultdict, deque


class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        unlocks = defaultdict(list)
        in_degree = [0] * numCourses

        for course, prerequisite in prerequisites:
            unlocks[prerequisite].append(course)      # edge prerequisite -> course
            in_degree[course] += 1

        ready = deque(c for c in range(numCourses) if in_degree[c] == 0)

        taken = 0
        while ready:
            course = ready.popleft()
            taken += 1

            for next_course in unlocks[course]:
                in_degree[next_course] -= 1
                if in_degree[next_course] == 0:
                    ready.append(next_course)

        return taken == numCourses

Unpacking for course, prerequisite in prerequisites names the two halves, which is worth doing — pair[0] and pair[1] is where the direction gets reversed by accident.

The DFS version, and its third state

The recursive answer marks nodes and looks for a back edge. The trap is that two states — visited and unvisited — are not enough:

0 = unvisited
1 = in progress   (on the current DFS path)
2 = done          (fully explored, no cycle below it)

reaching a node in state 1  ->  CYCLE
reaching a node in state 2  ->  fine, already cleared

With only "visited", a diamond — a → b, a → c, b → d, c → d — reports a cycle when the second path reaches d, because d is marked and the algorithm cannot tell "already finished" from "currently above me on the stack". Those are different facts and both are needed.

That distinction is the reason this problem is asked with DFS at all, and it is worth stating even if you write Kahn's.

Complexity

Every node is dequeued once and every edge relaxed once. The adjacency list dominates the space, and building it is unavoidable — the input is an edge list, and traversing an edge list repeatedly would be O(V · E).

The pattern

Topological sorting and cycle detection in a DAG are the same computation read two ways, and this family is large: Course Schedule II (210) returns the order instead of a boolean, Alien Dictionary (269) derives the edges from word comparisons before doing exactly this, and Minimum Height Trees (310) peels degree-1 nodes with the same in-degree loop on an undirected graph.

The recognition to carry away: "can these tasks be ordered given these dependencies?" is always this problem, whatever the tasks are called.

What the interviewer is checking

• That you restate it as cycle detection in a directed graph.
• The edge direction, and that [a, b] means b → a.
• That the count of taken courses is what detects the cycle.
• Three DFS states, not two, and the diamond that proves it.
• No prerequisites, a self-loop, and disconnected components.
• That building an adjacency list is what keeps it O(V + E).