Course Schedule - 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 determine whether it is possible to complete all courses. In graph terms, each course is a node and prerequisites are directed edges. The question reduces to detecting whether the directed graph contains a cycle.

Approach 1: Depth First Search (DFS) for Cycle Detection (Time: O(V+E), Space: O(V+E))

Model the problem as a directed graph using an adjacency list. Run a DFS from each unvisited node while tracking the recursion state of nodes: unvisited, visiting, and visited. If DFS encounters a node currently marked as visiting, a back edge exists, which means a cycle in the dependency graph. A cycle makes it impossible to finish all courses because prerequisites loop indefinitely. If DFS completes without detecting a cycle, the course ordering is valid. This technique relies on recursion stack tracking and is a common pattern in Depth-First Search problems involving directed graphs.

Implementation details matter. Build the adjacency list from prerequisite pairs, iterate through all nodes, and start DFS only from nodes that have not been processed. Mark nodes as visited once their subtree is fully explored so they are not reprocessed. This approach naturally handles disconnected components in the graph.

Approach 2: Kahn's Algorithm for Topological Sort (Time: O(V+E), Space: O(V+E))

Kahn's algorithm uses a BFS-style process to compute a topological ordering. First compute the in-degree for every node, which represents how many prerequisites a course has. Push all nodes with in-degree 0 into a queue since those courses can be taken immediately. Repeatedly remove a node from the queue, simulate taking the course, and decrement the in-degree of its neighbors. When a neighbor's in-degree becomes 0, push it into the queue.

If the number of processed courses equals numCourses, the graph is acyclic and all courses can be completed. If some nodes remain with nonzero in-degree, a cycle exists. This method is widely used for dependency resolution and scheduling systems and is a classic application of Topological Sort with Breadth-First Search.

Recommended for interviews: Both DFS cycle detection and Kahn's algorithm run in linear time O(V+E). Interviewers often expect you to recognize the problem as a directed cycle detection task in a graph. DFS demonstrates strong understanding of recursion and graph traversal, while Kahn's algorithm shows knowledge of topological sorting and queue-based processing. Being comfortable explaining both approaches signals solid graph fundamentals.