Course Schedule solution and explanation
Infosys
9 more videos on this problem
Course Schedule - Graph Adjacency List - Leetcode 207NeetCode · 15:47 · 559K views
Course Schedule | Deadlock detection | Graph coloring | Leetcode #207Techdose · 9:08 · 71K views
Course Schedule | Apple | Microsoft | Amazon | BFS | Graph Concepts & Qns - 12 | Leetcode 207codestorywithMIK · 14:14 · 36K views
Course Schedule (Detecting Cycles in a Graph) - Leetcode 207 - Graphs (Python)Greg Hogg · 13:32 · 32K views
Topological Sort Graph | Leetcode 207 | Course ScheduleNideesh Terapalli · 10:39 · 21K views
Leetcode - Course Schedule (Python)Timothy H Chang · 9:47 · 11K views
LeetCode 207: Course Schedule | Topological SortAbstracted Away · 12:02 · 9K views
Course Schedule (LeetCode 207) | Interview Essential | BFS, Queue, Cycle in a directed graphNikhil Lohia · 18:41 · 9K views
LeetCode 207 | Course Scheduleleetuition · 19:02 · 5K views
Course Schedule- LeetCode 207 - Python #leetcode #graphDeepti Talesra · 17:58 · 3K views
The problem
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.
- For example, the pair
[0, 1], indicates that to take course0you have to first take course1.
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 < numCourses- All the pairs prerequisites[i] are unique.
Approach overview
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.
Approach 1: Approach 1: Depth First Search (DFS) for Cycle Detection
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.
def canFinish(numCourses, prerequisites):
from collections import defaultdict
def dfs(course):
if visit[course] == 1:
return False
if visit[course] == 2:
return True
visit[course] = 1
for prereq in graph[course]:
if not dfs(prereq):
return False
visit[course] = 2
return True
graph = defaultdict(list)
for course, prereq in prerequisites:
graph[course].append(prereq)
visit = [0] * numCourses
for course in range(numCourses):
if not dfs(course):
return False
return True#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#define MAX_COURSES 2000
bool dfs(int course, int **graph, int *graphCol, int *visit) {
if (visit[course] == 1) return false;
if (visit[course] == 2) return true;
visit[course] = 1;
for (int i = 0; i < graphCol[course]; i++) {
if (!dfs(graph[course][i], graph, graphCol, visit))
return false;
}
visit[course] = 2;
return true;
}
bool canFinish(int numCourses, int **prerequisites, int prerequisitesSize, int *prerequisitesColSize) {
int *graph[MAX_COURSES];
int graphCol[MAX_COURSES] = {0};
for (int i = 0; i < prerequisitesSize; i++) {
int course = prerequisites[i][0];
int prereq = prerequisites[i][1];
graph[prereq] = realloc(graph[prereq], sizeof(int) * (++graphCol[prereq]));
graph[prereq][graphCol[prereq] - 1] = course;
}
int visit[MAX_COURSES] = {0};
for (int i = 0; i < numCourses; i++) {
if (!dfs(i, graph, graphCol, visit))
return false;
}
return true;
}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).
Approach 2: Approach 2: Kahn's Algorithm for Topological Sort
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.
import java.util.*;
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] inDegree = new int[numCourses];
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
for (int[] prerequisite : prerequisites) {
graph.get(prerequisite[1]).add(prerequisite[0]);
inDegree[prerequisite[0]]++;
}
Queue<Integer> zeroInDegreeQueue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
zeroInDegreeQueue.add(i);
}
}
int visitedCourses = 0;
while (!zeroInDegreeQueue.isEmpty()) {
int course = zeroInDegreeQueue.poll();
visitedCourses++;
for (int neighbor : graph.get(course)) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
zeroInDegreeQueue.add(neighbor);
}
}
}
return visitedCourses == numCourses;
}
}var canFinish = function(numCourses, prerequisites) {
let inDegree = new Array(numCourses).fill(0);
let graph = Array.from({length: numCourses}, () => []);
for (let [course, prereq] of prerequisites) {
graph[prereq].push(course);
inDegree[course]++;
}
let zeroInDegreeQueue = [];
for (let i = 0; i < numCourses; i++) {
if (inDegree[i] === 0) zeroInDegreeQueue.push(i);
}
let visitedCourses = 0;
while (zeroInDegreeQueue.length) {
let course = zeroInDegreeQueue.shift();
visitedCourses++;
for (let neighbor of graph[course]) {
inDegree[neighbor]--;
if (inDegree[neighbor] === 0) {
zeroInDegreeQueue.push(neighbor);
}
}
}
return visitedCourses === numCourses;
};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.
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.
Approach 3: Topological Sorting
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.
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> g(numCourses);
vector<int> indeg(numCourses);
for (auto& p : prerequisites) {
int a = p[0], b = p[1];
g[b].push_back(a);
++indeg[a];
}
queue<int> q;
for (int i = 0; i < numCourses; ++i) {
if (indeg[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int i = q.front();
q.pop();
--numCourses;
for (int j : g[i]) {
if (--indeg[j] == 0) {
q.push(j);
}
}
}
return numCourses == 0;
}
};function canFinish(numCourses: number, prerequisites: number[][]): boolean {
const g: number[][] = Array.from({ length: numCourses }, () => []);
const indeg: number[] = Array(numCourses).fill(0);
for (const [a, b] of prerequisites) {
g[b].push(a);
indeg[a]++;
}
const q: number[] = [];
for (let i = 0; i < numCourses; ++i) {
if (indeg[i] === 0) {
q.push(i);
}
}
for (const i of q) {
--numCourses;
for (const j of g[i]) {
if (--indeg[j] === 0) {
q.push(j);
}
}
}
return numCourses === 0;
}public class Solution {
public bool CanFinish(int numCourses, int[][] prerequisites) {
var g = new List<int>[numCourses];
for (int i = 0; i < numCourses; ++i) {
g[i] = new List<int>();
}
var indeg = new int[numCourses];
foreach (var p in prerequisites) {
int a = p[0], b = p[1];
g[b].Add(a);
++indeg[a];
}
var q = new Queue<int>();
for (int i = 0; i < numCourses; ++i) {
if (indeg[i] == 0) {
q.Enqueue(i);
}
}
while (q.Count > 0) {
int i = q.Dequeue();
--numCourses;
foreach (int j in g[i]) {
if (--indeg[j] == 0) {
q.Enqueue(j);
}
}
}
return numCourses == 0;
}
}func canFinish(numCourses int, prerequisites [][]int) bool {
g := make([][]int, numCourses)
indeg := make([]int, numCourses)
for _, p := range prerequisites {
a, b := p[0], p[1]
g[b] = append(g[b], a)
indeg[a]++
}
q := []int{}
for i, x := range indeg {
if x == 0 {
q = append(q, i)
}
}
for len(q) > 0 {
i := q[0]
q = q[1:]
numCourses--
for _, j := range g[i] {
indeg[j]--
if indeg[j] == 0 {
q = append(q, j)
}
}
}
return numCourses == 0
}use std::collections::VecDeque;
impl Solution {
pub fn can_finish(mut num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
let mut g: Vec<Vec<i32>> = vec![vec![]; num_courses as usize];
let mut indeg: Vec<i32> = vec![0; num_courses as usize];
for p in prerequisites {
let a = p[0] as usize;
let b = p[1] as usize;
g[b].push(a as i32);
indeg[a] += 1;
}
let mut q: VecDeque<usize> = VecDeque::new();
for i in 0..num_courses {
if indeg[i as usize] == 0 {
q.push_back(i as usize);
}
}
while let Some(i) = q.pop_front() {
num_courses -= 1;
for &j in &g[i] {
let j = j as usize;
indeg[j] -= 1;
if indeg[j] == 0 {
q.push_back(j);
}
}
}
num_courses == 0
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Course Schedule easy or hard?
Course Schedule is considered a medium-level problem on LeetCode. The difficulty comes from recognizing that the prerequisite relationships form a directed graph and that the task reduces to cycle detection or topological sorting.
Course Schedule Python/Java solution
Python solutions commonly implement DFS with a visited state array or Kahn's algorithm using collections.deque. Java implementations often use adjacency lists with ArrayList and a Queue for topological sorting. Both approaches run in O(V+E) time.
How to solve Course Schedule in O(n)?
Treat courses as nodes in a directed graph and prerequisites as edges. Build an adjacency list and either run DFS to detect cycles or apply Kahn's algorithm with in-degree counting. Both approaches process each vertex and edge once, giving O(V+E) time complexity.
What is the best approach for Course Schedule?
The best approach is detecting cycles in the directed prerequisite graph. Both DFS-based cycle detection and Kahn's topological sort solve the problem in O(V+E) time. DFS tracks recursion states to detect back edges, while Kahn's algorithm processes nodes with zero in-degree using a queue.
Is Course Schedule asked at Google/Amazon/Meta?
Course Schedule is a classic graph problem frequently asked in technical interviews at companies like Amazon, Google, Meta, and Microsoft. It tests understanding of graph traversal, cycle detection, and topological sorting.
What data structure is used in Course Schedule?
The core data structure is a directed graph represented with an adjacency list. DFS solutions also use recursion stacks or state arrays, while Kahn's algorithm uses an in-degree array and a queue for BFS-style processing.
What is the time complexity of Course Schedule?
The optimal solutions run in O(V+E) time, where V is the number of courses and E is the number of prerequisite pairs. Each node and edge in the graph is processed at most once during DFS traversal or during Kahn's topological sort.