Problem statement

There are numCourses courses; prerequisites[i] = [a, b] means course b comes before course a. Return a valid order to take all courses — specifically the lexicographically smallest valid order. If finishing all courses is impossible, return an empty array.

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]

Example 2

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]

Example 3

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: []

Constraints

• 1 <= numCourses <= 10
• 0 <= prerequisites.length <= 20

Hints for Course Schedule II

1. Hint 1

   Kahn's algorithm, but pick the SMALLEST available course each step (a min-heap).

2. Hint 2

   If the produced order is shorter than numCourses, there was a cycle.

How to solve Course Schedule II

Same topological sort as the yes/no version, but now the order itself is the answer — and among all valid orders you must return the lexicographically smallest. Kahn's algorithm leaves you free to pick any available course at each step, so exploit that freedom: always take the smallest-numbered course currently available.

Approach

1. Build edges b -> a for each [a, b] and count in-degrees.
2. Collect every course with in-degree 0 into an available set.
3. Repeatedly take the smallest available course, append it to the order, and decrement its dependants' in-degrees.
4. Any dependant reaching in-degree 0 joins the available set.
5. If the finished order is shorter than numCourses, a cycle blocked the rest — return an empty array.

Why it works

Greedily taking the smallest available course is optimal for lexicographic order: at each position the candidates are exactly the available courses, taking a larger one can only make the sequence bigger at that index, and choosing the smallest never removes a later option — a course's availability depends only on which courses have been taken, not on their order. Shortness of the result is still an exact cycle test, for the same reason as in the decision version.

Complexity

• Time — O(V^2 + E) with a linear scan for the minimum, O((V + E) log V) with a heap
• Space — O(V + E)

Pitfalls

• A plain FIFO queue gives a valid order but not the lexicographically smallest — the selection must be by value.
• Return an empty array on a cycle, not a partial order.
• Edge direction again: [a, b] means b first, so the edge is b -> a.
• Re-select the minimum after every step; the newly freed courses may be smaller than what was already waiting.

Reference solution

Python

from typing import List
import heapq

def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    indeg = [0] * numCourses
    adj = [[] for _ in range(numCourses)]
    for a, b in prerequisites:
        adj[b].append(a)
        indeg[a] += 1
    heap = [i for i in range(numCourses) if indeg[i] == 0]
    heapq.heapify(heap)
    out = []
    while heap:
        c = heapq.heappop(heap)
        out.append(c)
        for nxt in adj[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                heapq.heappush(heap, nxt)
    return out if len(out) == numCourses else []

Java

public static int[] findOrder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    int[] indeg = new int[numCourses];
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<Integer>());
    for (int[] p : prerequisites) {
        adj.get(p[1]).add(p[0]);
        indeg[p[0]]++;
    }
    PriorityQueue<Integer> avail = new PriorityQueue<>();
    for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) avail.add(i);
    List<Integer> order = new ArrayList<>();
    while (!avail.isEmpty()) {
        int u = avail.poll();
        order.add(u);
        for (int v : adj.get(u)) {
            indeg[v]--;
            if (indeg[v] == 0) avail.add(v);
        }
    }
    if (order.size() != numCourses) return new int[0];
    int[] out = new int[order.size()];
    for (int i = 0; i < order.size(); i++) out[i] = order.get(i);
    return out;
}

C++

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(numCourses);
    vector<int> indeg(numCourses, 0);
    for (const auto& p : prerequisites) {
        adj[p[1]].push_back(p[0]);
        indeg[p[0]]++;
    }
    priority_queue<int, vector<int>, greater<int>> avail;
    for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) avail.push(i);
    vector<int> out;
    while (!avail.empty()) {
        int u = avail.top();
        avail.pop();
        out.push_back(u);
        for (int v : adj[u]) {
            indeg[v]--;
            if (indeg[v] == 0) avail.push(v);
        }
    }
    if ((int) out.size() != numCourses) return vector<int>();
    return out;
}

JavaScript

var findOrder = function(numCourses, prerequisites) {
    const indeg = new Array(numCourses).fill(0);
    const adj = [];
    for (let i = 0; i < numCourses; i++) adj.push([]);
    for (const p of prerequisites) {
        adj[p[1]].push(p[0]);
        indeg[p[0]]++;
    }
    const avail = [];
    for (let i = 0; i < numCourses; i++) {
        if (indeg[i] === 0) avail.push(i);
    }
    const out = [];
    while (avail.length > 0) {
        avail.sort(function(a, b) { return a - b; });
        const c = avail.shift();
        out.push(c);
        for (const nxt of adj[c]) {
            if (--indeg[nxt] === 0) avail.push(nxt);
        }
    }
    return out.length === numCourses ? out : [];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More graph problems

• Minimize Maximum Component Cost Medium
• Minimum Time for K Connected Components Medium
• Power Grid Maintenance Medium
• Minimum Time to Reach Destination in Directed Graph Medium
• Unit Conversion I Medium
• Digit Operations to Make Two Integers Equal Medium