Graphs · LC #207
Course Schedule
Determine if a course schedule is possible (no circular prerequisites) by detecting cycles in a directed graph using 3-state DFS coloring.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
There are `numCourses` courses labeled `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates you must take course `bi` first to take course `ai`. Return `true` if you can finish all courses, or `false` if a cycle exists.
Sample I/O
Input: numCourses=2, prerequisites=[[1,0]] Output: true Input: numCourses=2, prerequisites=[[1,0],[0,1]] Output: false (cycle: 0→1→0)
Time: O(V+E) · Space: O(V+E)
Intuition
How to Think About It
Intuition
Course prerequisites form a directed graph. You can finish all courses if and only if the graph is a DAG (no cycles). DFS with 3-state coloring detects back edges (cycle indicators): 0=unvisited, 1=in current DFS stack (visiting), 2=fully processed (no cycle through this node).
Core Concept
3-color DFS. State 1 (gray/visiting) marks nodes on the current recursion stack. If DFS reaches a gray node, a back edge - and therefore a cycle - exists. State 2 (black/done) means the entire subtree was explored with no cycle; skip on re-encounter. Kahn's algorithm (BFS + in-degree) is the alternative topological sort approach.
When to use
Cycle detection in directed graphs; validating DAG property; any task-scheduling or dependency-resolution problem where circular dependencies are invalid.
When NOT to use
Undirected graphs (use simple visited boolean - revisiting parent is normal). When you need the actual topological ordering (use Course Schedule II). When graph edges are weighted (different algorithms).
Key Insights
What to Know Cold
- 3-state coloring (unvisited/visiting/done) is required; 2-state (visited/unvisited) incorrectly flags normal back-tracking as cycles in directed graphs.
- State 2 (done) acts as a memoization shortcut - entire subtree verified cycle-free, skip re-processing.
- Kahn's BFS alternative: count in-degrees, process zero-in-degree nodes in queue, cycle exists if queue empties before processing all nodes.
- The graph direction matters: [a, b] means b→a (b is prerequisite of a), not a→b.
- Each edge/node is processed at most once due to state transitions - O(V+E) guaranteed.
1 example
Worked Examples
3-state DFS cycle detection
numCourses=2, prerequisites=[[1,0],[0,1]] - mutual dependency creates a cycle.
Build adjacency list; DFS with state array; return false if any gray node encountered.
function canFinish(n: number, prereqs: number[][]): boolean {
const graph: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of prereqs) graph[b].push(a);
const state = new Array(n).fill(0); // 0=unvisited, 1=visiting, 2=done
function dfs(v: number): boolean {
if (state[v] === 1) return true; // back edge → cycle
if (state[v] === 2) return false; // already processed
state[v] = 1;
for (const nb of graph[v]) if (dfs(nb)) return true;
state[v] = 2;
return false;
}
for (let i = 0; i < n; i++) if (dfs(i)) return false;
return true;
}Output: false (cycle detected)
Top-3 most-asked graph problem at Amazon and Google. Interviewers expect you to articulate why 3-state (not 2-state) coloring is required for directed cycle detection.