207. Course Schedule

Course Schedule looks like a scheduling puzzle, but strip away the story and it’s a pure graph question: can you order these nodes so every dependency comes first? That’s topological sorting, and the answer hinges on one thing — cycles. It’s a cornerstone of the graph pattern, and once you see the reduction the code almost writes itself.

The problem

You have numCourses courses numbered 0 to numCourses - 1, and a list of prerequisite pairs. A pair [a, b] means you must finish course b before you can take a. Return true if some order lets you finish every course. (Full statement on LeetCode.)

Two courses with rules [1, 0] and [0, 1] are impossible: 1 needs 0 first, but 0 needs 1 first. Drop one of those rules and suddenly there’s a valid order. That deadlock is the entire challenge.

Intuition: a valid schedule exists iff the graph is acyclic

Model each course as a node and each pair [a, b] as a directed edge $b \rightarrow a$ (“b unlocks a”). A prerequisite loop — a course that eventually depends on itself — is exactly a cycle in this graph. So the question “can I finish everything?” is identical to “is this directed graph acyclic?”

The clean way to check is Kahn’s algorithm. Track each course’s in-degree: how many prerequisites still block it. Any course with in-degree $0$ has nothing in its way, so you can take it now. Take it, then relax its edges — every course it unlocks loses one blocker. Keep peeling off zero-in-degree courses like layers of an onion.

Here’s the key insight: if the graph is acyclic, you’ll eventually peel away every course. But if a cycle exists, those courses form a knot where each one is waiting on another inside the loop — their in-degree never reaches $0$, so they’re never processed. Count how many you managed to take; if it’s fewer than numCourses, a cycle trapped the rest.

Solution

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // adjacency list: for edge b -> a, adj[b] lists the courses b unlocks
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());

        int[] inDegree = new int[numCourses];
        for (int[] pre : prerequisites) {
            int a = pre[0], b = pre[1];   // must take b before a
            adj.get(b).add(a);
            inDegree[a]++;                // a gains one blocker
        }

        // start with every course that has no prerequisites
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }

        int taken = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            taken++;
            for (int next : adj.get(course)) {
                // one blocker cleared; if it was the last, this course is free
                if (--inDegree[next] == 0) queue.offer(next);
            }
        }

        return taken == numCourses;   // all taken => no cycle
    }
}

The DFS alternative works too: walk each course and mark nodes as unvisited / on the current path / done. If you ever step onto a node already on the current path, you’ve closed a cycle. Both run in the same time; Kahn’s tends to read more naturally because “take the course with no blockers left” mirrors how you’d actually plan a semester.

Complexity

	Time	Space
Kahn’s (BFS) topological sort	$O(V + E)$	$O(V + E)$

$V =$ numCourses and $E =$ number of prerequisite pairs. You touch each node once when it hits in-degree $0$ and each edge once when you relax it. Space is the adjacency list plus the in-degree array and queue.

In an interview

Say the reduction out loud before touching code: “this is asking whether a directed graph is acyclic, so I’ll do a topological sort and check that I can order all the nodes.” That single sentence signals you recognized the pattern rather than inventing an ad-hoc fix.

The trap is edge direction. [a, b] means b before a, so the edge runs $b \rightarrow a$ and it’s a’s in-degree that goes up. Reversing every edge preserves whether a cycle exists, so a globally flipped convention still gets this true/false right — but mix the two conventions and the in-degree counts turn to garbage, and even a consistent flip hands back the wrong ordering the moment the follow-up (Course Schedule II) asks you to return one. State your convention explicitly and keep it consistent. Also mention the empty-prerequisites case: no edges means every course starts free, and the count naturally reaches numCourses.

This is the gateway to topological ordering, which powers Course Schedule II (return the actual order) and Alien Dictionary. The same graph-modeling instinct — nodes, edges, traversal — sits underneath Clone Graph and Number of Islands; the graph pattern hub ties them together.

References

• LeetCode 207 — Course Schedule