Course Schedule II

NeetCode: Course Schedule II · LeetCode: 210. Course Schedule II · Difficulty: Medium

Same setup as Course Schedule: a pair [a, b] means take course b before course a. Return an order in which to take all numCourses courses, or an empty array if it is impossible. Any valid order is accepted.

Example

Text

numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0, 1, 2, 3]     ([0, 2, 1, 3] is also valid)

numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: []   (empty array)

The answer is a topological order of the prerequisite graph. It exists exactly when the graph has no cycle.

Brute force: repeatedly scan for courses that are ready

Work in rounds. In each round, scan all courses and collect those that are not taken yet and whose prerequisites are all already taken. Take them all, then repeat. If a round finds nothing while courses remain, the rest are stuck behind a cycle.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            List<List<Integer>> prereqs = new ArrayList<>();
            for (int i = 0; i < numCourses; i++) {
                prereqs.add(new ArrayList<>());
            }
            for (int[] p : prerequisites) {
                prereqs.get(p[0]).add(p[1]);
            }
            boolean[] taken = new boolean[numCourses];
            int[] order = new int[numCourses];
            int count = 0;
            while (count < numCourses) {
                List<Integer> ready = new ArrayList<>();
                for (int c = 0; c < numCourses; c++) {
                    if (taken[c]) {
                        continue;
                    }
                    boolean allTaken = true;
                    for (int pre : prereqs.get(c)) {
                        if (!taken[pre]) {
                            allTaken = false;
                            break;
                        }
                    }
                    if (allTaken) {
                        ready.add(c);
                    }
                }
                if (ready.isEmpty()) {
                    return new int[0];
                }
                for (int c : ready) {
                    taken[c] = true;
                    order[count++] = c;
                }
            }
            return order;
        }
    }

    static boolean isValid(int[] order, int n, int[][] prerequisites) {
        if (order.length != n) {
            return false;
        }
        int[] pos = new int[n];
        for (int i = 0; i < n; i++) {
            pos[order[i]] = i;
        }
        for (int[] p : prerequisites) {
            if (pos[p[1]] >= pos[p[0]]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] pre = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        int[] order = s.findOrder(4, pre);
        System.out.println(Arrays.toString(order) + " valid=" + isValid(order, 4, pre));
        System.out.println(Arrays.toString(s.findOrder(2, new int[][]{{1, 0}, {0, 1}})));
        System.out.println(Arrays.toString(s.findOrder(1, new int[][]{})));
        System.out.println(Arrays.toString(s.findOrder(0, new int[][]{})));
    }
}

Output

[0, 1, 2, 3] valid=true
[]
[0]
[]

Each round takes at least one course, so there are at most V rounds, each costing a scan of all courses and their prerequisite lists. Time: O(V * (V + E)). Space: O(V + E).

Optimal: Kahn's algorithm records the order

The queue in Kahn's algorithm already produces courses in a valid order: a course is only enqueued once all its prerequisites have been dequeued. So the answer is the dequeue sequence; if it is shorter than V (count < numCourses), there is a cycle and the result is an empty array. The code is that of Course Schedule with the order recorded.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

public class Main {
    static class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            List<List<Integer>> adj = new ArrayList<>();
            for (int i = 0; i < numCourses; i++) {
                adj.add(new ArrayList<>());
            }
            int[] indegree = new int[numCourses];
            for (int[] p : prerequisites) {
                adj.get(p[1]).add(p[0]);
                indegree[p[0]]++;
            }
            Deque<Integer> queue = new ArrayDeque<>();
            for (int i = 0; i < numCourses; i++) {
                if (indegree[i] == 0) {
                    queue.add(i);
                }
            }
            int[] order = new int[numCourses];
            int count = 0;
            while (!queue.isEmpty()) {
                int course = queue.poll();
                order[count++] = course;
                for (int next : adj.get(course)) {
                    indegree[next]--;
                    if (indegree[next] == 0) {
                        queue.add(next);
                    }
                }
            }
            return count == numCourses ? order : new int[0];
        }
    }

    static boolean isValid(int[] order, int n, int[][] prerequisites) {
        if (order.length != n) {
            return false;
        }
        int[] pos = new int[n];
        for (int i = 0; i < n; i++) {
            pos[order[i]] = i;
        }
        for (int[] p : prerequisites) {
            if (pos[p[1]] >= pos[p[0]]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] pre = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        int[] order = s.findOrder(4, pre);
        System.out.println(Arrays.toString(order) + " valid=" + isValid(order, 4, pre));
        System.out.println(Arrays.toString(s.findOrder(2, new int[][]{{1, 0}, {0, 1}})));
        System.out.println(Arrays.toString(s.findOrder(1, new int[][]{})));
        System.out.println(Arrays.toString(s.findOrder(0, new int[][]{})));
    }
}

Output

[0, 1, 2, 3] valid=true
[]
[0]
[]

Several valid orders can exist, so isValid checks the result against the prerequisites instead of comparing it with a fixed answer. Time: O(V + E). Space: O(V + E).