Course Schedule II

Medium Problem 107 of 151 Java and Python

Problem

There are numCourses courses labelled 0 to numCourses - 1. prerequisites[i] = [a, b] means course b must come before course a.

Return any valid order to take all courses. If it 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] or [0, 2, 1, 3]

Constraints

1 ≤ numCourses ≤ 2000
All prerequisite pairs are distinct.

Explanation

Course Schedule asked "is there an order?". Kahn's algorithm builds that order as a by-product: the sequence in which courses leave the queue is a valid topological order.

With DFS, a course is finished only after everything that depends on it, so reversed finishing order is also valid.

Approach 1 · Better

DFS post-order, reversed

Time O(V + E)
Space O(V + E)

Run the three-colour DFS; append each course when it turns black. The reversed list is a valid order, unless a cycle was found.

DFS from every white course; on finishing a course, append it to order.
If a grey course is reached, return [].
Return order reversed.

Java

import java.util.*;

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<>());
        }
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
        }
        int[] state = new int[numCourses];
        List<Integer> order = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            if (!visit(graph, i, state, order)) {
                return new int[0];
            }
        }
        Collections.reverse(order);
        return order.stream().mapToInt(Integer::intValue).toArray();
    }

    // Returns false when a cycle is found.
    private boolean visit(List<List<Integer>> graph, int node, int[] state, List<Integer> order) {
        if (state[node] == 1) {
            return false;
        }
        if (state[node] == 2) {
            return true;
        }
        state[node] = 1;
        for (int next : graph.get(node)) {
            if (!visit(graph, next, state, order)) {
                return false;
            }
        }
        state[node] = 2;
        order.add(node);
        return true;
    }
}

Python

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            graph[b].append(a)
        state, order = [0] * numCourses, []

        def visit(node):
            if state[node] == 1:
                return False
            if state[node] == 2:
                return True
            state[node] = 1
            if not all(visit(nxt) for nxt in graph[node]):
                return False
            state[node] = 2
            order.append(node)
            return True

        if not all(visit(i) for i in range(numCourses)):
            return []
        return order[::-1]

Approach 2 · Optimal

Kahn's algorithm, recording the order

Time O(V + E)
Space O(V + E)

Same BFS as Course Schedule; append each course as it is taken from the queue.

Build the graph and in-degrees; queue all courses with in-degree 0.
Pop a course, append it to order, and release its dependants.
If order has every course, return it; otherwise return [].

Java

import java.util.*;

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[] inDegree = new int[numCourses];
        for (int[] p : prerequisites) {
            graph.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 taken = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            order[taken++] = course;
            for (int next : graph.get(course)) {
                if (--inDegree[next] == 0) {
                    queue.add(next);
                }
            }
        }
        return taken == numCourses ? order : new int[0];
    }
}

Python

from collections import deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)
            in_degree[a] += 1
        queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
        order = []
        while queue:
            course = queue.popleft()
            order.append(course)
            for nxt in graph[course]:
                in_degree[nxt] -= 1
                if in_degree[nxt] == 0:
                    queue.append(nxt)
        return order if len(order) == numCourses else []

Complexity compared

Approach	Time	Space
Better DFS post-order, reversed	O(V + E)	O(V + E)
Optimal Kahn's algorithm, recording the order	O(V + E)	O(V + E)

Key takeaways

Topological sort shows up as build systems, task scheduling, spreadsheet formulas and Alien Dictionary.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem