Course Schedule

1. Problem & Core Objective

There are numCourses courses labelled 0 to numCourses − 1, and prerequisites[i] = [a, b] means you must take b before a. Return true if all courses can be finished.

numCourses = 2, prerequisites = [[1,0]]        →  true    (0 then 1)
numCourses = 2, prerequisites = [[1,0],[0,1]]  →  false   (circular)

Constraints: 1 <= numCourses <= 2000 · 0 <= prerequisites.length <= 5000 · pairs are distinct

What's actually being tested: recognising this as cycle detection in a directed graph. "Can all courses be finished" is exactly "is the prerequisite graph acyclic". The two standard algorithms — three-colour DFS and Kahn's topological sort — are both worth knowing, and the section's next question needs the ordering as well.

2. First-Principles Thought Process

Model it as a graph

Each course is a node. [a, b] is a directed edge b → a: b unlocks a.

The edge direction is a decision worth stating. b → a means "b comes first", which makes a topological order read naturally as a valid course sequence. Reversing it also works but flips every subsequent argument, so it's worth fixing the convention explicitly.

Why a cycle is exactly the failure

If courses form a cycle a → b → c → a, then each requires another that transitively requires it. No ordering can satisfy all of them.

And conversely, any directed acyclic graph has a topological order — so if there's no cycle, a valid schedule exists. The two conditions are equivalent, not merely related.

Two states are not enough

The instinct is a visited set: if a DFS reaches an already-visited node, declare a cycle.

That's wrong.

Consider A → B, A → C, B → C. Exploring from A: visit B, from B visit C, finish both. Back at A, visit C — already visited. But C isn't on A's current path; it was finished long ago. That's a cross-edge, which is perfectly legal in a DAG.

I verified this: a two-state check reports a cycle on that graph, and the correct answer is no cycle.

The three states

Reaching a GRAY node means looping back onto your own path — a genuine cycle. Reaching BLACK is fine.

The alternative: Kahn's algorithm

Repeatedly remove a node with in-degree 0 (no unmet prerequisites), decrementing its neighbours' in-degrees. If you can remove all n nodes, the graph is acyclic; if you get stuck, the remainder contains a cycle.

This is BFS-shaped, needs no recursion, and produces the ordering as a by-product — which is exactly what question 9 asks for.

3. Solution Paths

Approach 1 — DFS with only a visited set (broken, worth showing)

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = buildAdj(numCourses, prerequisites);
    boolean[] visited = new boolean[numCourses];
    for (int i = 0; i < numCourses; i++)
        if (!visited[i] && hasCycle(adj, i, visited)) return false;
    return true;
}

private boolean hasCycle(List<List<Integer>> adj, int u, boolean[] visited) {
    if (visited[u]) return true;                   // WRONG: any revisit looks like a cycle
    visited[u] = true;
    for (int v : adj.get(u)) if (hasCycle(adj, v, visited)) return true;
    return false;
}

• Time O(V + E) · Correct: no

Counter-questions on this approach

⭐ "Give me a graph where this reports a cycle that doesn't exist."

A → B, A → C, B → C — a diamond with no cycle. From A, visit B, then C, both marked. Back at A, visit C again: already visited, so it reports a cycle.

But C was never on A's current path in a way that loops back — it was fully explored and returned. That's a cross-edge, and DAGs are full of them.

I confirmed both behaviours: the two-state check says cycle, the three-colour check says no cycle. The correct answer is no cycle.

⭐ "So what distinction is missing?"

"Visited" conflates "currently on my path" with "already finished". Only the first is a cycle.

Adding a third state separates them: GRAY for in-progress, BLACK for done. Reaching GRAY is a back-edge (cycle); reaching BLACK is a cross- or forward-edge (fine).

"Could you fix it by clearing visited on the way out?"

That does work — it turns visited into "on the current path", which is the GRAY set. But then finished nodes are re-explored from every ancestor, and the complexity blows up to exponential on a dense DAG.

The three-state version keeps BLACK precisely so finished work isn't repeated. You need both flags for correctness and efficiency.

Approach 2 — Three-colour DFS (optimal)

private static final int WHITE = 0, GRAY = 1, BLACK = 2;

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    for (int[] p : prerequisites) adj.get(p[1]).add(p[0]);       // b -> a

    int[] color = new int[numCourses];
    for (int i = 0; i < numCourses; i++)
        if (color[i] == WHITE && hasCycle(adj, i, color)) return false;
    return true;
}

private boolean hasCycle(List<List<Integer>> adj, int u, int[] color) {
    color[u] = GRAY;                                  // now on the current path
    for (int v : adj.get(u)) {
        if (color[v] == GRAY) return true;            // back-edge — cycle
        if (color[v] == WHITE && hasCycle(adj, v, color)) return true;
        // BLACK: already finished, safe to ignore
    }
    color[u] = BLACK;                                 // done; leaves the current path
    return false;
}

• Time O(V + E) · Space O(V + E) for the adjacency list, O(V) recursion

Counter-questions on this approach

⭐ "Why is reaching GRAY a cycle but reaching BLACK is not?"

GRAY means the node is an ancestor on the current DFS path — the recursion entered it and hasn't returned. So an edge to it closes a loop back onto the path I'm standing on. That's a cycle by definition.

BLACK means the node was fully explored and returned, so it's not on my path. An edge to it just re-enters a region already proven acyclic.

The colours are literally "on my path" versus "already done", which is the distinction two states can't express.

⭐ "Why does color[u] = BLACK come after the loop?"

Because a node is only finished once all its descendants are. Marking BLACK before the loop would make it look finished while still being explored, so a genuine back-edge would be misread as a safe cross-edge — and cycles would go undetected.

GRAY on entry, BLACK on exit. The two assignments bracket the recursion, which is exactly what makes GRAY mean "in progress".

"Why loop over all nodes at the top level?"

The graph may be disconnected. A cycle can sit in a component unreachable from node 0, so every WHITE node must be tried as a starting point. The color[i] == WHITE guard means already-explored components aren't re-traversed.

"Why adj.get(p[1]).add(p[0]) rather than the reverse?"

Because [a, b] means b must come first, so the edge points b → a. With that convention a topological order reads as a valid course sequence, and "in-degree 0" means "no unmet prerequisites".

The reverse convention is also workable, but then everything downstream inverts. Worth fixing deliberately rather than by accident.

"What's the recursion depth?"

Up to V = 2000 on a path-shaped graph — safe in Java. At 10^5 nodes I'd switch to Kahn's, which is iterative.

"Does this handle self-loops and duplicate edges?"

A self-loop a → a is caught: a is GRAY when its own edge is examined. Duplicate edges are harmless — the second one hits a BLACK or GRAY node and behaves identically. The constraints say pairs are distinct, but the algorithm doesn't rely on it.

Approach 3 — Kahn's algorithm (BFS topological sort)

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

    for (int[] p : prerequisites) {
        adj.get(p[1]).add(p[0]);
        inDegree[p[0]]++;                              // a has one more prerequisite
    }

    Queue<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++)
        if (inDegree[i] == 0) q.offer(i);              // no prerequisites — can take now

    int taken = 0;
    while (!q.isEmpty()) {
        int course = q.poll();
        taken++;
        for (int next : adj.get(course))
            if (--inDegree[next] == 0) q.offer(next);  // its last prerequisite is met
    }

    return taken == numCourses;                         // stuck early means a cycle
}

Trace — numCourses = 4, prerequisites [[1,0],[2,0],[3,1],[3,2]]:

taken == 4 → true ✓

• Time O(V + E) · Space O(V + E)

Counter-questions on this approach

⭐ "Why does taken < numCourses prove a cycle?"

A node only enters the queue when its in-degree reaches 0 — all prerequisites satisfied. If the queue empties with nodes left over, every remaining node still has an unmet prerequisite.

Follow those prerequisites backwards: each remaining node points to another remaining node, and since the set is finite, that chain must repeat. A repeated node in a chain of dependencies is a cycle.

So getting stuck and having a cycle are equivalent, which is why counting is sufficient proof.

⭐ "How does this compare to the DFS version?"

Same O(V + E), but iterative — no stack depth limit, which matters at large V. And it produces the topological order as a by-product: the order nodes are dequeued is a valid schedule.

That's exactly what question 9 asks for, so Kahn's answers both questions with one algorithm. I'd default to it for that reason.

"Why --inDegree[next] == 0 rather than decrementing and checking separately?"

Just compactness — pre-decrement then compare. Checking inDegree[next] == 0 after a separate decrement is identical; combining them avoids a stale-read bug where you decrement and then test the wrong variable.

"Can a node be enqueued twice?"

No. In-degree reaches exactly 0 once, since each incoming edge is decremented exactly once. After that it goes negative only if an edge were processed twice, which can't happen.

Comparison

4. Why the Optimal Wins

The two-state version is simply wrong — it can't distinguish a back-edge from a cross-edge, and I confirmed it misreports A→B, A→C, B→C.

Between the two correct algorithms, both are O(V + E). Kahn's wins on two practical counts: it's iterative, so no stack limit, and it yields the topological order directly — which is what the next question needs.

The three-colour DFS is worth knowing cold anyway, because the GRAY/BLACK distinction generalises to any back-edge detection.

The framing worth keeping:

"Can all courses be finished" is "is the graph acyclic". Two states can't detect a cycle — you need GRAY for "on my current path" and BLACK for "already finished", because only the first is a back-edge.

5. Java Prerequisites

Adjacency list from edge pairs

List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] p : prerequisites) adj.get(p[1]).add(p[0]);   // b -> a

Three-colour DFS — GRAY on entry, BLACK on exit, bracketing the recursion.

Kahn's skeleton

for each node with inDegree 0: q.offer(node);
while (!q.isEmpty()) {
    int u = q.poll(); taken++;
    for (int v : adj.get(u)) if (--inDegree[v] == 0) q.offer(v);
}
return taken == n;

ArrayDeque for the queue. int[] color rather than an enum — smaller and faster, and three states fit comfortably.

6. Interview Communication Guide

Clarifying questions: Does [a, b] mean b before a (yes — confirm, the direction flips everything)? Can the graph be disconnected (yes)? Are there self-loops (constraints say distinct pairs, but a self-loop would be a cycle)? Do I need the ordering or just a boolean (boolean here; question 9 wants the order)?

The pitch

"Each course is a node, and [a, b] is a directed edge b → a meaning b unlocks a. Then 'can all courses be finished' is exactly 'is this graph acyclic' — a cycle means a set of courses each requiring another that transitively requires it, so no ordering works. And conversely any DAG has a topological order, so the two conditions are equivalent.

The trap is thinking a visited set is enough. It isn't. Take A → B, A → C, B → C — no cycle. Exploring from A, you visit B, then C, both marked. Back at A you reach C again, already visited, and a two-state check calls that a cycle. But C was finished, not on A's current path — that's a cross-edge, and DAGs are full of them.

So you need three states. WHITE unvisited, GRAY on the current path, BLACK fully explored. Reaching GRAY is a back-edge and a genuine cycle; reaching BLACK is fine. GRAY is set on entry and BLACK on exit, bracketing the recursion — marking BLACK early would make a real back-edge look safe.

I'd actually submit Kahn's algorithm instead. Repeatedly take a course with in-degree 0 — no unmet prerequisites — and decrement its dependents. If you take all n, it's acyclic; if you get stuck, everything remaining still has an unmet prerequisite, and following those backwards in a finite set must repeat, which is a cycle.

Two reasons to prefer it: it's iterative, so no stack depth concern, and it produces the topological order as a by-product — which is exactly what the follow-up question asks for.

Both are O(V + E). I'd also loop over all nodes at the top level, since the graph can be disconnected and a cycle might sit in an unreachable component."

Edge cases to volunteer:

Name the diamond. It's the case that separates a correct solution from a two-state one, and the two-state version fails it while passing every simple cycle test.

7. Follow-Up Questions — Modified Constraints

⭐ "Return a valid order, not just whether one exists."

Question 9. With Kahn's it's free — collect the dequeue order. With DFS it's the reverse postorder: append each node as it turns BLACK, then reverse. Both O(V + E).

⭐ "Return ALL valid orderings."

Exponentially many in general, so it becomes backtracking: at each step choose any in-degree-0 node, recurse, and undo. That's the Backtracking template over a changing candidate set. Worth naming that counting linear extensions of a DAG is #P-complete.

"Find the minimum number of semesters if unlimited courses can be taken in parallel."

The number of levels in Kahn's BFS — process the queue level by level, exactly like Rotting Oranges. That's the longest path in the DAG.

"Detect a cycle in an UNDIRECTED graph instead."

Different problem. Three colours don't apply, because every undirected edge looks like a back-edge to its own parent. Track the parent and ignore it, or use union-find — which is question 10's approach.

"What if there were 10^5 courses?"

The DFS would risk overflow on a long chain, so Kahn's is the clear choice. The adjacency list is fine, though List<List<Integer>> boxes every id — for that scale, a flat int[] CSR representation would be far leaner.

"Which single prerequisite, if removed, would make the schedule feasible?"

Find a cycle, then try removing each of its edges and re-testing — O(E · (V + E)) naively. Any feasibility-restoring edge must lie on every cycle, which narrows the candidates considerably. Worth noting that identifying a minimum feedback arc set in general is NP-hard.