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 finish all courses. In graph terms, courses form a directed graph and the question becomes: does the graph contain a cycle?

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

This approach models the courses as a directed graph using an adjacency list and runs Depth-First Search from each node. During DFS, track three states for every node: unvisited, visiting (currently in the recursion stack), and visited. If DFS reaches a node already marked as visiting, a cycle exists, meaning two courses depend on each other indirectly and completion becomes impossible.

The key insight is that cycles in a directed graph can be detected using the recursion stack. Each DFS call explores neighbors and marks nodes as visited only after all prerequisites are processed. If the traversal finishes without encountering a back edge, the graph is acyclic and all courses can be completed. This method is intuitive if you already think about problems in terms of recursion and graph traversal.

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

This method uses Breadth-First Search combined with Topological Sort. Start by computing the indegree of each course (number of prerequisites). Push all courses with indegree 0 into a queue because they can be taken immediately.

Repeatedly remove a course from the queue, simulate completing it, and reduce the indegree of its dependent courses. Whenever a dependent course reaches indegree 0, add it to the queue. If you process exactly numCourses nodes, the graph has no cycles and a valid course order exists. If some nodes remain with non‑zero indegree, they are part of a cycle.

Kahn's algorithm works because topological ordering only exists in directed acyclic graphs (DAGs). The queue-based process effectively removes nodes layer by layer while verifying that prerequisites can be satisfied.

Recommended for interviews: Both approaches run in optimal O(V + E) time, where V is the number of courses and E is the number of prerequisite relationships. Interviewers commonly expect either DFS cycle detection or Kahn's topological sort. DFS demonstrates strong understanding of recursion and graph states, while Kahn's algorithm shows familiarity with indegree processing and queue-based graph traversal. Being comfortable with both makes cycle detection problems in directed graphs much easier to recognize.