Course Schedule II: return a valid topological order

• Course Schedule II extends cycle detection to produce an actual topological order.
• Kahn's algorithm emits courses in the order their in-degree reaches zero, respecting every prerequisite.
• Completeness check is whether the emitted count equals the total number of courses.
• Any valid order is acceptable; the algorithm may produce different orders depending on queue behavior.
• Time is O(V + E); space is O(V + E) for the adjacency list and output.

What is Course Schedule II?

Given courses numbered 0 to numCourses-1 and prerequisite pairs, return any valid ordering in which all courses can be taken. If no valid ordering exists because of a cycle, return an empty array. This extends the boolean feasibility check of Course Schedule I into producing the actual order.

package com.bank.service;

import java.util.*;

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

        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }

        int[] order = new int[numCourses];
        int idx = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            order[idx++] = course;
            for (int next : adj.get(course)) {
                if (--inDegree[next] == 0) queue.offer(next);
            }
        }
        return idx == numCourses ? order : new int[0];
    }
}

Why does Kahn's algorithm produce a valid order?

A course is emitted only when all its prerequisites have been processed, because that is exactly when its in-degree reaches zero. This guarantees every prerequisite appears before its dependent in the output. The order respects all edges in the directed graph.

Prerequisites: [[1,0], [2,0], [3,1], [3,2]]
Meaning: 0→1, 0→2, 1→3, 2→3

In-degrees: [0:0, 1:1, 2:1, 3:2]

Step 1: Queue=[0], emit 0, decrement 1 and 2
Step 2: Queue=[1,2], emit 1, decrement 3
Step 3: emit 2, decrement 3
Step 4: Queue=[3], emit 3

Order: [0, 1, 2, 3] (valid topological order)

How does this relate to Course Schedule I?

Course Schedule I asks "can all courses be finished?" and returns boolean. Course Schedule II asks "in what order?" and returns the order array. The algorithm is identical; only the return type differs. The completeness check (idx == numCourses) serves both: it is the boolean answer for I and the validity check for II.

| Aspect | Course Schedule I | Course Schedule II |
|--------|------------------|-------------------|
| Question | Can all be finished? | What order? |
| Return | boolean | int[] or empty |
| Algorithm | Same Kahn's pass | Same Kahn's pass |
| Cycle indication | false | empty array |

Why can any zero-in-degree node be picked first?

Topological ordering is not unique unless the graph is a single chain. Any node with zero in-degree can be processed next without violating the ordering constraint. Whether you use a queue (FIFO), a stack (LIFO), or a priority queue (lexicographic), the result is a valid topological order.

What about DFS-based topological sort?

DFS topological sort records nodes in reverse finish order. After DFS completes, reversing the finish order gives a valid topological order. This approach also detects cycles via the three-color method.

public int[] findOrderDFS(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    for (int[] pre : prerequisites) adj.get(pre[1]).add(pre[0]);

    int[] color = new int[numCourses];
    List<Integer> order = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        if (color[i] == 0 && hasCycle(i, adj, color, order))
            return new int[0];
    }
    Collections.reverse(order);
    return order.stream().mapToInt(Integer::intValue).toArray();
}

private boolean hasCycle(int node, List<List<Integer>> adj,
                          int[] color, List<Integer> order) {
    color[node] = 1;
    for (int next : adj.get(node)) {
        if (color[next] == 1) return true;
        if (color[next] == 0 && hasCycle(next, adj, color, order))
            return true;
    }
    color[node] = 2;
    order.add(node);  // add in finish order
    return false;
}

What are edge cases?

• Zero courses: return empty array (nothing to order).
• No prerequisites: every course has in-degree 0, any permutation is valid.
• Single prerequisite chain 0→1→2→...→n: only one valid order.
• Cycle: return empty array.

// Edge case: no prerequisites
// All in-degrees are 0, all enqueued immediately
// Output: [0, 1, 2, ...] in queue order

What are common mistakes?

The first mistake is returning the partial order instead of an empty array when a cycle is detected. The second mistake is building edges in the wrong direction. The third mistake is forgetting to handle disconnected components.

// WRONG: returns partial order on cycle
return order;  // should check completeness first

// CORRECT: returns empty array on cycle
return idx == numCourses ? order : new int[0];

What should a senior engineer know?

At the National Bank of India, the onboarding engine needed a concrete execution order for dependent steps, not merely a feasibility verdict. Kahn's algorithm emitted each step as its prerequisites were met, producing a runnable plan. When a misconfiguration introduced a cycle, the short emitted count made the planner return an empty order so the engine refused to run a plan that could never complete. The same approach was used for regulatory-filing workflows where filing order had to respect inter-filing dependencies.