Plan the Course Order
Solve this ProblemA school offers n courses, and some courses can only be taken after others. The requirements are given as an adjacency list of a directed graph: courses[u] holds the courses that require course u first. Produce a plan that takes every course after its requirements, or report that this is impossible.
When several plans are valid, return the lexicographically smallest, and return an empty list when the requirements contain a cycle.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 8 courses numbered 0 … n-1; courses[u] lists, in increasing order, every course v that requires course u to be completed first (adjacency-list form of a directed graph) - ◆
A course may require itself (a road u → u), which can never be satisfied; the graph may contain cycles - ◆
A valid plan takes every course exactly once, each one after all the courses it requires - ◆
Return the lexicographically smallest valid plan, or an empty list if no valid plan exists
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Orderings in Dictionary Order
BruteGenerate the orderings of the courses in dictionary order and check every requirement u → v (u must appear before v; a course requiring itself fails automatically). The first ordering that passes is the lexicographically smallest plan. If none of the n! orderings passes, return an empty list. Correct but only usable for tiny n.
O(n! · (n + E))O(n)1class Solution {
2 private boolean respectsRoads(int[][] courses, int[] order) {
3 int n = courses.length;
4 int[] position = new int[n];
5 for (int i = 0; i < n; i++) position[order[i]] = i;
6 for (int u = 0; u < n; u++) {
7 for (int v : courses[u]) {
8 if (position[u] >= position[v]) return false;
9 }
10 }
11 return true;
12 }
13
14 private boolean search(int[][] courses, int[] order, int len, boolean[] used) {
15 int n = courses.length;
16 if (len == n) return respectsRoads(courses, order);
17 for (int v = 0; v < n; v++) {
18 if (used[v]) continue;
19 used[v] = true;
20 order[len] = v;
21 if (search(courses, order, len + 1, used)) return true;
22 used[v] = false;
23 }
24 return false;
25 }
26
27 public int[] orderCourses(int[][] courses) {
28 int[] order = new int[courses.length];
29 if (!search(courses, order, 0, new boolean[courses.length])) return new int[0];
30 return order;
31 }
32}Optimal — Kahn’s Algorithm With a Min-Heap
OptimalCount the unfinished requirements of every course (indegree). Repeatedly take the smallest course whose count is 0 (a min-heap keeps the ready courses ordered), append it to the plan and cross it off by decreasing the counts of the courses that require it. If the plan ends up with all n courses, return it; if the heap runs dry earlier, the remaining courses wait on each other in a cycle, so return an empty list. Every course and requirement is handled once (heap steps cost log n).
O((n + E) log n)O(n)1class Solution {
2 public int[] orderCourses(int[][] courses) {
3 int n = courses.length;
4 int[] indegree = new int[n];
5 for (int u = 0; u < n; u++) {
6 for (int v : courses[u]) indegree[v]++;
7 }
8 PriorityQueue<Integer> ready = new PriorityQueue<>();
9 for (int i = 0; i < n; i++) {
10 if (indegree[i] == 0) ready.add(i);
11 }
12 int[] order = new int[n];
13 int len = 0;
14 while (!ready.isEmpty()) {
15 int u = ready.poll();
16 order[len++] = u;
17 for (int v : courses[u]) {
18 indegree[v]--;
19 if (indegree[v] == 0) ready.add(v);
20 }
21 }
22 if (len < n) return new int[0];
23 return order;
24 }
25}