Course Schedule: A Step-by-Step Interview Walkthrough

Jun 2

13 min read

Course Schedule is a problem whose entire difficulty lies in recognizing what it's actually asking. The framing — courses, prerequisites, "can you finish everything?" — sounds like a scheduling or simulation problem, and candidates who take that framing literally end up trying to build actual orderings and check them, which is both hard and slow. The candidates who pass are the ones who strip away the cover story and ask: when is it impossible to finish all courses? The answer is "when the prerequisites form a cycle" — course A needs B, B needs C, C needs A, and now nobody can go first. Once you see that, the problem isn't about scheduling at all; it's about detecting a cycle in a directed graph. The signal interviewers are watching for is whether you can recognize hidden graph structure beneath a real-world story.

Cycle detection in dependency graphs is something real systems do constantly. Build systems (Make, Bazel, Gradle) detect circular dependencies between targets and refuse to build. Package managers (npm, pip, apt) reject circular dependency chains. Spreadsheet engines detect circular cell references. Task schedulers validate that job dependencies form a valid execution order. Compilers check for circular type definitions and module imports. Any time you have items that depend on each other and you need to know whether a valid processing order exists, you're solving exactly this problem.

Problem Statement

There are numCourses courses labeled from 0 to numCourses - 1.

You are given an array prerequisites, where prerequisites[i] = [a, b] means you must take course b before course a.

Return true if it is possible to finish all courses, false otherwise.

Examples:

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

result → true (take 0, then 1).

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

result → false (each needs the other first — impossible).

1. Clarify Requirements Before Jumping Into Code

Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would change our approach.

Input: an integer numCourses and a list of prerequisite pairs.

Output: a boolean — can all courses be completed?

Details to clarify:

What does [a, b] mean exactly? a is the class, b is a prerequisite. You must take b before a. The direction matters, and it's easy to flip by accident.
Are we asked for the actual order, or just whether one exists? Just feasibility — a yes/no answer. (A variant, "Course Schedule II," asks for the order itself.)
Can a course have multiple prerequisites? Yes.
Can the prerequisite graph be disconnected? Yes — some courses may have no relationship to others.
Can a course be its own prerequisite ([a, a])? No. That would be a self-cycle, which makes finishing impossible.

The thing to flag is what makes finishing impossible. We'll dive into that question more deeply in the Brainstorming step.

2. Identify the Category of the Question

A few signals jump out:

Items depend on other items (prerequisites).
The dependencies have direction (b before a, not the reverse).
We want to know whether a valid ordering exists.

That combination — directed dependencies, ordering feasibility — places this squarely in the directed graph / topological ordering family. And the specific question "can all items be ordered respecting dependencies?" is equivalent to "is the dependency graph free of cycles?" A directed graph has a valid topological ordering if and only if it has no cycles (it's a DAG — directed acyclic graph). Same family as Alien Dictionary, Course Schedule II, and any build-order or dependency-resolution problem.

3. Brute Force Solution

Let's think about the most naive approach to understand the problem. We could try to construct a valid ordering directly: try every possible permutation of courses, and for each one, check whether it respects all prerequisites.

for each permutation of courses:
    if permutation respects all prerequisites:
        return true
return false

There are n! permutations, and checking each takes O(e) time (e is the number of edges in the permutation). That's factorial time — completely infeasible beyond a handful of courses.

The brute force does teach us something useful, though. When we ask "does a valid ordering exist?", we're really asking "is there any way to lay these courses out so every prerequisite comes before the course that needs it?" And the only thing that could make that impossible is a circular dependency. If there's no cycle, we can always find an order (process courses with no remaining prerequisites first, then the ones they unblock, and so on). So the feasibility question reduces to a cycle question — and detecting a cycle is far cheaper than trying every ordering.

4. Brainstorm More Solutions

Step 1: Reframe the problem as a graph

Let's make the graph view explicit. Each course is a node. Each prerequisite pair [a, b] ("take b before a") becomes a directed edge b → a.

Now restate the question in graph terms: "Can all courses be finished?" becomes "Can we process every node in an order that respects the edge directions?" And as we established, that's possible if and only if the graph has no directed cycle.

So the problem has fully transformed: detect whether a directed graph contains a cycle. If it does, return false (impossible). If it doesn't, return true. We've replaced a vague scheduling question with a precise, well-studied graph question.

Step 2: How do we detect a cycle in a directed graph?

This is where it gets interesting, because cycle detection in a directed graph is trickier than it first appears. Let's start with the obvious idea and see where it breaks.

The natural first attempt: do a DFS, and if we ever reach a node we've already visited, declare a cycle. That's how cycle detection works in many simpler settings, so let's test it. Take this graph: node 0 points to both node 1 and node 2, and both node 1 and 2 point to node 3. We DFS from node 0, go down through node 1 to node 3, then back up and down through node 2 — and reach node 3 again.

Our naive rule fires: "already visited 3, so there's a cycle!" But there's no cycle here. It's a diamond — two separate paths that happen to converge on 3. You can absolutely finish these courses (0, then 1 and 2, then 3). So "I've seen this node before" produces false positives. It's too blunt.

So let's think harder about what a cycle actually is. A cycle means I can start at some node, follow edges, and arrive back where I started. The defining feature isn't just "I revisited a node" — it's "I revisited a node that I'm still in the middle of exploring."

Let's walk through the difference. In the diamond, when I reach node 3 the second time (via node 2), I had already finished with node 3 the first time — I went down to it, found nothing below, and came back up. It's behind me, done. But in a real cycle like 0 → 1 → 2 → 0, when I follow the edge from node 2 back to node 0, node 0 is still open — I'm currently inside the DFS call for node 0, exploring its descendants, and one of those descendants just pointed back at it.

That's the distinction we need to capture: not "have I seen this node," but "is this node currently on the path I'm actively exploring — the chain of calls between the root and where I am right now?" An edge pointing to a node on that active path is called a back-edge, and a back-edge is exactly what a cycle looks like during a DFS. An edge to a node that's been fully finished, like the second arrival at 3 in the diamond, is harmless — it's just two paths meeting, not a loop. So our job isn't to track what we've seen; it's to track what's currently open on our path, and to fire only when an edge points back into that open chain.

Step 3: Three states instead of two

To capture that distinction, we can give each node a value to track one of three states instead of the usual visited/unvisited binary:

0 = unvisited: we haven't touched this node yet.
1 = visiting: this node is on our current DFS path — we've entered it but haven't finished exploring all its descendants.
2 = visited: we've completely finished this node and everything reachable from it.

Now the cycle test is precise. During DFS, if we reach a node that's in state visiting (1), we've found a back-edge to a node on our active path — that's a cycle. If we reach a node in state visited (2), it's already fully explored and led to no cycle, so we can safely skip it (it's the diamond case, not a cycle).

The three-state idea is the crucial upgrade over naive two-state visited tracking. Two states can't distinguish "on the current path" from "seen earlier on a different path," and that distinction is exactly what separates a cycle from a harmless convergence.

Step 4: Assemble the DFS

The algorithm:

Build an adjacency list from the prerequisite pairs.
Initialize every node to state 0 (unvisited).
For each node, if it's unvisited, run a DFS that looks for cycles.
In the DFS: mark the node "visiting," recurse into neighbors, and mark it "visited" when done. If we ever recurse into a "visiting" node, report a cycle.

hasCycle(node):
    # back-edge to active path → cycle
    if state[node] == 1: return true. 

    # already fully explored, no cycle here   
    if state[node] == 2: return false 

    state[node] = 1  # mark as on the current path
    for neighbor in graph[node]:
        if hasCycle(neighbor): return true
    state[node] = 2  # done — mark fully visited
    return false

The transition from "visiting" to "visited" happens after exploring all neighbors. That ordering matters: a node is only "fully visited" once we've confirmed everything reachable from it is cycle-free. While we're still exploring its descendants, it stays "visiting" so that any back-edge to it is correctly flagged.

Step 5: Walk through a cycle and a non-cycle

Cycle case: numCourses = 2, prerequisites [[1, 0], [0, 1]]. Edges: 0 → 1 and 1 → 0.

DFS from 0. Mark 0 "visiting." Recurse into neighbor 1.
- Mark 1 "visiting." Recurse into neighbor 0.
  - 0 is in state "visiting" → cycle detected. Return true up the chain.
canFinish returns false. Correct — the two courses each require the other.

Non-cycle case: numCourses = 3, prerequisites [[2, 1], [1, 0]]. Edges: 1 → 2 and 0 → 1.

DFS from 0. Mark 0 "visiting." Recurse into neighbor 1.
- Mark 1 "visiting." Recurse into neighbor 2.
  - Mark 2 "visiting." No neighbors. Mark 2 "visited." Return false.
- Mark 1 "visited." Return false.
Mark 0 "visited." Return false.
DFS from 1: already "visited," skip. DFS from 2: already "visited," skip.
canFinish returns true. Correct — the chain 0 → 1 → 2 can be followed in order.

Notice how the three states prevented redundant work: once 1 and 2 were marked "visited" during the DFS from 0, the outer loop skipped them entirely.

Step 6: The other standard approach — Kahn's algorithm (BFS)

There's a second classic solution worth knowing: Kahn's algorithm, which detects cycles via BFS using indegrees (the number of prerequisites each course still has).

The idea: a course with zero remaining prerequisites can be taken immediately. Take it, then "remove" it from the graph, decrementing the indegree of every course that depended on it. This may free up new zero-prerequisite courses. Repeat. If we manage to process all n courses this way, there's no cycle. If we get stuck with courses remaining but none at zero indegree, those remaining courses form a cycle.

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] indegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    for (int[] p : prerequisites) {
        graph.get(p[1]).add(p[0]);
        indegree[p[0]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    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)) {
            if (--indegree[next] == 0) queue.offer(next);
        }
    }

    return processed == numCourses;
}

Both approaches are O(n + e). The DFS version detects cycles directly via the recursion stack, which some find more intuitive. Kahn's algorithm is iterative (no recursion-depth risk) and has the bonus that the order in which it processes courses is a valid topological order — handy if a follow-up asks for the actual schedule. I'd mention both and pick based on what the interviewer emphasizes.

Step 7: Complexity

Building the adjacency list takes O(n + e). The DFS visits each node once and traverses each edge once across the whole run (the three-state marking ensures no node is explored more than once), so the traversal is O(n + e).

Space is O(n + e) for the adjacency list, plus O(n) for the state array and O(n) for the recursion stack (or the queue, in Kahn's version). So O(n + e) overall.

This is optimal — we have to look at every course and every prerequisite at least once, so O(n + e) is the floor.

5. Discuss Trade-Offs Between Solutions

Approach	Time	Space	When I'd use it
Try all orderings	O(n!)	High	Never — but frames why we need cycle detection
DFS with three-state tracking	O(n + e)	O(n + e)	My default when the question is purely feasibility — direct cycle detection
Kahn's algorithm (BFS, indegrees)	O(n + e)	O(n + e)	When recursion depth is a concern, or when a follow-up wants the actual order

Both real approaches are optimal. DFS with three states is the cleanest explanation of cycle detection; Kahn's algorithm is iterative and doubles as a topological sort. Knowing both lets you adapt to whatever the interviewer pushes on.

6. Pseudocode

build adjacency list: edge b → a for each prerequisite [a, b]
state[node] = 0 for all nodes   # 0 = unvisited, 1 = visiting, 2 = visited

for each node:
    if state[node] == 0 and hasCycle(node):
        return false
return true

hasCycle(node):
    if state[node] == 1: return true    # back-edge to active path → cycle
    if state[node] == 2: return false   # already cleared

    state[node] = 1
    for neighbor in graph[node]:
        if hasCycle(neighbor): return true
    state[node] = 2
    return false

7. Edge Cases

Things to verify before claiming we're done:

No prerequisites at all → no edges, no cycles, return true. ✓
Single course, no prerequisites → trivially finishable, return true. ✓
Self-dependency [a, a] → creates edge a → a; DFS marks a "visiting," then recurses into a which is still "visiting" → cycle detected, return false. ✓
Multiple disconnected components → the outer loop starts a DFS from every unvisited node, so disconnected pieces all get checked. ✓
Long linear chain (0 → 1 → 2 → ... → n) → no cycle; DFS confirms feasibility. The recursion depth equals the chain length, which could be a concern for very long chains (Kahn's avoids this).
Diamond dependency (two paths converging) → not a cycle; the "visited" state correctly distinguishes convergence from a real cycle.

The self-dependency case is a nice one to mention — it's the simplest possible cycle, and it's where the three-state logic earns its keep most directly.

8. Full Code

import java.util.*;

public class CourseSchedule {

    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        // Build adjacency list: 
        // edge b -> a means "take b before a"
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
        }

        // 0 = unvisited, 
        // 1 = visiting (on current path), 
        // 2 = fully visited
        int[] state = new int[numCourses];

        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0 && hasCycle(i, graph, state)) {
                return false;
            }
        }

        return true;
    }

    private static boolean hasCycle(int course, List<List<Integer>> graph, int[] state) {
        // Reached a node already on our current DFS path — 
        // that's a back-edge, a cycle
        if (state[course] == 1) {
            return true;
        }
        // Already explored this node completely and 
        // found no cycle through it
        if (state[course] == 2) {
            return false;
        }

        state[course] = 1;  // mark as "on the current path"

        for (int next : graph.get(course)) {
            if (hasCycle(next, graph, state)) {
                return true;
            }
        }

        state[course] = 2;  // done exploring — safe, no cycle
        return false;
    }

    // Kahn's algorithm (BFS) alternative — iterative, also yields a topological order.
    public static boolean canFinishBFS(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] indegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
            indegree[p[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        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)) {
                if (--indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        // If we processed every course, there was no cycle
        return processed == numCourses;
    }
}

9. Test the Code

// Simple dependency: take 0, then 1
int[][] p1 = {{1, 0}};
System.out.println(canFinish(2, p1));  // true

// Direct cycle: 0 and 1 each require the other
int[][] p2 = {{1, 0}, {0, 1}};
System.out.println(canFinish(2, p2));  // false

// Linear chain: 0 → 1 → 2
int[][] p3 = {{2, 1}, {1, 0}};
System.out.println(canFinish(3, p3));  // true

// No prerequisites at all
System.out.println(canFinish(3, new int[][]{}));  // true

// Self-dependency: course 0 requires itself
int[][] p4 = {{0, 0}};
System.out.println(canFinish(1, p4));  // false

// Diamond (not a cycle): 0 → 1, 0 → 2, 1 → 3, 2 → 3
int[][] p5 = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
System.out.println(canFinish(4, p5));  // true

// Larger cycle: 0 → 1 → 2 → 0
int[][] p6 = {{1, 0}, {2, 1}, {0, 2}};
System.out.println(canFinish(3, p6));  // false

These hit the meaningful cases: a simple dependency, a direct two-node cycle, a linear chain, no prerequisites, a self-dependency (the smallest cycle), a diamond (which catches algorithms that mistake convergence for a cycle), and a larger three-node cycle.

10. Key Lessons

When a problem is phrased as a real-world scenario (scheduling, dependencies, ordering), look for the real problem hidden underneath. "Can I finish all courses given prerequisites?" transforms to "is this dependency graph acyclic?" Stripping the story down to its graph structure is the move that makes the problem tractable.
Cycle detection in a directed graph needs three states, not two. "Visited" alone can't distinguish a real cycle (a back-edge to a node on your current path) from a harmless convergence (two paths reaching the same already-finished node). The "visiting" state is what captures "currently on my path."
Mark a node "visiting" when you enter it and "visited" only after exploring all its descendants. The window in which a node is "visiting" is exactly the window in which a back-edge to it signals a cycle. Getting this ordering wrong breaks the detection.
Feasibility questions don't require constructing the actual solution. We answered "can all courses be finished?" without ever building a schedule — we just checked for cycles. Ask whether the problem wants existence or construction; the former is often much cheaper.
DFS and Kahn's algorithm both solve topological problems. DFS detects cycles directly via the recursion stack; Kahn's is iterative and produces a topological order as a byproduct. Knowing both lets you handle follow-ups like "now give me the actual order."

The thing that makes Course Schedule click is the recognition that a question about finishing tasks with dependencies is really a question about cycles in a directed graph, and that detecting those cycles requires distinguishing "on my current path" from "seen before." Once you train yourself to look past the story to the graph, an entire category of scheduling, ordering, and dependency problems collapses into "build the graph, check for a cycle."

Good Luck and Happy Coding!