[Medium] 210. Course Schedule II

Problem Statement

You have numCourses courses labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] means you must take course bi before course ai. Return any valid ordering of courses to finish all of them, or an empty array if it is impossible.

Examples

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: To take course 1 you must take course 0 first. So [0,1] is valid.

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3] (or [0,1,2,3], etc.)
Explanation: 0 has no prereq; 1 and 2 depend on 0; 3 depends on 1 and 2.

Example 3:

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

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • ai != bi; all pairs are distinct

Solution Approach

This is topological sort on a directed graph: edge (bi, ai) means bi must come before ai. If the graph has a cycle, no valid order exists. Two standard approaches:

  1. DFS + three-state coloring: 0 = unvisited, 1 = visiting (on stack), 2 = visited. If we see a node with color 1 while DFS, there is a cycle. When we finish a node (color 2), append it to a list; reverse the list to get topological order.
  2. Kahn’s algorithm (BFS): Compute indegree of each node. Repeatedly take a node with indegree 0, add it to the order, and decrease indegree of its neighbors. If the final order has size numCourses, no cycle; else return [].

Solution 1: DFS with Three-State Coloring

class Solution:
    def findOrder(self, numCourses, prerequisites):
        adj = [[] for _ in range(numCourses)]
        
        for a, b in prerequisites:
            adj[b].append(a)
        
        color = [0] * numCourses  # 0=unvisited, 1=visiting, 2=visited
        order = []
        valid = True
        
        def dfs(u):
            nonlocal valid
            
            color[u] = 1
            
            for v in adj[u]:
                if color[v] == 0:
                    dfs(v)
                    if not valid:
                        return
                elif color[v] == 1:
                    valid = False
                    return
            
            color[u] = 2
            order.append(u)
        
        for i in range(numCourses):
            if color[i] == 0:
                dfs(i)
                if not valid:
                    return []
        
        return order[::-1]
  • Cycle: Seeing color[v] == 1 means v is on the current DFS stack → back edge → cycle.
  • Order: We push a node when we finish it (all descendants done), so the list is reverse topological order; one reverse gives a valid order.
  • Time: O(V + E). Space: O(V).

Solution 2: Kahn’s Algorithm (BFS)

from collections import deque

class Solution:
    def findOrder(self, numCourses, prerequisites):
        adj = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        
        for a, b in prerequisites:
            adj[b].append(a)
            indegree[a] += 1
        
        q = deque()
        order = []
        
        for i in range(numCourses):
            if indegree[i] == 0:
                q.append(i)
        
        while q:
            u = q.popleft()
            order.append(u)
            
            for v in adj[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)
        
        return order if len(order) == numCourses else []
  • Indegree: indegree[v] = number of edges into v. Process nodes with indegree 0 (no unmet prerequisites).
  • Cycle: If there is a cycle, some nodes never get indegree 0, so order.size() < numCourses → return [].
  • Time: O(V + E). Space: O(V).

Comparison

Approach Idea Cycle check
DFS + coloring Finish order → reverse Back edge (color == 1)
Kahn (BFS) Indegree 0 → order order.size() != numCourses

Key Insights

  1. Prerequisite = edge: [a, b] means b → a in the graph; topological order has predecessors before successors.
  2. DFS order: Finishing order is reverse topological; one reverse gives a valid schedule.
  3. Kahn: No need to reverse; order is built in topological order as we dequeue.