A training catalog is asked one boolean before a cohort enrolls: can every module be finished given the prerequisite pairs. The intern generated every ordering of the catalog. Eight modules in staging returned before standup. Four hundred in production were still permuting when the request timed out — and one pair had been entered twice, reversed.

Course Schedule asks whether every course can be finished — equivalently, whether 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. DFS owns finish times; cycle detection owns the gray back edge. Here we only count how many courses left 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 whether every course can be finished.

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

First row: take 0, then 1, then 2. Second: each waits on the other. Third: 0 unlocks 1 and 2; either of those unlocks 3. Fourth: a course that requires itself. Fifth: five independent modules.

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.

Trying every catalog order is the honest brute force

Generate every permutation of 0 .. n-1 and accept the first ordering where every pair has b before a. Correct. Factorial.

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

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 counting: did every vertex leave the queue?

Kahn: leftover vertices mean a cycle

Build the directed adjacency list: edge b → a for each pair. Count indegree. Seed an ArrayDeque with every course whose indegree is 0 — including courses that never appear in prereqs. While the queue is nonempty, take the front, decrement each successor, and enqueue anyone who just hit zero. Count how many you took. Return taken == numCourses. Anything still sitting with positive indegree never became ready. Topological sort already proved leftover vertices are a cycle; do not re-derive it at the board unless they ask.

Do not append the drained vertices to a list. The prompt is a boolean.

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

take 0   1--, 2-- → both 0    ready: 1, 2    taken=1
take 1   3-- → 1              ready: 2        taken=2
take 2   3-- → 0              ready: 3        taken=3
take 3                        ready: empty    taken=4

taken == 4  →  true

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

The Java is that count:

boolean canFinish(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 taken = 0;
    while (!ready.isEmpty()) {
        int u = ready.poll();
        taken++;
        for (int v : adj.get(u)) {
            indegree[v]--;
            if (indegree[v] == 0) {
                ready.offer(v);
            }
        }
    }
    return taken == numCourses;
}

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, and queue. 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 rejects a gray neighbor is the same boolean — that test lives on cycle detection. Prefer Kahn unless they asked for the back edge. Do not emit reverse finish times; this prompt does not want a sequence.

What interviewers usually poke next

  • Return a legal order. That is Course Schedule II. Append as you drain, still fail when taken != n. Do not start collecting a list in canFinish unless they switch the prompt.
  • DFS 3-color / back edge. Gray neighbor means a cycle. Same answer, different procedure. Name cycle detection and keep Kahn as the default board.
  • 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.
  • Self-loop / empty pairs. [0, 0] never hits indegree 0. prereqs = [] seeds every course and drains n. Ask what numCourses = 0 should do; vacuously true is the usual call.
  • Why leftovers prove a cycle. Point at topological sort. Do not re-prove Kahn unless they ask.

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