Course Schedule II - Video Solutions

Problem Overview: You are given numCourses and a list of prerequisite pairs where [a, b] means you must take course b before a. The task is to return a valid ordering of all courses so every prerequisite is satisfied. If a cycle exists in the dependency graph, no valid order exists and you return an empty array.

This problem is a classic application of graph traversal and topological sort. Each course is a node and each prerequisite forms a directed edge. A valid schedule is simply a topological ordering of the directed graph.

Approach 1: Topological Sort using Kahn's Algorithm (BFS) (Time: O(V + E), Space: O(V + E))

Model the courses as a directed graph using an adjacency list and maintain an indegree array for each node. The indegree represents how many prerequisites a course still needs. Initialize a queue with all courses whose indegree is zero because they can be taken immediately. Repeatedly pop from the queue, append the course to the result, and decrease the indegree of its neighbors. Whenever a neighbor's indegree becomes zero, push it into the queue.

If you process all numCourses nodes, the result list is a valid ordering. If some nodes remain unprocessed, the graph contains a cycle. This approach works well because it explicitly tracks dependency resolution and processes nodes in dependency order using Breadth-First Search.

Approach 2: DFS with Cycle Detection (Time: O(V + E), Space: O(V + E))

This approach performs depth-first traversal while tracking node states to detect cycles. Each node can be marked as unvisited, visiting, or visited. During DFS, mark the current node as visiting and recursively explore its neighbors. If you encounter another visiting node, a cycle exists and scheduling is impossible.

After exploring all neighbors, mark the node as visited and push it into the result list. The final ordering is obtained by reversing the post-order traversal. This method naturally constructs a topological ordering while ensuring cycles are detected during recursion.

Recommended for interviews: Kahn’s Algorithm (BFS topological sort) is usually the expected solution because it clearly models prerequisite counts and processes nodes in dependency order. DFS with cycle detection demonstrates deeper understanding of graph traversal and recursion. Showing both approaches signals strong command of topological sorting problems.