Course Schedule (LeetCode 207)
You have numCourses courses to complete, numbered 0 through numCourses - 1, and a list prerequisites where each entry [ai, bi] means course bi must be completed before course ai.
- So an entry
[0, 1]means course1has to be finished before course0.
Decide whether every course can be completed at all — return true if a valid completion order exists, and false otherwise.
Worked Examples
numCourses = 2, prerequisites = [[1,0]]truenumCourses = 2, prerequisites = [[1,0],[0,1]]false⚖️Formal Constraints & Bounds
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesAll the pairs prerequisites[i] are unique.
Core Insight
Directed cycle detection via in-degree tracking prevents deadlocks in linear time.
Real-World Scenario & Production Applications
Build system package dependency resolution (npm, bazel, make), compiler task DAG(Directed Acyclic Graph) scheduling.
Subproblems & Recurrence Decomposition3 Phases
Construct directed graph from edge pairs and compute in-degree for every vertex: in_degree[v] = number of prerequisite dependencies.
adj = defaultdict(list)
in_degree = [0] * numCourses
for dest, src in prerequisites:
adj[src].append(dest)
in_degree[dest] += 1Step-by-Step Execution Trace Table
| Queue (0 In-Degree) | Popped Course | Decremented Dependents | In-Degree State |
|---|---|---|---|
| [0] | Course 0 | in_degree[1] -> 0 | in_degree[1]=0 |
| [1] | Course 1 | None | Completed |
| Result | Count = 2 == numCourses (2) -> True | - | - |
numCourses = 2, prerequisites = [[1,0]]true| Queue (0 In-Degree) | Popped Course | Decremented Dependents | In-Degree State |
|---|---|---|---|
| [0] | Course 0 | in_degree[1] -> 0 | in_degree[1]=0 |
| [1] | Course 1 | None | Completed |
| Result | Count = 2 == numCourses (2) -> True | - | - |
| 1 | WHITE, GREY, BLACK = 0, 1, 2 |
| 2 | state = [WHITE] * numCourses |
| 3 | adj[prereq].append(course) for every pair |
| 4 | def dfs(u): |
| 5 | state[u] = GREY |
| 6 | for v in adj[u]: |
| 7 | if state[v] == GREY: |
| 8 | return True |
| 9 | if state[v] == WHITE and dfs(v): |
| 10 | return True |
| 11 | state[u] = BLACK |
| 12 | return False |
| 13 | for node in range(numCourses): |
| 14 | if state[node] == WHITE and dfs(node): |
| 15 | return False |
| 16 | return True |
Conceptual Narrative
Course Schedule models prerequisites as a directed graph: every course can be finished exactly when that graph has no directed cycle.
🧭 Conceptual Foundation & Pattern Intuition
An edge prereq -> course means "take prereq first". A cycle such as 0 -> 1 -> 0 means each course waits on the other, so neither can ever start. The Cycle Detection card finds such a loop with a depth-first search that gives every course one of three states: WHITE (not visited), GREY (on the current search path) and BLACK (finished, and known to reach no cycle).
🏟️ The Analogy: Following a Chain of Prerequisites With Your Finger
Start at a course and follow its arrows to the courses it unlocks, marking each course you pass as "in progress" (GREY). If your finger lands on a course that is already in progress, you have walked in a circle: that is a cycle. When every arrow out of a course has been followed without finding one, stamp the course "done" (BLACK). A later walk that reaches a done course can stop there, because nothing past it loops.
🔑 Why It Works
Only GREY means a cycle. Reaching a BLACK course again through a second path is safe, which is why a single visited flag is not enough.
Inverted prerequisite edge direction: Input
[a, b]means 'take b before a' (). Creating edge inverts the dependency DAG(Directed Acyclic Graph) and yields erroneous schedules.Ignoring disconnected graph components: Failing to seed the queue with ALL zero-in-degree nodes across all disjoint components leaves valid subgraphs unexplored.
Self-loops and parallel edges: A course listing itself as a prerequisite (
[1, 1]) creates an immediate cycle of length 1. Ensure edge deduplication or proper in-degree accounting.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Each pair [ai, bi] means course bi "must be completed before" course ai, and the question is "whether every course can be completed at all": the pairs are the edges of a directed graph, and a valid order exists exactly when that graph has no cycle. Only a yes/no is asked, not the order itself, so this is Cycle Detection with three colors.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The GREY courses are exactly the courses on the current dfs path, and every course reachable from a BLACK course is BLACK and on no cycle. So a neighbour with state[v] == GREY is an edge back into the path (a cycle), a BLACK neighbour is skipped, and a WHITE one is searched.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
if state[v] == GREY, not "already visited": with one visited flag, a course reached again through a second path looks like a cycle, andnumCourses = 3,prerequisites = [[1,0],[2,0],[2,1]]returnsfalseinstead oftrue.state[u] = BLACKgoes after thefor v in adj[u]loop: a course marked finished on entry is skipped when a later edge comes back to it, so Example 2's cycle is never seen.for node in range(numCourses): start adfsat every course stillWHITE, because a cycle can sit in a part of the graph that course 0 never reaches.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"The pairs form a directed graph, and every course can be finished exactly when that graph has no cycle, so I'd use Cycle Detection with three colors. Every course starts white. When my depth-first search enters a course it turns grey, meaning it is on the current path, and once all its neighbours are done it turns black. Reaching a grey course means an edge back into my own path, so that path plus the edge is a cycle and I return false. A black course can't lead to a cycle, so I skip it. The trap is using one visited flag: reaching a finished course again through a second path is not a cycle, so grey and black must stay different. I start a search from every white course, so no part of the graph is missed. It's O(V plus E) time and space."
Complexity & Mathematical Proof
O(V + E)
Look at the code: building adj reads each of the E pairs once, and state and adj are V-sized lists. dfs(u) is only called on a WHITE course and turns it GREY at once, so it runs at most once per course: at most V calls in total. Each call walks adj[u] once with O(1) work per entry (the GREY test and the WHITE test), so all the loops together read each pair once. The outer for node in range(numCourses) adds V constant-time checks. Total: O(V + E).
O(V + E)
adj holds V lists with E entries in total, and state holds V colors. The recursion stack holds the GREY courses of the current path, at most V frames on a long chain. The output is one boolean.
T(V, E) = V + E (build adj) + V (dfs calls) + E (adjacency entries) + V (outer loop) = O(V + E)
Derivation Progression
state = [WHITE] * numCourses and adj: O(V); for course, prereq in prerequisites: O(E)
Each pair adds one edge prereq -> course to adj.
dfs(u) runs only when state[u] == WHITE and sets state[u] = GREY first: at most V calls
A course never goes back to WHITE, so no course is entered twice.
sum over dfs calls of len(adj[u]) = E, O(1) per entry
The for v in adj[u] loop runs once per call, and each entry costs one GREY test and one WHITE test.
for node in range(numCourses): V checks
A course that is already GREY or BLACK costs one comparison; only a WHITE one opens a search.
Variable Definitions
Number of courses, numCourses
Number of prerequisite pairs, len(prerequisites)
Memory Architecture & Bounds
O(V): the GREY courses on the current path, V frames on a chain of courses
O(V + E): adj holds E entries in V lists, and state holds V colors
O(1): one boolean
Boundary Best / Worst Cases
to build adj; the search itself can stop early, when the first path it follows already closes a cycle.
.
: no cycle, so every course is searched and every pair is read before return True.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Scale signal: a separate walk from every course costs , about steps here, which still passes, but real dependency graphs (build targets, packages) have far more nodes, and only the one-pass Cycle Detection stays linear.
courses, pairs: adj holds 5000 entries and state 2000 colors. A chain of 2000 courses makes the recursion 2000 frames deep, past CPython's default limit of 1000, so the depth, not the time, is what breaks first.
Deep graphs: production code runs the same three colors on an explicit stack of (node, next neighbour) frames instead of recursion. A bare false is hard to act on: the GREY courses at the moment the cycle is found are the cycle's path, so keep them to report which dependencies form the loop.
Core Algorithmic State Invariants
- Example 2, Step by Step
prerequisites = [[1,0],[0,1]] gives adj[0] = [1] and adj[1] = [0]. dfs(0) sets state[0] = GREY and calls dfs(1), which sets state[1] = GREY and reads v = 0: state[0] == GREY, an edge back into the path 0 -> 1, so canFinish returns false.
- Edge Direction Doesn't Change the Answer
Reversing every pair turns each cycle into the same cycle walked backwards, so building adj[course].append(prereq) instead would return the same true or false. The direction only matters when the order itself must be returned.
Course Schedule (LeetCode 207)
You have numCourses courses to complete, numbered 0 through numCourses - 1, and a list prerequisites where each entry [ai, bi] means course bi must be completed before course ai.
- So an entry
[0, 1]means course1has to be finished before course0.
Decide whether every course can be completed at all — return true if a valid completion order exists, and false otherwise.
Worked Examples
numCourses = 2, prerequisites = [[1,0]]truenumCourses = 2, prerequisites = [[1,0],[0,1]]false⚖️Formal Constraints & Bounds
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesAll the pairs prerequisites[i] are unique.
Core Insight
Directed cycle detection via in-degree tracking prevents deadlocks in linear time.
Real-World Scenario & Production Applications
Build system package dependency resolution (npm, bazel, make), compiler task DAG(Directed Acyclic Graph) scheduling.
Subproblems & Recurrence Decomposition3 Phases
Construct directed graph from edge pairs and compute in-degree for every vertex: in_degree[v] = number of prerequisite dependencies.
adj = defaultdict(list)
in_degree = [0] * numCourses
for dest, src in prerequisites:
adj[src].append(dest)
in_degree[dest] += 1Step-by-Step Execution Trace Table
| Queue (0 In-Degree) | Popped Course | Decremented Dependents | In-Degree State |
|---|---|---|---|
| [0] | Course 0 | in_degree[1] -> 0 | in_degree[1]=0 |
| [1] | Course 1 | None | Completed |
| Result | Count = 2 == numCourses (2) -> True | - | - |
numCourses = 2, prerequisites = [[1,0]]true| Queue (0 In-Degree) | Popped Course | Decremented Dependents | In-Degree State |
|---|---|---|---|
| [0] | Course 0 | in_degree[1] -> 0 | in_degree[1]=0 |
| [1] | Course 1 | None | Completed |
| Result | Count = 2 == numCourses (2) -> True | - | - |
| 1 | WHITE, GREY, BLACK = 0, 1, 2 |
| 2 | state = [WHITE] * numCourses |
| 3 | adj[prereq].append(course) for every pair |
| 4 | def dfs(u): |
| 5 | state[u] = GREY |
| 6 | for v in adj[u]: |
| 7 | if state[v] == GREY: |
| 8 | return True |
| 9 | if state[v] == WHITE and dfs(v): |
| 10 | return True |
| 11 | state[u] = BLACK |
| 12 | return False |
| 13 | for node in range(numCourses): |
| 14 | if state[node] == WHITE and dfs(node): |
| 15 | return False |
| 16 | return True |
Conceptual Narrative
Course Schedule models prerequisites as a directed graph: every course can be finished exactly when that graph has no directed cycle.
🧭 Conceptual Foundation & Pattern Intuition
An edge prereq -> course means "take prereq first". A cycle such as 0 -> 1 -> 0 means each course waits on the other, so neither can ever start. The Cycle Detection card finds such a loop with a depth-first search that gives every course one of three states: WHITE (not visited), GREY (on the current search path) and BLACK (finished, and known to reach no cycle).
🏟️ The Analogy: Following a Chain of Prerequisites With Your Finger
Start at a course and follow its arrows to the courses it unlocks, marking each course you pass as "in progress" (GREY). If your finger lands on a course that is already in progress, you have walked in a circle: that is a cycle. When every arrow out of a course has been followed without finding one, stamp the course "done" (BLACK). A later walk that reaches a done course can stop there, because nothing past it loops.
🔑 Why It Works
Only GREY means a cycle. Reaching a BLACK course again through a second path is safe, which is why a single visited flag is not enough.
Inverted prerequisite edge direction: Input
[a, b]means 'take b before a' (). Creating edge inverts the dependency DAG(Directed Acyclic Graph) and yields erroneous schedules.Ignoring disconnected graph components: Failing to seed the queue with ALL zero-in-degree nodes across all disjoint components leaves valid subgraphs unexplored.
Self-loops and parallel edges: A course listing itself as a prerequisite (
[1, 1]) creates an immediate cycle of length 1. Ensure edge deduplication or proper in-degree accounting.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Each pair [ai, bi] means course bi "must be completed before" course ai, and the question is "whether every course can be completed at all": the pairs are the edges of a directed graph, and a valid order exists exactly when that graph has no cycle. Only a yes/no is asked, not the order itself, so this is Cycle Detection with three colors.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The GREY courses are exactly the courses on the current dfs path, and every course reachable from a BLACK course is BLACK and on no cycle. So a neighbour with state[v] == GREY is an edge back into the path (a cycle), a BLACK neighbour is skipped, and a WHITE one is searched.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
if state[v] == GREY, not "already visited": with one visited flag, a course reached again through a second path looks like a cycle, andnumCourses = 3,prerequisites = [[1,0],[2,0],[2,1]]returnsfalseinstead oftrue.state[u] = BLACKgoes after thefor v in adj[u]loop: a course marked finished on entry is skipped when a later edge comes back to it, so Example 2's cycle is never seen.for node in range(numCourses): start adfsat every course stillWHITE, because a cycle can sit in a part of the graph that course 0 never reaches.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"The pairs form a directed graph, and every course can be finished exactly when that graph has no cycle, so I'd use Cycle Detection with three colors. Every course starts white. When my depth-first search enters a course it turns grey, meaning it is on the current path, and once all its neighbours are done it turns black. Reaching a grey course means an edge back into my own path, so that path plus the edge is a cycle and I return false. A black course can't lead to a cycle, so I skip it. The trap is using one visited flag: reaching a finished course again through a second path is not a cycle, so grey and black must stay different. I start a search from every white course, so no part of the graph is missed. It's O(V plus E) time and space."
Complexity & Mathematical Proof
O(V + E)
Look at the code: building adj reads each of the E pairs once, and state and adj are V-sized lists. dfs(u) is only called on a WHITE course and turns it GREY at once, so it runs at most once per course: at most V calls in total. Each call walks adj[u] once with O(1) work per entry (the GREY test and the WHITE test), so all the loops together read each pair once. The outer for node in range(numCourses) adds V constant-time checks. Total: O(V + E).
O(V + E)
adj holds V lists with E entries in total, and state holds V colors. The recursion stack holds the GREY courses of the current path, at most V frames on a long chain. The output is one boolean.
T(V, E) = V + E (build adj) + V (dfs calls) + E (adjacency entries) + V (outer loop) = O(V + E)
Derivation Progression
state = [WHITE] * numCourses and adj: O(V); for course, prereq in prerequisites: O(E)
Each pair adds one edge prereq -> course to adj.
dfs(u) runs only when state[u] == WHITE and sets state[u] = GREY first: at most V calls
A course never goes back to WHITE, so no course is entered twice.
sum over dfs calls of len(adj[u]) = E, O(1) per entry
The for v in adj[u] loop runs once per call, and each entry costs one GREY test and one WHITE test.
for node in range(numCourses): V checks
A course that is already GREY or BLACK costs one comparison; only a WHITE one opens a search.
Variable Definitions
Number of courses, numCourses
Number of prerequisite pairs, len(prerequisites)
Memory Architecture & Bounds
O(V): the GREY courses on the current path, V frames on a chain of courses
O(V + E): adj holds E entries in V lists, and state holds V colors
O(1): one boolean
Boundary Best / Worst Cases
to build adj; the search itself can stop early, when the first path it follows already closes a cycle.
.
: no cycle, so every course is searched and every pair is read before return True.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Scale signal: a separate walk from every course costs , about steps here, which still passes, but real dependency graphs (build targets, packages) have far more nodes, and only the one-pass Cycle Detection stays linear.
courses, pairs: adj holds 5000 entries and state 2000 colors. A chain of 2000 courses makes the recursion 2000 frames deep, past CPython's default limit of 1000, so the depth, not the time, is what breaks first.
Deep graphs: production code runs the same three colors on an explicit stack of (node, next neighbour) frames instead of recursion. A bare false is hard to act on: the GREY courses at the moment the cycle is found are the cycle's path, so keep them to report which dependencies form the loop.
Core Algorithmic State Invariants
- Example 2, Step by Step
prerequisites = [[1,0],[0,1]] gives adj[0] = [1] and adj[1] = [0]. dfs(0) sets state[0] = GREY and calls dfs(1), which sets state[1] = GREY and reads v = 0: state[0] == GREY, an edge back into the path 0 -> 1, so canFinish returns false.
- Edge Direction Doesn't Change the Answer
Reversing every pair turns each cycle into the same cycle walked backwards, so building adj[course].append(prereq) instead would return the same true or false. The direction only matters when the order itself must be returned.