Course Schedule

Difficulty: Medium
Topics: Depth-First Search, Breadth-First Search, Graph, Topological Sort
Link: https://leetcode.com/problems/course-schedule/

Problem Description

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 course 0 you have to first take course 1.

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 <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All the pairs prerequisites[i] are unique.

Solution

1. Problem Deconstruction

Technical Restatement
Given a directed graph of numCourses nodes labeled 0 to numCourses-1, determine if there exists a topological ordering. Each directed edge (b, a) from prerequisites [a, b] indicates course a depends on b. Return true iff the graph is acyclic.

Beginner’s Description
You want to take all courses but some have prerequisites. If course A needs B, you must take B first. Determine if there’s a way to take all courses without getting stuck in an impossible loop (e.g., A needs B and B needs A).

Mathematical Formulation
Let $G=(V,E)$ where $V=\{0,1,...,n-1\}$ and $E=\{(b_i,a_i)\}$ for each prerequisite $[a_i,b_i]$ . Find if $\exists$ a permutation $P$ of $V$ such that for every $(u,v) \in E$ , $u$ appears before $v$ in $P$ (i.e., $G$ is a DAG).

Constraint Analysis

1 <= numCourses <= 2000
- Solutions must handle up to 2000 nodes → $O(n^2)$ is feasible but $O(n)$ preferred.
0 <= prerequisites.length <= 5000
- Edge count up to 5K → $O(n + m)$ algorithms (e.g., BFS/DFS) are optimal.
Unique prerequisite pairs
- No duplicate edges → no need for duplicate handling in graph construction.
0 <= ai, bi < numCourses
- Implies possible self-edges (e.g., [0,0]) → immediate cycle if present.

Hidden Edge Cases

Empty prerequisites → trivially possible.
Single course with self-prerequisite → impossible.
Disconnected graph with cycles in any component → impossible.

2. Intuition Scaffolding

Real-World Metaphor
Planning a recipe requiring prepped ingredients, where each ingredient might depend on another task. Circular dependencies (e.g., needing eggs to make a cake mix, but needing cake mix to make eggs) make completion impossible.

Gaming Analogy
Unlocking skill trees where each skill requires prior skills. A cycle (e.g., Skill A needs B, B needs A) blocks progression.

Math Analogy
Proving a partial order has no cycles (i.e., is a poset) → topological sort exists iff no cycles.

Common Pitfalls

Ignoring Disconnected Components
- Cycles might exist in isolated subgraphs.
Incorrect Edge Direction
- Reversing (a,b) as (a→b) instead of (b→a).
Early Termination
- Stopping BFS/DFS prematurely before full traversal.
State Tracking in DFS
- Forgetting to mark nodes as fully processed post-traversal.
Overlooking Self-Edges
- Failing to check ai == bi cases.

3. Approach Encyclopedia

Approach 1: Kahn’s Algorithm (BFS Topological Sort)
Pseudocode

def canFinish(numCourses, prerequisites):
    adj = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        adj[b].append(a)
        in_degree[a] += 1
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    count = 0
    while queue:
        u = queue.popleft()
        count += 1
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    return count == numCourses

Complexity Proof

Time: $O(n + m)$ . Each node and edge processed exactly once.
Space: $O(n + m)$ for adjacency list and queue.

Visualization

Nodes: 0 → 1 → 2  
In-degree: [0,1,1] → Queue starts with 0.  
Process 0 → in-degree[1] becomes 0 → enqueue 1.  
Process 1 → in-degree[2] becomes 0 → enqueue 2.  
All nodes processed.

Approach 2: DFS Cycle Detection
Pseudocode

def canFinish(numCourses, prerequisites):
    adj = [[] for _ in range(numCourses)]
    for a, b in prerequisites:
        adj[b].append(a)
    visited = [0] * numCourses  # 0=unvisited, 1=visiting, 2=visited
    def has_cycle(u):
        if visited[u] == 1: return True
        if visited[u] == 2: return False
        visited[u] = 1
        for v in adj[u]:
            if has_cycle(v): return True
        visited[u] = 2
        return False
    for u in range(numCourses):
        if has_cycle(u): return False
    return True

Complexity Proof

Time: $O(n + m)$ . Each node/edge processed once.
Space: $O(n)$ for recursion stack and visited.

Visualization

Start DFS at 0 → mark as visiting.  
Check neighbor 1 → mark as visiting.  
Neighbor 1's neighbor 0 is already visiting → cycle detected.

4. Code Deep Dive

Kahn’s Algorithm Line-by-Line

adj = [[] for _ ...]
- Builds adjacency list: index = source node, list = destinations.
in_degree[a] += 1
- Tracks incoming edges for each node.
queue = deque(...)
- Seeds BFS with in-degree 0 nodes (no prerequisites).
count += 1
- Tracks processed nodes. Final count must equal total courses.

Edge Case Handling

Example 2: Nodes 0 and 1 both have in-degree 1 → queue empty → count remains 0.
Self-Edge: Node 0 with in-degree 1 (from [0,0]) → queue remains empty.

5. Complexity War Room

Hardware-Aware Analysis

For 2000 nodes and 5000 edges:
- Adjacency list uses ~40KB (2000 lists × 20B overhead + 5000 pointers × 8B = ~60KB).
- Easily fits in CPU cache for fast BFS.

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Kahn’s BFS	$O(n + m)$	$O(n + m)$	High	✅ Preferred
DFS Cycle	$O(n + m)$	$O(n)$	Moderate	✅ Alternative
Brute Force	$O(n^2)$	$O(n + m)$	Low	❌ Inefficient

6. Pro Mode Extras

Variants

Course Schedule II (LC 210): Return the topological order.
Parallel Courses (LC 1136): Find minimum semesters to complete all courses.

Interview Cheat Sheet

Key Insight: Problem reduces to cycle detection in directed graphs.
Mention First: “This is a classic topological sort problem with cycle detection.”
Optimization Note: “Kahn’s algorithm is optimal for this constraint range.”

#207 - Course Schedule