Course Schedule II

MEDIUM✓ CHIP-TIMEDLC #210 — FULL STATEMENT ↗

The drill: Some courses require other courses first. Produce one valid order to take every course so no course comes before something it needs — or report that no such order exists because the requirements loop.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Same setup as the yes/no version of this drill — a fixed number of courses and a list of prerequisite pairs — but this time the answer has to be an actual valid order to take every course, one where nothing appears before something it depends on.

Multiple valid orders can exist for the same input, and any one of them is acceptable — the grading only cares that every prerequisite pair is respected somewhere in the sequence produced.

When the requirements loop back on themselves and no valid order can exist at all, the expected answer is an empty list rather than a partial attempt.

EX 01

numCourses = 1 · prerequisites = []

→ [0]

ONE COURSE, NO REQUIREMENTS

EX 02

numCourses = 2 · prerequisites = [[1, 0]]

→ [0, 1]

ONE REQUIREMENT FORCES THE ORDER

EX 03

numCourses = 2 · prerequisites = [[1, 0], [0, 1]]

→ []

THE TWO COURSES NEED EACH OTHER

up to a few thousand courses and prerequisite pairs
any one valid ordering is accepted — the answer isn't unique
a cycle among the requirements means the answer is an empty list
a course with no prerequisites can appear anywhere before its dependents

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

This is the same requirement graph as before, but now the answer isn't yes/no — it's the actual order. Which courses are always safe to take right now, on any valid schedule?

HINT 2 THE STRUCTURE

A course is safe the moment every one of its prerequisites is already taken. That set of "safe now" courses changes as you take courses — the real question is how cheaply you can track it.

HINT 3 ONE STEP FROM THE ANSWER

Keep a running count of remaining prerequisites per course. Take any course sitting at zero, then decrement that count for everyone who depended on it — no rescanning needed, just a queue of newly-zeroed courses.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE PEEL ORDERPATTERN · TOPOLOGICAL SORT — KAHN5 courses · chain: 1→3→0→2→4

STEP 1

5 courses, numbered out of sequence: taking 1 unlocks 3, 3 unlocks 0, 0 unlocks 2, 2 unlocks 4. Count in-degrees first.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/course-schedule-ii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(numCourses)]
        indeg = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)  # taking b unlocks a
            indeg[a] += 1

        queue = collections.deque(c for c in range(numCourses) if indeg[c] == 0)
        order = []
        while queue:
            course = queue.popleft()
            order.append(course)
            for nxt in graph[course]:
                indeg[nxt] -= 1
                if indeg[nxt] == 0:
                    queue.append(nxt)

        return order if len(order) == numCourses else []

TIME O(V+E)SPACE O(V+E)PYTHON · RACE PACE · 19 LN

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        taken = [False] * numCourses
        order = []

        for _ in range(numCourses):
            progressed = False
            for c in range(numCourses):
                if taken[c]:
                    continue
                # recheck every requirement of c from scratch, every round
                if all(taken[b] for a, b in prerequisites if a == c):
                    taken[c] = True
                    order.append(c)
                    progressed = True
                    break
            if not progressed:
                return []
        return order

TIME O(V²·E)SPACE O(V+E)PYTHON · TRAINING PACE · 19 LN

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        int[] indeg = new int[numCourses];
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
            indeg[p[0]]++;
        }

        Deque<Integer> queue = new ArrayDeque<>();
        for (int c = 0; c < numCourses; c++) if (indeg[c] == 0) queue.add(c);

        int[] order = new int[numCourses];
        int filled = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            order[filled++] = course;
            for (int nxt : graph.get(course)) {
                if (--indeg[nxt] == 0) queue.add(nxt);
            }
        }
        return filled == numCourses ? order : new int[0];
    }
}

TIME O(V+E)SPACE O(V+E)JAVA · RACE PACE · 25 LN

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        boolean[] taken = new boolean[numCourses];
        int[] order = new int[numCourses];
        int filled = 0;

        for (int round = 0; round < numCourses; round++) {
            boolean progressed = false;
            for (int c = 0; c < numCourses; c++) {
                if (taken[c]) continue;
                boolean ready = true;
                for (int[] p : prerequisites) {
                    if (p[0] == c && !taken[p[1]]) {
                        ready = false;
                        break;
                    }
                }
                if (ready) {
                    taken[c] = true;
                    order[filled++] = c;
                    progressed = true;
                    break;
                }
            }
            if (!progressed) return new int[0];
        }
        return order;
    }
}

TIME O(V²·E)SPACE O(V+E)JAVA · TRAINING PACE · 29 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED