Course Schedule II

LeetCode 210: Course Schedule II Solution & Explanation

Problem Overview

TL;DR: The optimal solution models the courses and prerequisites as a directed graph and performs a topological sort using Depth-First Search (DFS) with three-state coloring to detect cycles and determine the execution order.

In the LeetCode 210 problem, "Course Schedule II," you are given a specific number of courses and a list of prerequisites. Each prerequisite is defined as a pair [a, b], meaning you must take course b before you can take course a. Your objective is to return a valid linear ordering of courses that respects all prerequisite constraints. If a circular dependency exists (e.g., A requires B, and B requires A), it is impossible to complete the courses, and you must return an empty array.

This is a classic graph theory problem that tests your ability to model dependencies and validate the structure of a Directed Acyclic Graph (DAG).

Brute Force Approach for Course Schedule II

A naive brute force approach would attempt to generate every possible permutation of the courses and verify if any permutation satisfies the prerequisite constraints.

1. Generate all permutations of the numbers 0 to numCourses - 1.
2. For each permutation, iterate through the prerequisites list.
3. Check if every prerequisite [a, b] is satisfied (i.e., b appears before a in the permutation).
4. Return the first valid permutation found.

Pseudo-code:

function solve_brute_force(n, prerequisites):
    permutations = generate_all_permutations(0 to n-1)
    for perm in permutations:
        valid = true
        for [a, b] in prerequisites:
            if index_of(b, perm) > index_of(a, perm):
                valid = false
                break
        if valid:
            return perm
    return []

Why this fails: The time complexity of generating all permutations is $O(N!)$. For $N=2000$ (the constraint in this problem), $2000!$ is an astronomically large number, far exceeding the computational limits of any machine. This approach will result in a Time Limit Exceeded (TLE) error immediately.

Algorithm Strategy: Graph DFS - Cycle Detection

1. Graph Construction: Convert the input prerequisites list into an adjacency list. Note that an input [a, b] means an edge exists from b to a (b must be taken before a).
2. State Initialization: Initialize an array state of size numCourses with all values set to 0 (Unvisited).
3. Result Container: Use a dynamic array or list to store the topological sort.
4. Outer Loop: Iterate through every course from 0 to numCourses - 1. If a course is in State 0, initiate a DFS traversal from that node. This handles disconnected graph components.
5. DFS Function:
   • If the current node is State 1 (Visiting), a cycle is detected. Return false.
   • If the current node is State 2 (Visited), it is already processed. Return true.
   • Mark the current node as State 1.
   • Recursively visit all neighbors. If any recursive call returns false, propagate the failure up the stack.
   • After visiting all neighbors successfully, mark the current node as State 2 (Visited).
   • Append the node to the result list.
6. Final Processing: Since DFS finishes the deepest nodes first (post-order traversal), the result list will contain courses in reverse topological order (children before parents). Reverse the list to get the correct order.
7. Output: If a cycle was detected at any point, return an empty array. Otherwise, return the reversed list.

Execution Flow

Let's trace the algorithm with numCourses = 4 and prerequisites = [[1,0], [2,0], [3,1], [3,2]]. Edges: $0 \to 1$, $0 \to 2$, $1 \to 3$, $2 \to 3$.

1. Init: state = [0, 0, 0, 0], result = [].
2. Outer Loop: Start at node 0 (State 0). Call dfs(0).
3. dfs(0):
   • Mark 0 as State 1.
   • Neighbors of 0 are 1 and 2.
   • Call dfs(1):
     • Mark 1 as State 1.
     • Neighbor of 1 is 3.
     • Call dfs(3):
       • Mark 3 as State 1.
       • No neighbors.
       • Mark 3 as State 2.
       • Add 3 to result. result = [3].
       • Return true.
     • Mark 1 as State 2.
     • Add 1 to result. result = [3, 1].
     • Return true.
   • Call dfs(2):
     • Mark 2 as State 1.
     • Neighbor of 2 is 3.
     • Call dfs(3):
       • 3 is State 2 (Visited). Return true.
     • Mark 2 as State 2.
     • Add 2 to result. result = [3, 1, 2].
     • Return true.
   • Mark 0 as State 2.
   • Add 0 to result. result = [3, 1, 2, 0].
   • Return true.
4. Outer Loop: Nodes 1, 2, 3 are already State 2. Skip.
5. Finalize: Reverse result to get [0, 2, 1, 3]. This is a valid topological order.

Proof of Correctness

The correctness of this algorithm relies on the properties of Depth-First Search on a DAG.

1. Cycle Detection: By marking nodes as "Visiting" (State 1) upon entry and "Visited" (State 2) upon exit, any edge pointing to a "Visiting" node represents a back-edge to an ancestor in the current recursion stack. This is the definition of a cycle in DFS. If such an edge is found, the algorithm correctly identifies that no topological sort exists.
2. Ordering: In a DFS, a node is marked "Visited" and added to the list only after all its reachable descendants have been processed (post-order traversal). This means for any edge $u \to v$, $v$ will be added to the list before $u$. Consequently, the list represents a reverse topological order. Reversing this list guarantees that for every edge $u \to v$, $u$ appears before $v$, satisfying the problem constraints.

Pattern Reuse Notes

The Graph DFS - Cycle Detection pattern used in LeetCode 210 is directly applicable to several other popular interview questions:

• LeetCode 207: Course Schedule: This is the exact same problem but asks only for a boolean (can you finish?) rather than the order. The logic is identical, just without the result list.
• LeetCode 802: Find Eventual Safe States: Uses the same 3-state coloring. Nodes that are part of a cycle or lead to a cycle are "unsafe."
• LeetCode 1059: All Paths from Source Lead to Destination: Requires detecting cycles to ensure paths are finite and checking specific conditions on leaf nodes using DFS.

Reference Implementation

C++ Solution for LeetCode 210

1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6class Solution {
7public:
8    // 0 = Unvisited, 1 = Visiting, 2 = Visited
9    bool dfs(int node, vector<vector<int>>& adj, vector<int>& state, vector<int>& result) {
10        if (state[node] == 1) return false; // Cycle detected
11        if (state[node] == 2) return true;  // Already processed
12        
13        state[node] = 1; // Mark as visiting
14        
15        for (int neighbor : adj[node]) {
16            if (!dfs(neighbor, adj, state, result)) {
17                return false;
18            }
19        }
20        
21        state[node] = 2; // Mark as visited
22        result.push_back(node); // Add to result (post-order)
23        return true;
24    }
25
26    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
27        vector<vector<int>> adj(numCourses);
28        // Build adjacency list: [a, b] means b -> a
29        for (const auto& edge : prerequisites) {
30            adj[edge[1]].push_back(edge[0]);
31        }
32        
33        vector<int> state(numCourses, 0);
34        vector<int> result;
35        
36        for (int i = 0; i < numCourses; ++i) {
37            if (state[i] == 0) {
38                if (!dfs(i, adj, state, result)) {
39                    return {}; // Cycle detected, return empty
40                }
41            }
42        }
43        
44        reverse(result.begin(), result.end());
45        return result;
46    }
47};

Java Solution for LeetCode 210

1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.List;
4
5class Solution {
6    // 0 = Unvisited, 1 = Visiting, 2 = Visited
7    private boolean dfs(int node, List<List<Integer>> adj, int[] state, List<Integer> result) {
8        if (state[node] == 1) return false; // Cycle detected
9        if (state[node] == 2) return true;  // Already processed
10        
11        state[node] = 1; // Mark as visiting
12        
13        for (int neighbor : adj.get(node)) {
14            if (!dfs(neighbor, adj, state, result)) {
15                return false;
16            }
17        }
18        
19        state[node] = 2; // Mark as visited
20        result.add(node); // Add to result (post-order)
21        return true;
22    }
23
24    public int[] findOrder(int numCourses, int[][] prerequisites) {
25        List<List<Integer>> adj = new ArrayList<>();
26        for (int i = 0; i < numCourses; i++) {
27            adj.add(new ArrayList<>());
28        }
29        
30        // Build adjacency list: [a, b] means b -> a
31        for (int[] edge : prerequisites) {
32            adj.get(edge[1]).add(edge[0]);
33        }
34        
35        int[] state = new int[numCourses];
36        List<Integer> resultList = new ArrayList<>();
37        
38        for (int i = 0; i < numCourses; i++) {
39            if (state[i] == 0) {
40                if (!dfs(i, adj, state, resultList)) {
41                    return new int[0]; // Cycle detected
42                }
43            }
44        }
45        
46        // Reverse to get topological order
47        Collections.reverse(resultList);
48        
49        // Convert List to int[]
50        int[] result = new int[numCourses];
51        for (int i = 0; i < numCourses; i++) {
52            result[i] = resultList.get(i);
53        }
54        
55        return result;
56    }
57}

Python Solution for LeetCode 210

1from collections import defaultdict
2
3class Solution:
4    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
5        adj = defaultdict(list)
6        # Build adjacency list: [a, b] means b -> a
7        for dest, src in prerequisites:
8            adj[src].append(dest)
9            
10        # 0 = Unvisited, 1 = Visiting, 2 = Visited
11        state = [0] * numCourses
12        result = []
13        
14        def dfs(node):
15            if state[node] == 1:
16                return False # Cycle detected
17            if state[node] == 2:
18                return True  # Already processed
19            
20            state[node] = 1 # Mark as visiting
21            
22            for neighbor in adj[node]:
23                if not dfs(neighbor):
24                    return False
25            
26            state[node] = 2 # Mark as visited
27            result.append(node) # Add to result (post-order)
28            return True
29            
30        for i in range(numCourses):
31            if state[i] == 0:
32                if not dfs(i):
33                    return []
34                    
35        return result[::-1] # Reverse to get topological order