Course Schedule Solution

Problem

Given a number of courses (labeled 0 through numCourses-1) and a list of prerequisite pairs, determine whether it's possible to complete all courses. Each pair [a, b] means course b must be finished before course a — the question is whether these dependencies form a cycle that makes completion impossible.

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: true
Explanation: Take course 0 first, then 1 and 2 in either order, then 3.

Counter-example: numCourses = 2, prerequisites = [[0,1],[1,0]] → false, because course 0 requires 1 and course 1 requires 0 — neither can ever start.

Intuition

The problem is equivalent to cycle detection in a directed graph: each pair [a, b] creates an edge b → a encoding "b precedes a." If any cycle exists, the courses involved all wait on each other and can never begin. A cycle-free directed graph (a DAG) always has a valid completion order.

Approach 1 — BFS Topological Sort (Kahn's Algorithm)

Track how many unmet prerequisites each course has. Repeatedly "enroll" in any course whose count drops to zero — if we can enroll in all courses, there was no cycle.

Build an adjacency list and compute each course's in-degree (number of prerequisites).
Seed a queue with every course that has zero prerequisites.
While the queue is non-empty, dequeue a course and increment an enrollment counter.
For each course that depends on the dequeued course, decrement its in-degree.
If a dependent course's in-degree drops to zero, enqueue it.
Return true if the enrollment counter equals numCourses.

1from collections import deque
2
3def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
4    adjacency = [[] for _ in range(numCourses)]
5    in_degree = [0] * numCourses
6
7    for course, prereq in prerequisites:
8        adjacency[prereq].append(course)  # prereq must come before course
9        in_degree[course] += 1
10
11    # start with courses that have no unmet prerequisites
12    queue = deque(c for c in range(numCourses) if in_degree[c] == 0)
13    enrolled = 0
14
15    while queue:
16        course = queue.popleft()
17        enrolled += 1
18        for next_course in adjacency[course]:
19            in_degree[next_course] -= 1
20            if in_degree[next_course] == 0:  # all prereqs now satisfied
21                queue.append(next_course)
22
23    # a cycle permanently keeps some courses at in_degree > 0
24    return enrolled == numCourses

Time: O(V+E) — each course and each prerequisite pair is processed exactly once.
Space: O(V+E) — adjacency list plus the in-degree array and BFS queue.

Approach 2 — DFS with 3-State Coloring

Run DFS from every unvisited course, tagging each node as "currently on the call stack" while exploring it. If DFS reaches a node still on the stack, a back edge exists — meaning a cycle.

Build an adjacency list.
Give each course state 0 (unvisited), 1 (active on current DFS path), or 2 (fully explored).
For each unvisited course, run DFS.
In DFS: state 1 means we've looped back to an ancestor — return true (cycle found).
State 2 means this subtree was already proven safe — return false immediately.
Set state to 1, recurse on all dependents, then set state to 2 before returning.
Return false if no cycle was found across all DFS trees.

1def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
2    adjacency = [[] for _ in range(numCourses)]
3    for course, prereq in prerequisites:
4        adjacency[prereq].append(course)
5
6    # 0 = unvisited, 1 = on current DFS stack, 2 = fully explored (safe)
7    state = [0] * numCourses
8
9    def has_cycle(node: int) -> bool:
10        if state[node] == 1:  # back edge: this node is an ancestor on the current path
11            return True
12        if state[node] == 2:  # already proved no cycle exists past this node
13            return False
14        state[node] = 1
15        for neighbor in adjacency[node]:
16            if has_cycle(neighbor):
17                return True
18        state[node] = 2  # all descendants safe; mark as fully explored
19        return False
20
21    for node in range(numCourses):
22        if state[node] == 0 and has_cycle(node):
23            return False
24    return True

Time: O(V+E) — each node and each edge is visited at most once.
Space: O(V+E) — adjacency list, state array, and recursion stack up to depth V in the worst case.

Complexity Summary

Approach	Time	Space	When to use
BFS Topological Sort	O(V+E)	O(V+E)	When you also need the valid course order or a count of reachable nodes
DFS 3-State Coloring	O(V+E)	O(V+E)	When only a yes/no answer is needed; generalizes naturally to finding the cycle itself

Common Mistakes

Building edges in the wrong direction — prerequisites[i] = [a, b] means b must precede a, so the graph edge goes from b to a. Reversing it (a → b) inverts all dependencies and silently produces wrong answers on almost every input.
Using only 2 DFS states (visited/unvisited) — without a distinct "active" state, a node in a different DFS branch is indistinguishable from a node on the current path. Any cross edge gets misread as a back edge, producing false cycle reports.
Skipping disconnected components in the outer loop — a course with no prerequisites and no dependents is never reached unless you explicitly start DFS or count it. Always iterate over all nodes in the outer loop, not just those that appear in the prerequisites list.
Checking enrolled == prerequisites.length instead of enrolled == numCourses in Kahn's algorithm — a course that appears in no prerequisite pair still needs to be counted. The comparison must be against the total number of courses.
Not accounting for Python's recursion limit in the DFS approach — with up to 2000 courses, a path-shaped graph can push 2000 recursive calls. For production code or very large inputs, convert the DFS to an explicit stack; for LeetCode's constraints it's typically fine.

Course Schedule — Solution