Course Schedule II

1. Problem & Core Objective

Same setup as question 8, but return a valid ordering of all courses. If impossible, return an empty array. Any valid order is acceptable.

numCourses = 2, prerequisites = [[1,0]]              →  [0,1]
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
                                                     →  [0,1,2,3] or [0,2,1,3]
numCourses = 2, prerequisites = [[1,0],[0,1]]        →  []

Constraints: 1 <= numCourses <= 2000 · 0 <= prerequisites.length <= numCourses · (numCourses − 1) · pairs are distinct

What's actually being tested: that question 8's algorithm already computed this. Kahn's dequeue order is a topological order; the DFS's reverse postorder is another. The question is whether you recognise that detecting a cycle and producing an ordering are the same computation.

2. First-Principles Thought Process

The ordering was always there

Question 8 asked whether the graph is acyclic. Both algorithms produce an ordering as a by-product:

So this question needs one extra line, not a new algorithm.

Why Kahn's dequeue order is valid

A node is enqueued only when its in-degree hits 0 — every prerequisite already dequeued. So when a node is emitted, everything it depends on is already in the output.

That's the definition of a topological order, and it holds by construction rather than needing a proof afterwards.

Why DFS reverse postorder is valid

A node turns BLACK only after all its descendants have. So in postorder, every node appears after everything it points to. Reversing puts it before them — which is what a prerequisite order requires.

The subtlety: you must append on exit (BLACK), not on entry. Appending on entry gives preorder, which is not a topological order.

Detecting failure

Same as before. Kahn's: if fewer than numCourses nodes are emitted, there's a cycle — return []. DFS: if a GRAY node is reached, abandon and return [].

Which to write

Kahn's, for the same reasons as question 8: iterative, no stack limit, and the ordering falls out directly without a reversal step.

3. Solution Paths

Approach 1 — Repeatedly scan for an available course (brute force)

public int[] findOrder(int numCourses, int[][] prerequisites) {
    int[] inDegree = new int[numCourses];
    List<List<Integer>> adj = buildAdj(numCourses, prerequisites, inDegree);

    boolean[] taken = new boolean[numCourses];
    int[] order = new int[numCourses];
    int idx = 0;

    for (int round = 0; round < numCourses; round++) {
        int next = -1;
        for (int i = 0; i < numCourses; i++)                 // rescan every round
            if (!taken[i] && inDegree[i] == 0) { next = i; break; }

        if (next == -1) return new int[0];                    // stuck — cycle
        taken[next] = true;
        order[idx++] = next;
        for (int v : adj.get(next)) inDegree[v]--;
    }
    return order;
}

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

Counter-questions on this approach

⭐ "Where's the waste?"

The inner scan. Every round walks all V nodes looking for one with in-degree 0 — O(V²) total, which at 2000 courses is 4 × 10^6. Survivable, but unnecessary.

A node becomes available at a precise, known moment: when its last prerequisite is removed. Kahn's enqueues it right then, so the next available node is always at the queue's head. The scan rediscovers what the decrement already knew.

"It's still O(V²), not exponential. Is it really a problem?"

Not at these constraints. The objection is that the queue version is both faster and shorter — the scan is pure overhead with no compensating simplicity.

"Does the taken[] array do anything the in-degree doesn't?"

Yes, unfortunately: after a node is emitted its in-degree stays 0, so without taken it would be picked again every round. Kahn's avoids this because a node is enqueued exactly once, so no separate flag is needed. One fewer piece of state to keep consistent.

Approach 2 — Kahn's algorithm (optimal)

public int[] findOrder(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]);                    // b -> a
        inDegree[p[0]]++;
    }

    Queue<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++)
        if (inDegree[i] == 0) q.offer(i);

    int[] order = new int[numCourses];
    int idx = 0;

    while (!q.isEmpty()) {
        int course = q.poll();
        order[idx++] = course;                      // the dequeue order IS the answer
        for (int next : adj.get(course))
            if (--inDegree[next] == 0) q.offer(next);
    }

    return idx == numCourses ? order : new int[0];  // stuck early means a cycle
}

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

idx == 4 → return [0,1,2,3] ✓

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

Counter-questions on this approach

⭐ "Prove the dequeue order is a valid topological order."

A node is enqueued only when its in-degree reaches 0, which happens only after every incoming edge has been decremented — and each decrement happens when the source node is dequeued.

So by the time a node is emitted, all its prerequisites have already been emitted. That's exactly the topological property, and it holds by construction at every step rather than needing verification at the end.

⭐ "Why does idx < numCourses mean a cycle?"

The queue empties only when no remaining node has in-degree 0. So every remaining node still has an unmet prerequisite, which is itself remaining.

Follow those backwards: each remaining node points to another remaining node. In a finite set that chain must revisit a node, and a repeated node in a dependency chain is a cycle.

So "stuck" and "cyclic" are equivalent — counting the output is a complete proof, not a heuristic.

⭐ "The answer isn't unique. Does the queue choice matter?"

No — any in-degree-0 node is a legal next choice, so the queue's ordering only decides which valid answer you get. With [[1,0],[2,0],[3,1],[3,2]], both [0,1,2,3] and [0,2,1,3] are correct.

If a specific tie-break were required — lexicographically smallest, say — I'd swap the ArrayDeque for a PriorityQueue, at O((V + E) log V).

"Why build order as an int[] rather than a List?"

The size is known in advance, so an array avoids growth and the final toArray conversion. idx doubles as both the write position and the count of emitted nodes, which is what the cycle check needs.

"What if there are no prerequisites at all?"

Every in-degree is 0, so all nodes seed the queue and come out in index order. [0, 1, …, n−1] — valid, since there are no constraints to violate.

"Can inDegree go negative?"

No. Each edge is decremented exactly once, when its source is dequeued, and each node is dequeued at most once. So a node's in-degree reaches 0 exactly once and stops.

Approach 3 — DFS reverse postorder

public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = buildAdj(numCourses, prerequisites);
    int[] color = new int[numCourses];
    Deque<Integer> stack = new ArrayDeque<>();

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

    int[] order = new int[numCourses];
    for (int i = 0; i < numCourses; i++) order[i] = stack.pop();   // reverse postorder
    return order;
}

private boolean hasCycle(List<List<Integer>> adj, int u, int[] color, Deque<Integer> stack) {
    color[u] = 1;                                   // GRAY
    for (int v : adj.get(u)) {
        if (color[v] == 1) return true;
        if (color[v] == 0 && hasCycle(adj, v, color, stack)) return true;
    }
    color[u] = 2;                                   // BLACK
    stack.push(u);                                  // append on EXIT
    return false;
}

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

Counter-questions on this approach

⭐ "Why append on exit rather than on entry?"

Appending on entry gives preorder, which is not a topological order — a node would be emitted before its descendants are known, and a descendant might turn out to be a prerequisite of something already emitted.

Appending on exit gives postorder, in which every node appears after everything it points to. Reversing that puts each node before its dependents, which is what a prerequisite order requires.

The reversal is what the stack provides for free: pushing on exit and popping produces the reversal without a separate pass.

⭐ "Why is this correct even though the DFS visits components in arbitrary order?"

Because a topological order only constrains nodes connected by a path. Nodes in different components have no edges between them, so any relative order is valid.

Within a component, the postorder property guarantees the ordering. Across components, there's nothing to guarantee.

"Which would you submit?"

Kahn's. Same complexity, but iterative — no stack limit at large V — and the ordering comes out directly without needing the push-and-reverse trick. The DFS version is worth knowing because reverse postorder appears in Tarjan's SCC algorithm and elsewhere.

Comparison

4. Why the Optimal Wins

The brute force rescans all V nodes each round to find an available course, when the exact moment a course becomes available is already known — it's when its last prerequisite is removed. Kahn's enqueues it precisely then.

Against the DFS: identical complexity, but Kahn's is iterative and emits the order directly, where DFS needs the append-on-exit discipline plus a reversal.

And the larger point: this question needed no new algorithm. Question 8's cycle detection already computed the ordering; it just discarded it.

The framing worth keeping:

Kahn's dequeue order is a topological order by construction — a node is emitted only after every prerequisite has been. Detecting a cycle and producing the schedule are the same computation.

5. Java Prerequisites

Kahn's, emitting the order

while (!q.isEmpty()) {
    int u = q.poll();
    order[idx++] = u;                               // the dequeue order IS the answer
    for (int v : adj.get(u)) if (--inDegree[v] == 0) q.offer(v);
}
return idx == n ? order : new int[0];

DFS reverse postorder — push on exit, then pop:

color[u] = BLACK;
stack.push(u);        // after the loop, not before

Deque as a stack — push/pop on ArrayDeque. Faster than java.util.Stack, which is synchronised and legacy.

new int[0] for the empty result — the problem expects an empty array, not null.

6. Interview Communication Guide

Clarifying questions: Any valid order, or a specific one (any — it permits a plain queue)? What to return when impossible (empty array)? Does [a, b] mean b first (yes)? Must every course appear (yes — all numCourses of them)?

The pitch

"This is the previous question with one line changed — the ordering was already being computed, it was just thrown away.

With Kahn's algorithm, the order in which nodes are dequeued is a valid topological order. A node is only enqueued when its in-degree hits 0, meaning every prerequisite has already been dequeued and emitted. So by construction, each course appears after everything it depends on.

The failure check is the same: if fewer than numCourses nodes come out, the queue emptied with nodes remaining, and every remaining node still has an unmet prerequisite — which is itself remaining. Following those backwards in a finite set must repeat a node, and that's a cycle. So I return an empty array.

O(V + E).

The alternative is DFS producing reverse postorder — append each node as it turns BLACK, then reverse. That works because a node turns BLACK only after all its descendants, so postorder puts it after everything it points to, and reversing flips that. The subtlety is appending on exit, not entry; on entry gives preorder, which isn't topological.

I'd submit Kahn's: iterative, so no stack concern at 2000 nodes, and the order comes out directly without the reversal.

The answer isn't unique — any in-degree-0 node is a legal next pick, so the queue just decides which valid answer you get. If a lexicographically smallest order were required, I'd swap in a PriorityQueue at O((V+E) log V)."

Edge cases to volunteer:

Name the diamond and the no-prerequisites case. The first shows the answer isn't unique (so a test comparing against one fixed array is wrong); the second is where every node seeds at once.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the lexicographically smallest valid order."

Replace the ArrayDeque with a PriorityQueue<Integer>, so the smallest available course is always taken first. O((V + E) log V). The greedy is correct because any available node is legal, so taking the smallest never blocks a later choice.

⭐ "Minimum number of semesters, taking unlimited courses in parallel."

Process the queue level by level, counting rounds — the same snapshot idiom as Rotting Oranges. That number is the longest path in the DAG.

"Return all valid orderings."

Exponentially many, so it becomes backtracking over the set of currently-available nodes: choose one, decrement, recurse, undo. The Backtracking template over a changing candidate set. Counting them exactly is #P-complete.

"Each course takes a different amount of time; minimise total completion."

With unlimited parallelism it's the critical path — longest weighted path through the DAG, computed in O(V + E) by DP over the topological order. With limited parallelism it becomes job-shop scheduling, which is NP-hard.

"What if prerequisites were added incrementally and you re-queried?"

Recomputing is O(V + E) per query. Incremental topological order maintenance exists but is significantly more complex; for a few thousand nodes, recomputing is usually the right engineering call.

"What if there were 10^5 courses and 10^6 edges?"

Kahn's handles it — but List<List<Integer>> boxes every id and allocates a list per node. A flat CSR representation (int[] head, int[] next) is far leaner and avoids a million Integer objects.