There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
[0, 1], indicates that to take course 0 you have to first take course 1.Return true if you can finish all courses. Otherwise, return false.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Constraints:
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesProblem 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.
This problem can be translated into finding cycles in a directed graph. Each course is a node, and a prerequisite is a directed edge from one course to another. If there is a cycle in the graph, it means there is no way to complete all courses because a course depends on itself indirectly.
To detect cycles, we perform a Depth First Search (DFS). We maintain a visitation state for each node: 0 = unvisited, 1 = visiting (currently in stack), and 2 = visited. During DFS, if we encounter a node that is already in the visiting state, it implies the presence of a cycle.
We utilize a recursion stack to perform DFS on each node. When a node is being processed, it is marked as 'visiting'. If during the traversal we encounter a node that is already marked 'visiting', a cycle is present, and we return False. After processing, nodes are marked 'visited'. This implementation correctly detects cycles in the directed graph of course dependencies.
Time Complexity: O(V+E) where V is the number of courses and E is the number of prerequisites. We traverse each node and edge once.
Space Complexity: O(V+E) for the graph representation and recursion stack (in worst case).
Kahn's Algorithm provides an alternative way to perform a topological sort and can be employed to detect cycles. The idea is to repeatedly remove nodes with no incoming edges (no prerequisites) and reduce the incoming edges of each node's neighbors. If we are left with unvisited nodes, these form a cycle.
Initially, we compute the in-degree (number of incoming edges) for each node. Nodes with zero in-degree are added to a queue. We dequeue a node, add it to the topological order, and reduce the in-degree of its neighbors.
In this Java implementation of Kahn's Algorithm, we initialize in-degrees for all courses. Nodes with zero in-degree are processed first. Processing involves adding them to an output list and decreasing the in-degree of their neighboring nodes. If a neighboring node's in-degree drops to zero, it becomes eligible for processing next.
Java
JavaScript
Time Complexity: O(V+E) where V is the number of courses and E is the number of prerequisites. Each node and edge are processed exactly once.
Space Complexity: O(V+E) for the graph and queue structures.
For this problem, we can consider the courses as nodes in a graph, and prerequisites as edges in the graph. Thus, we can transform this problem into determining whether there is a cycle in the directed graph.
Specifically, we can use the idea of topological sorting. For each node with an in-degree of 0, we reduce the in-degree of its out-degree nodes by 1, until all nodes have been traversed.
If all nodes have been traversed, it means there is no cycle in the graph, and we can complete all courses; otherwise, we cannot complete all courses.
The time complexity is O(n + m), and the space complexity is O(n + m). Here, n and m are the number of courses and prerequisites respectively.
| Approach | Complexity |
|---|---|
| Approach 1: Depth First Search (DFS) for Cycle Detection | Time Complexity: |
| Approach 2: Kahn's Algorithm for Topological Sort | Time Complexity: |
| Topological Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Cycle Detection | O(V+E) | O(V+E) | When detecting cycles in a directed graph using recursion and adjacency lists |
| Kahn's Algorithm (Topological Sort) | O(V+E) | O(V+E) | When you want a BFS-based solution using in-degree counts and a queue |
Course Schedule - Graph Adjacency List - Leetcode 207 • NeetCode • 533,425 views views
Watch 9 more video solutions →Practice Course Schedule with our built-in code editor and test cases.
Practice on FleetCode