Course Schedule II: A Step-by-Step Interview Walkthrough

Course Schedule II is the natural sequel to Course Schedule, and interviewers often pose it as a follow-up after you've solved the feasibility version. The shift is small to state but significant in practice: instead of asking whether all courses can be finished, it asks you to produce a valid order to finish them. That's the difference between detecting a cycle and performing a full topological sort. Candidates who only memorized "use three-state DFS to find cycles" get stuck, because cycle detection alone doesn't hand you an ordering. Candidates who understand why the absence of a cycle guarantees an ordering — and how to construct that ordering as they go — solve it cleanly. The signal here is whether you can move from "does a solution exist?" to "construct the solution," which is a recurring escalation across many interview problems.

Topological sorting is one of the most widely-used graph algorithms in production systems. Build tools compute the order to compile modules so dependencies build first. Package managers determine install order. Spreadsheet engines decide which cells to recalculate and in what sequence. Task schedulers order jobs whose outputs feed into other jobs. Even university course-planning software genuinely uses this to lay out multi-semester plans. Any time you have items with dependencies and need an actual execution order — not just a yes/no on feasibility — topological sort is the tool.

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 an array of course labels representing a valid order to complete all courses. If no valid order exists, return an empty array.

Example: 

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

result → one valid answer is [0, 1, 2, 3] (0 first, then 1 and 2, then 3).

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: an array giving a valid completion order, or an empty array if no order exists.

Details to clarify:

• What does [a, b] mean? Take b before a — same convention as Course Schedule. Easy to flip, so worth confirming.

• If multiple valid orders exist, does it matter which we return? No — any valid order is accepted.

• What do we return if it's impossible (a cycle exists)? An empty array.

• Can courses have no prerequisites? Yes — those can go anywhere a valid order allows, typically early.

• Can the graph be disconnected? Yes — independent groups of courses with no cross-dependencies.

The thing to flag is that this is a construction problem, not a decision problem. Course Schedule asked "is it possible?" — a boolean. This asks "show me how" — an actual ordering. That shift means cycle detection alone isn't enough; we need an algorithm that builds the order while also detecting impossibility. As we'll see, one classic algorithm does both at once.

2. Identify the Category of the Question

A few signals jump out:

• Items have directed dependencies.

• We need to produce a linear ordering that respects all dependencies.

• If the dependencies are contradictory (cyclic), no ordering exists.

That combination — directed dependencies, produce a valid linear order — is the definition of topological sorting. A topological sort of a directed acyclic graph (DAG) is an ordering of its nodes such that every edge points "forward" in the ordering. The problem is exactly: produce a topological sort, or report that none exists (because the graph has a cycle). Same family as Course Schedule, Alien Dictionary, and build-order problems.

3. Brute Force Solution

Let's think about the naive approach to understand the problem. We could generate every permutation of the courses and check each one against the prerequisites, returning the first valid permutation we find.

for each permutation of courses:
    if permutation respects all prerequisites:
        return permutation
return empty array

There are n! permutations, and checking each takes O(e) (number of edges). That's factorial time — we can do better.

4. Brainstorm More Solutions

Step 1: What makes a course "ready" to be scheduled?

Let's reframe the problem as a graph (each prerequisite [a, b] is an edge b → a, "b before a") and think about how we'd build an order by hand.

At the very start, which courses can we take? We'd have to pick from the list of classes that have exactly no prerequisites — nothing has to come before them. So we take all of those first.

Once we've taken all of those courses, what classes would we be able to take next? What classes would we have unlocked? We would have unblocked course whose only prerequisites were among the ones we just took. The dependencies for those classes have been satisfied, so they're ready to be taken. So we take those classes next, and the cycle repeats - taking a set of classes then unblocks still more courses, and so on.

This gives us a natural strategy: repeatedly find the courses whose prerequisites are all already scheduled, schedule them, and let that unlock the next wave. The question is how to track "are all of this course's prerequisites scheduled yet?" efficiently.

Step 2: Track readiness with indegree counts

So a class is ready to be taken when we met all of its prerequisites. That's a number we can track that — for each course, we count how many prerequisites it has. In graph terms, we're tracking its indegree (the number of incoming edges). A course with indegree 0 has no unmet prerequisites and is ready to schedule immediately.

When we schedule a course, we don't necessarily need to worry about tracking it in the graph anymore. We can add it to our result and remove it from the graph. Then, for every course that depended on it, we decrement that course's indegree by one, since one of its prerequisites is now satisfied. If any course's indegree drops to 0, it has just become ready, so we add it to our pool of available courses.

We've just discovered Kahn's algorithm, and it maps perfectly onto the manual process from Step 1:

1. Compute every course's indegree.

2. Put all indegree-0 courses into a queue (the initially-ready courses).

3. Repeatedly: pull a course from the queue, append it to the result order, and decrement the indegree of each course that depended on it. Any course that hits indegree 0 joins the queue.

4. Continue until the queue is empty.

The queue holds exactly the courses that are ready to be scheduled right now. Each course enters the queue precisely when its last prerequisite gets scheduled.

Step 3: Where does cycle detection come in for free?

Now let's think about the failure condition. What happens if the graph has a cycle — say, course X requires Y and Y requires X?

If we think about it in terms of indegrees for each course, neither X nor Y can ever reach indegree 0, because each is always waiting on the other. They'll never enter the queue. So when the algorithm finishes (queue empties), X and Y — and anything depending on them — will be missing from the result.

That gives us a built-in cycle check: if we successfully scheduled all numCourses courses, there was no cycle. If we scheduled fewer, the leftover courses form a cycle and no valid order exists. We don't need a separate cycle-detection pass — the construction process detects impossibility as a side effect. If the result has fewer than numCourses entries, we return an empty array.

This is why Kahn's algorithm is such a satisfying fit for this problem. The same machinery that builds the order also proves whether an order is possible.

Step 4: Walk through an example

Let's trace numCourses = 4, prerequisites [[1,0],[2,0],[3,1],[3,2]]. Edges: 0→1, 0→2, 1→3, 2→3.

Indegrees: course 0 has 0, course 1 has 1 (from 0), course 2 has 1 (from 0), course 3 has 2 (from 1 and 2).

• Initial queue: [0] (only course 0 has indegree 0).

• Pop 0. Result: [0]. Decrement neighbors 1 and 2 → both drop to 0. Queue: [1, 2].

• Pop 1. Result: [0, 1]. Decrement neighbor 3 → drops to 1. Queue: [2].

• Pop 2. Result: [0, 1, 2]. Decrement neighbor 3 → drops to 0. Queue: [3].

• Pop 3. Result: [0, 1, 2, 3]. No neighbors. Queue empty.

Scheduled 4 courses out of 4 → valid. Return [0, 1, 2, 3].

Notice that if we'd popped 2 before 1 (the queue order is up to us), we'd get [0, 2, 1, 3] — also valid. Multiple correct answers exist, which the problem allows.

Now a cycle case: numCourses = 2, prerequisites [[1,0],[0,1]]. Edges 0→1 and 1→0. Both courses have indegree 1, so the initial queue is empty. The loop never runs. Result has 0 entries, which is fewer than 2 → return empty array. The cycle blocked everything from the start.

Step 5: The DFS alternative

There's a second classic approach: DFS postorder. We run a depth-first search, and after finishing all of a node's descendants, prepend the node to the order (or push it onto a stack and reverse at the end). Nodes that finish later in the DFS belong earlier in the topological order, which is why we reverse.

DFS topo sort also needs the three-state cycle detection from Course Schedule (unvisited / visiting / visited) to handle the "no valid order" case — if we hit a node that's currently "visiting," there's a cycle and we bail.

Both approaches are O(n + e). I generally prefer Kahn's algorithm for this problem because the cycle check falls out of the result length naturally, with no separate state machine to manage. DFS is a bit more compact to write but requires interleaving the ordering logic with cycle detection, which is more error-prone under pressure. I'd mention both and lead with Kahn's.

Step 6: Complexity

Building the adjacency list and indegree array takes O(n + e). In the main loop, each course is enqueued and dequeued exactly once (O(n) total), and each edge is processed exactly once when we decrement the indegree of the course it points to (O(e) total). So the loop is O(n + e). Total time: O(n + e).

Space is O(n + e) for the adjacency list, plus O(n) for the indegree array, the queue, and the result. So O(n + e) overall.

This is optimal — we must examine 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 permutations	O(n! × e)	O(n)	Never — but frames why we need a structural approach
Kahn's algorithm (BFS, indegrees)	O(n + e)	O(n + e)	My default — builds the order and detects cycles in one pass
DFS postorder + three-state cycle detection	O(n + e)	O(n + e)	Compact, but interleaves ordering and cycle logic; more error-prone

Both real approaches are optimal. Kahn's algorithm is my preference here because the "no valid order" case is detected automatically by checking the result length — no separate cycle-detection bookkeeping required.

6. Pseudocode

build adjacency list: edge b → a for each prerequisite [a, b]
compute indegree[node] for every node

queue = all nodes with indegree 0
result = empty list

while queue not empty:
    node = queue.pop()
    append node to result
    for neighbor in graph[node]:
        indegree[neighbor]--
        if indegree[neighbor] == 0:
            queue.add(neighbor)

if result.size != numCourses:
    return empty array       # a cycle blocked some courses

return result

7. Edge Cases

Things to verify before claiming we're done:

• No prerequisites at all → every course has indegree 0, all start in the queue, result is some valid permutation of all courses. ✓

• Single course → indegree 0, scheduled immediately, result is [0]. ✓

• A cycle → cyclic courses never reach indegree 0, result is shorter than numCourses, return empty array. ✓

• Disconnected groups → each independent group's indegree-0 courses seed the queue; all groups get processed. ✓

• Multiple valid orders → the queue's pop order determines which valid order we produce; any is acceptable.

• Self-dependency [a, a] → course a has indegree 1 from itself and can never reach 0, so it's excluded → empty array. ✓

The result-length check at the end is what handles every cycle case uniformly. If index != numCourses, something was unreachable, and the only thing that makes a course permanently unreachable is a cycle.

8. Full Code

import java.util.*;

public class CourseScheduleII {

    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        // Build adjacency list (edge b -> a) and indegree array
        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]]++;
        }

        // Seed the queue with every course that has no 
        // prerequisites
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }

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

        while (!queue.isEmpty()) {
            int course = queue.poll();
            order[index++] = course;

            // Scheduling this course satisfies one 
            // prerequisite for each dependent
            for (int next : graph.get(course)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.add(next);   // newly unblocked — ready to schedule
                }
            }
        }

        // If we couldn't schedule every course, 
        // a cycle blocked the rest
        if (index != numCourses) {
            return new int[0];
        }

        return order;
    }
}

9. Test the Code

// Simple ordering
int[][] p1 = {{1, 0}};
System.out.println(Arrays.toString(findOrder(2, p1)));   // [0, 1]

// Cycle → empty array
int[][] p2 = {{1, 0}, {0, 1}};
System.out.println(Arrays.toString(findOrder(2, p2)));   // []

// Multiple valid answers — both 0 and 1 must precede 2
int[][] p3 = {{2, 0}, {2, 1}};
System.out.println(Arrays.toString(findOrder(3, p3)));   // [0, 1, 2] or [1, 0, 2]

// No prerequisites — any order is valid
System.out.println(Arrays.toString(findOrder(3, new int[][]{})));  // [0, 1, 2]

// Diamond dependency
int[][] p4 = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
System.out.println(Arrays.toString(findOrder(4, p4)));   // [0, 1, 2, 3] (one valid order)

// Self-dependency → impossible
int[][] p5 = {{0, 0}};
System.out.println(Arrays.toString(findOrder(1, p5)));   // []

// Three-node cycle
int[][] p6 = {{1, 0}, {2, 1}, {0, 2}};
System.out.println(Arrays.toString(findOrder(3, p6)));   // []

These hit the meaningful cases: a simple ordering, a two-node cycle, a case with multiple valid answers, no prerequisites, a diamond dependency, a self-dependency, and a three-node cycle. When verifying outputs with multiple valid answers, check that the constraints hold (every prerequisite precedes its dependent) rather than expecting one exact array.

10. Key Lessons

• Moving from a decision problem ("does a solution exist?") to a construction problem ("produce the solution") often requires a different algorithm, not just a tweak. Course Schedule needed cycle detection; Course Schedule II needs a full topological sort. Recognize when a follow-up has escalated the ask.

• Kahn's algorithm builds a topological order by repeatedly scheduling whatever is currently unblocked (indegree 0). The indegree count is just an efficient way to track "how many prerequisites does this item still have?"

• Many topological-ordering problems accept multiple valid answers. When testing, verify the constraints (every dependency precedes its dependent) rather than matching one specific output. Hard-coding a single expected array leads to false test failures.

The thing that makes Course Schedule II click is understanding why repeatedly scheduling the unblocked items produces a valid order, and why the items you can never unblock are exactly the ones trapped in a cycle. Once you see that the construction process and the cycle check are the same process viewed two ways, the algorithm stops being something you recall and becomes something you can reconstruct from first principles. And that reconstruction skill is what carries over to every other dependency-ordering problem you'll face.

Good Luck and Happy Coding!