A registrar is asked for one legal enrollment order, not a yes. The intern generated every ordering of the catalog and returned the first list that respected every pair. Eight modules in staging printed a sequence before standup. Four hundred in production were still permuting when the request timed out — and one pair had been entered twice, reversed.

Course Schedule II asks for one legal order of every course — or an empty array if the prerequisite graph contains a directed cycle. A graph of “must take first” edges already gives neighbors for free. Trying every catalog order uses that and still pays n!.

This is an interview writeup, not a layout lecture. That post owns adjacency list versus matrix. Topological sort owns Kahn’s indegree queue and leftover vertices. Course Schedule already counted those leftovers for a boolean. Here we only record the courses as they leave the ready queue.

The problem

Courses are labeled 0 through numCourses - 1. Each pair [a, b] means you take b before a; courses that never appear in a pair are unconstrained. Return any ordering that respects every pair, or an empty array if that is impossible.

numCourses = 3,  prereqs = [[1, 0], [2, 1]]                 →  [0, 1, 2]
numCourses = 2,  prereqs = [[1, 0], [0, 1]]                 →  []
numCourses = 4,  prereqs = [[1, 0], [2, 0], [3, 1], [3, 2]] →  [0, 1, 2, 3]
numCourses = 1,  prereqs = [[0, 0]]                         →  []
numCourses = 5,  prereqs = []                               →  [0, 1, 2, 3, 4]

First row: take 0, then 1, then 2. Second: each waits on the other; no legal list. Third: 0 unlocks 1 and 2; either of those unlocks 3 — [0, 2, 1, 3] is equally legal. Fourth: a course that requires itself. Fifth: five independent modules; any permutation is fine.

Note: Say the pair out loud before you draw the arrow: [a, b] is b before a, so the edge is b → a. Reverse it and a legal catalog can look cyclic. Any valid topological order is an accepted answer; the empty array is the only failure.

Trying every catalog order is the honest brute force

Generate every permutation of 0 .. n-1 and return the first ordering where every pair has b before a. If none survive, return empty. Same check as Course Schedule. Different return. Correct. Factorial.

int[] findOrderPermute(int numCourses, int[][] prerequisites) {
    int[] order = new int[numCourses];
    for (int i = 0; i < numCourses; i++) {
        order[i] = i;
    }
    if (permute(order, 0, prerequisites)) {
        return order;
    }
    return new int[0];
}

boolean permute(int[] order, int i, int[][] prerequisites) {
    if (i == order.length) {
        return respects(order, prerequisites);
    }
    for (int j = i; j < order.length; j++) {
        swap(order, i, j);
        if (permute(order, i + 1, prerequisites)) {
            return true;
        }
        swap(order, i, j);
    }
    return false;
}

boolean respects(int[] order, int[][] prerequisites) {
    int[] at = new int[order.length];
    for (int i = 0; i < order.length; i++) {
        at[order[i]] = i;
    }
    for (int[] p : prerequisites) {
        int a = p[0];
        int b = p[1];
        if (at[b] >= at[a]) {
            return false;
        }
    }
    return true;
}

void swap(int[] order, int i, int j) {
    int tmp = order[i];
    order[i] = order[j];
    order[j] = tmp;
}

At n = 8 this is a rounding error. At a few dozen courses you paid n! for a question a ready queue answers by recording: did every vertex leave the queue, and in what order?

Kahn: record the emission

Course Schedule already built this graph: edge b → a for each pair, an indegree count, an ArrayDeque seeded with every course whose indegree is 0 — including courses that never appear in prereqs. Topological sort already proved leftover vertices are a cycle. Do not re-derive either at the board unless they ask.

The only change is the return. While the queue is nonempty, take the front, write it into the next slot of the order, decrement each successor, and enqueue anyone who just hit zero. If taken != numCourses, return new int[0]. If you filled every slot, return the array.

Do not collapse this to a boolean count. The prompt is a sequence.

Walk the four-course diamond. Edges 0 → 1, 0 → 2, 1 → 3, 2 → 3:

indegree:  0:0  1:1  2:1  3:2
ready:     0
order:     []

take 0   1--, 2-- → both 0    ready: 1, 2    order: [0]
take 1   3-- → 1              ready: 2        order: [0, 1]
take 2   3-- → 0              ready: 3        order: [0, 1, 2]
take 3                        ready: empty    order: [0, 1, 2, 3]

taken == 4  →  [0, 1, 2, 3]

The mutual pair [1, 0], [0, 1] starts both indegrees at 1. The queue is empty. taken == 0. Leftover {0, 1} is the cycle. Return [].

The Java is that recording:

int[] findOrder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>(numCourses);
    for (int i = 0; i < numCourses; i++) {
        adj.add(new ArrayList<>());
    }
    int[] indegree = new int[numCourses];
    for (int[] p : prerequisites) {
        int a = p[0];
        int b = p[1];
        adj.get(b).add(a);
        indegree[a]++;
    }
    Deque<Integer> ready = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            ready.offer(i);
        }
    }
    int[] order = new int[numCourses];
    int taken = 0;
    while (!ready.isEmpty()) {
        int u = ready.poll();
        order[taken++] = u;
        for (int v : adj.get(u)) {
            indegree[v]--;
            if (indegree[v] == 0) {
                ready.offer(v);
            }
        }
    }
    return taken == numCourses ? order : new int[0];
}

Time is O(n + m) — each course is enqueued at most once, each prerequisite edge decrements once. Space is O(n + m) for the adjacency lists, indegree array, queue, and the order you emit. n is the number of courses; m is the number of pairs.

Note: The ready set is a queue. Use ArrayDeque. ArrayList.remove(0) shifts on every take. java.util.Stack is the wrong type. A DFS walk that records reverse finish times is the same order family — that procedure lives on topological sort. Prefer Kahn unless they asked for finish times. Do not return a boolean; this prompt wants the sequence.

What interviewers usually poke next

  • Boolean only. That is Course Schedule. Count as you drain, still fail when taken != n. Do not drop the list in findOrder unless they switch the prompt.
  • DFS reverse finish times. Same DAG, different procedure. Name topological sort and keep Kahn as the default board. Do not paste the 3-color walk here.
  • Arrow direction. [a, b] is take b before a. Reverse the edge and a DAG can look stuck. Say the meaning out loud before you add.
  • Many valid orders. After taking 0 in the diamond, 1 and 2 are both ready. FIFO emits [0, 1, 2, 3]; taking 2 first emits [0, 2, 1, 3]. Both pass.
  • Self-loop / empty pairs. [0, 0] never hits indegree 0; return []. prereqs = [] seeds every course and emits 0 .. n-1. Ask what numCourses = 0 should do; empty array is the usual call.

You are done with this problem when you can say, out loud, why every permutation is correct, why leftover vertices after Kahn mean you return empty, and why this method returns a list instead of a boolean.