Approach Summary
Detect cycle in directed graph using DFS (3-color states) or Kahn's BFS topological sort. If cycle exists, impossible.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: DFS Cycle Detection (Call Stack / 3-Coloring) | O(V + E) | O(V + E) | Depth-first search tracking nodes currently in the recursion call stack to detect back-edges indicating directed cycles. |
| 2 Approach 2: BFS / Kahn's Algorithm (Topological Sort) | O(V + E) | O(V + E) | Calculates in-degrees for all courses and uses a queue to progressively strip completed courses, checking if all courses are resolved. |
Step 1: Baseline
Approach 1: DFS Cycle Detection (Call Stack / 3-Coloring)
Time: O(V + E)
Space: O(V + E)
1. Build adjacency list where `graph[prereq]` points to downstream `course`. 2. Maintain two boolean arrays: `visited` (globally processed) and `callStack` (currently on the active DFS path). 3. For each course `i` from 0 to `numCourses - 1`: - If not visited, run `dfs(i)`. - In `dfs(v)`: mark `visited[v] = true` and `callStack[v] = true`. - For each neighbor of `v`, if it is already in `callStack`, a cycle is detected, return true. - If not visited, recursively call `dfs(neighbor)`. If it finds a cycle, propagate true. - Before returning, unmark `callStack[v] = false` (backtrack). 4. If any DFS detects a cycle, return false; otherwise return true.
Approach 1: DFS Cycle Detection (Call Stack / 3-Coloring) Implementation
Approach 1: DFS Cycle Detection (Call Stack / 3-Coloring)
class Solution {
public boolean dfs(int v, ArrayList<ArrayList<Integer>> graph, boolean[] visited, boolean[] callStack ){
visited[v] = true;
callStack[v] = true;
ArrayList<Integer> neighbors = graph.get(v);
for(int neighbor : neighbors){
if(!visited[neighbor]){
if(dfs(neighbor, graph, visited, callStack)){
return true;
}
} else if(callStack[neighbor]){
return true;
}
}
callStack[v] = false;
return false;
}
public boolean canFinish(int numCourses, int[][] prerequisites) {
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for(int i = 0; i < numCourses; i++){
graph.add(new ArrayList<>());
}
for(int[] prerequisite : prerequisites){
int course = prerequisite[0];
int prerequisiteCourse = prerequisite[1];
graph.get(prerequisiteCourse).add(course);
}
boolean visited[] = new boolean[numCourses];
boolean callStack[] = new boolean[numCourses];
for(int i = 0; i < numCourses; i++){
if(!visited[i]){
if(dfs(i, graph, visited, callStack)){
return false;
}
}
}
return true;
}
}class Solution {
public:
bool dfs(int v, vector<vector<int>>& graph, vector<bool>& visited, vector<bool>& callStack) {
visited[v] = true;
callStack[v] = true;
vector<int>& neighbors = graph[v];
for (int neighbor : neighbors) {
if (!visited[neighbor]) {
if (dfs(neighbor, graph, visited, callStack)) {
return true;
}
} else if (callStack[neighbor]) {
return true;
}
}
callStack[v] = false;
return false;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
for (vector<int>& prerequisite : prerequisites) {
int course = prerequisite[0];
int prerequisiteCourse = prerequisite[1];
graph[prerequisiteCourse].push_back(course);
}
vector<bool> visited(numCourses, false);
vector<bool> callStack(numCourses, false);
for (int i = 0; i < numCourses; i++) {
if (!visited[i]) {
if (dfs(i, graph, visited, callStack)) {
return false;
}
}
}
return true;
}
};class Solution:
def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
graph = [[] for _ in range(numCourses)]
for course, prereq in prerequisites:
graph[prereq].append(course)
visited = [False] * numCourses
call_stack = [False] * numCourses
def dfs(v):
visited[v] = True
call_stack[v] = True
for neighbor in graph[v]:
if not visited[neighbor]:
if dfs(neighbor):
return True
elif call_stack[neighbor]:
return True
call_stack[v] = False
return False
for i in range(numCourses):
if not visited[i]:
if dfs(i):
return False
return Truevar canFinish = function(numCourses, prerequisites) {
const graph = Array.from({ length: numCourses }, () => []);
for (const [course, prereq] of prerequisites) {
graph[prereq].push(course);
}
const visited = new Array(numCourses).fill(false);
const callStack = new Array(numCourses).fill(false);
function dfs(v) {
visited[v] = true;
callStack[v] = true;
for (const neighbor of graph[v]) {
if (!visited[neighbor]) {
if (dfs(neighbor)) return true;
} else if (callStack[neighbor]) {
return true;
}
}
callStack[v] = false;
return false;
}
for (let i = 0; i < numCourses; i++) {
if (!visited[i]) {
if (dfs(i)) return false;
}
}
return true;
}; Step 2: Most Optimized
Approach 2: BFS / Kahn's Algorithm (Topological Sort)
Time: O(V + E)
Space: O(V + E)
1. Build adjacency list where `graph[prereq]` holds all dependent courses. 2. Compute `inDegree[course]` = number of incoming prerequisite edges. 3. Enqueue all vertices with `inDegree[i] == 0` (courses with zero prerequisites). 4. Pop vertex `curr` from queue and append to topological sort order. 5. For each neighbor of `curr`, decrement `inDegree[neighbor]`. If it reaches 0, enqueue `neighbor`. 6. When the queue is empty, if `topologicalSort.size() == numCourses`, the graph is an acyclic DAG and all courses can be completed.
Approach 2: BFS / Kahn's Algorithm (Topological Sort) Implementation
Approach 2: BFS / Kahn's Algorithm (Topological Sort)
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for(int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
for(int[] p : prerequisites) graph.get(p[1]).add(p[0]);
int inDegree[] = new int[numCourses];
for(ArrayList<Integer> list : graph) {
for(int elem : list) inDegree[elem]++;
}
Queue<Integer> q = new LinkedList<>();
for(int i = 0; i < numCourses; i++) {
if(inDegree[i] == 0) q.add(i);
}
int count = 0;
while(!q.isEmpty()){
int curr = q.poll();
count++;
for(int neighbor : graph.get(curr)){
if(--inDegree[neighbor] == 0) q.add(neighbor);
}
}
return count == numCourses;
}
}class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
for (auto& p : prerequisites) graph[p[1]].push_back(p[0]);
vector<int> inDegree(numCourses, 0);
for(auto& list : graph) {
for(int elem : list) inDegree[elem]++;
}
queue<int> q;
for(int i = 0; i < numCourses; i++) {
if(inDegree[i] == 0) q.push(i);
}
int count = 0;
while(!q.empty()){
int curr = q.front();
q.pop();
count++;
for(int neighbor : graph[curr]){
if(--inDegree[neighbor] == 0) q.push(neighbor);
}
}
return count == numCourses;
}
};from collections import deque
class Solution:
def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
adj = [[] for _ in range(numCourses)]
in_degree = [0] * numCourses
for course, prereq in prerequisites:
adj[prereq].append(course)
in_degree[course] += 1
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
count = 0
while queue:
curr = queue.popleft()
count += 1
for neighbor in adj[curr]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return count == numCoursesvar canFinish = function(numCourses, prerequisites) {
const adj = Array.from({ length: numCourses }, () => []);
const inDegree = new Array(numCourses).fill(0);
for (const [course, prereq] of prerequisites) {
adj[prereq].push(course);
inDegree[course]++;
}
const queue = [];
for (let i = 0; i < numCourses; i++) {
if (inDegree[i] === 0) queue.push(i);
}
let count = 0;
while (queue.length > 0) {
const curr = queue.shift();
count++;
for (const neighbor of adj[curr]) {
if (--inDegree[neighbor] === 0) queue.push(neighbor);
}
}
return count === numCourses;
};Edge Cases to Watch
- No prerequisites (prerequisites is empty) — all courses can be finished immediately, return true
- Self-dependency [0, 0] — immediate cycle of length 1, return false
- Mutual dependency [0, 1] and [1, 0] — 2-cycle, return false
- Disconnected components — multiple independent sets of courses, all must be cycle-free
Algorithmic Pattern
View Pattern Guide →
Master the Topological Sort Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Topological Sort pattern.
Framework: Topological Sort • Interview Prep: Tested at FAANG •
Explore all Topological Sort problems & invariants →
How to Recognize This Pattern
- Prerequisite ordering
- Can all courses be taken?
Complexity Analysis
Time Complexity
O(V + E)
Space Complexity
O(V + E)
Tags
Graph DFS BFS Topological Sort
Frequently Asked Questions
What is the optimal time and space complexity for Course Schedule?
The optimal solution for Course Schedule achieves O(V + E) runtime complexity and requires O(V + E) auxiliary space. Time Complexity is O(V + E) where V = numCourses and E = prerequisites.length. Constructing the adjacency list and in-degree array takes O(V + E), and every node and edge is processed at most once during traversal. Space Complexity is O(V + E) to store the adjacency list graph representation, in-degree counts, and traversal queue/stack.
How do I identify that Course Schedule requires the Topological Sort pattern?
In technical interviews, look for key problem signals: Prerequisite ordering; Can all courses be taken?. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Topological Sort strategy.
What critical edge cases must be handled in Course Schedule?
Essential edge cases to verify include: No prerequisites (prerequisites is empty) — all courses can be finished immediately, return true; Self-dependency [0, 0] — immediate cycle of length 1, return false; Mutual dependency [0, 1] and [1, 0] — 2-cycle, return false; Disconnected components — multiple independent sets of courses, all must be cycle-free. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Course Schedule?
Course Schedule is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Facebook, Google, Zenefits.