mediumGraphs

Course Schedule II

Find an order for completing all courses subject to prerequisites. When several courses are available, always choose the smallest label.

LeetCode ↗

Work through the cases

3 examples

Input notation

Number of courses on line 1; then pairs a b meaning b must precede a.

Expected result

The chosen order separated by spaces, or none if impossible.

Case 1

Input

Expected output

0 1 2 3

Case 2

Input

2
1 0
0 1

Expected output

none

Case 3

Input

Expected output

0 1 2

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

As in the decision version, prerequisites form a directed graph; here we also need one valid order. The dequeue order of a topological sort is such a sequence. If fewer than numCourses vertices enter the queue, a cycle exists and we return an empty array.

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer>[] g = new List[numCourses];
        Arrays.setAll(g, k -> new ArrayList<>());
        int[] indeg = new int[numCourses];
        for (var p : prerequisites) {
            int a = p[0], b = p[1];
            g[b].add(a);
            ++indeg[a];
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {
                q.offer(i);
            }
        }
        int[] ans = new int[numCourses];
        int cnt = 0;
        while (!q.isEmpty()) {
            int i = q.poll();
            ans[cnt++] = i;
            for (int j : g[i]) {
                if (--indeg[j] == 0) {
                    q.offer(j);
                }
            }
        }
        return cnt == numCourses ? ans : new int[0];
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.