Course Schedule II

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

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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• All the pairs [ai, bi] are distinct.

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement: Given a directed graph G = (V, E) where vertices represent courses (|V| = numCourses) and edges represent prerequisite relationships (edge bᵢ → aᵢ exists for each [aᵢ, bᵢ] in prerequisites), determine if G is a directed acyclic graph (DAG). If G is a DAG, return a topological ordering of its vertices. If G contains cycles (making topological sort impossible), return an empty array. The topological ordering must satisfy: for every directed edge u → v, u appears before v in the ordering.

Beginner-Friendly Restatement: Imagine you’re planning your college courses. Some courses require you to take other courses first (like Calculus before Physics). You’re given a list of all courses and their prerequisites. Your task is to find an order to take all courses without violating any prerequisite rules. If it’s impossible due to circular dependencies (like Course A needs Course B, but Course B also needs Course A), return an empty list.

Mathematical Formulation: Let C = {0, 1, 2, …, n-1} be the set of courses where n = numCourses. Let P = {(aᵢ, bᵢ) | [aᵢ, bᵢ] ∈ prerequisites} be the prerequisite relation. Find a permutation π: C → C such that ∀(a, b) ∈ P, π⁻¹(b) < π⁻¹(a) (b appears before a in the ordering). If no such permutation exists (∃ cycle b₁ → b₂ → … → bₖ → b₁), return ∅.

Constraint Analysis:

• 1 <= numCourses <= 2000: Graph has up to 2000 nodes → O(V²) algorithms (~4M operations) are acceptable but O(V+E) is preferred.
• 0 <= prerequisites.length <= numCourses * (numCourses - 1): Graph can be sparse (few edges) or complete (dense). Worst case ~4M edges → need efficient graph representation.
• prerequisites[i].length == 2: Each prerequisite is a simple directed edge.
• 0 <= ai, bi < numCourses: Node indices are valid and zero-based.
• ai != bi: No self-loops in the graph.
• All pairs [ai, bi] are distinct: No duplicate edges in the input.
• Hidden Edge Cases:
  • Empty prerequisites → any ordering is valid (return [0,1,…,n-1])
  • Single course with no prerequisites → trivial [0]
  • Completely disconnected graph → any ordering works
  • Chain prerequisites (0→1→2→3) → exactly one valid ordering
  • Diamond dependencies (0→1, 0→2, 1→3, 2→3) → multiple valid orderings

---

2. Intuition Scaffolding

Real-World Metaphor: Imagine building a house where certain tasks must precede others (foundation before walls, walls before roof). The courses are construction tasks, prerequisites are dependency rules. A valid schedule ensures no task starts before its dependencies are complete. Circular dependencies would mean the project is impossible (need walls before foundation, but foundation before walls).

Gaming Analogy: Think of a skill tree in an RPG game where advanced skills require basic skills first. You need to find an order to unlock all skills. If skill A requires skill B, and skill B requires skill A, you’re stuck in a deadlock and cannot progress.

Math Analogy: This is equivalent to finding a linear extension of a partial order. The prerequisite relation defines a partial order, and we need a total order that respects all the “less than” relationships. Cycles violate the antisymmetric property required for partial orders.

Common Pitfalls:

1. Assuming connected graph: The graph may have disconnected components.
2. Wrong cycle detection: Only checking local neighborhoods instead of global reachability.
3. Output order confusion: In DFS, the finished order is reversed for topological sort.
4. Performance with adjacency matrix: Using O(V²) space instead of adjacency lists for sparse graphs.
5. Handling multiple valid orders: The problem allows any valid order, but some algorithms naturally produce specific ones.
6. Early termination: Stopping when first cycle is found vs checking all components.

---

3. Approach Encyclopedia

Approach 1: Brute Force (Generate & Validate)

Pseudocode:
1. Generate all n! permutations of courses
2. For each permutation π:
   - For each prerequisite (a, b):
       if position(b) > position(a) in π: invalid
   - If all prerequisites satisfied: return π
3. If no valid permutation found: return []

Complexity Proof:
- Time: O(n! × m) where m = prerequisites.length
  - n! permutations, each checked against m edges
  - For n=10: 10! = 3,628,800 × m → infeasible
- Space: O(n) for storing current permutation

Visualization:
Permutations: [0,1,2], [0,2,1], [1,0,2], ...
Check each against: 1→0, 2→0
✓ [0,1,2]: 0 before 1? ✓, 0 before 2? ✓
✗ [1,0,2]: 0 before 1? ✗ (1 appears before 0)

Approach 2: Kahn’s Algorithm (BFS-based Topological Sort)

Pseudocode:
1. Compute in-degree for each node
2. Initialize queue with all nodes having in-degree 0
3. Initialize result list and processed node count
4. While queue not empty:
   - Dequeue node u, add to result
   - For each neighbor v of u:
       Decrement in-degree of v
       If in-degree becomes 0, enqueue v
5. If |result| = n: return result, else return []

Complexity Proof:
- Time: O(V + E) - each node and edge processed once
- Space: O(V + E) for adjacency list and in-degree array

Visualization:
Graph: 0 → 1 → 3
       0 → 2 → 3

Step 0: in-degree: [0:0, 1:1, 2:1, 3:2]
        Queue: [0], Result: []
Step 1: Process 0 → decrement 1,2
        in-degree: [0:0, 1:0, 2:0, 3:2]
        Queue: [1,2], Result: [0]
Step 2: Process 1 → decrement 3
        in-degree: [3:1], Queue: [2], Result: [0,1]
Step 3: Process 2 → decrement 3
        in-degree: [3:0], Queue: [3], Result: [0,1,2]
Step 4: Process 3 → Result: [0,1,2,3]

Approach 3: DFS-based Topological Sort

Pseudocode:
1. Build adjacency list
2. For each unvisited node:
   - If DFS detects cycle: return []
3. Return reversed finish order

DFS(u, visited, recursion_stack, result):
   - Mark u as visited and add to recursion stack
   - For each neighbor v of u:
       If v in recursion_stack: cycle detected
       If v unvisited: DFS(v)
   - Remove u from recursion stack, add to result

Complexity Proof:
- Time: O(V + E) - each node visited once
- Space: O(V) for recursion stack and visited sets

Visualization:
Graph: 0 → 1 → 3
       0 → 2 → 3

DFS(0): visit 0 → [0]
  DFS(1): visit 1 → [0,1]
    DFS(3): visit 3 → [0,1,3] → finish 3
  finish 1
  DFS(2): visit 2 → [0,1,3,2]
    DFS(3): already visited, skip
  finish 2
finish 0
Result: reverse([3,1,2,0]) = [0,2,1,3]

---

4. Code Deep Dive

Optimal Solution (Kahn’s Algorithm):

from collections import deque
from typing import List

def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    # Build graph and compute in-degrees
    adj = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses
    
    # Line 4-7: Graph construction
    for dest, src in prerequisites:  # [a_i, b_i] means b_i → a_i
        adj[src].append(dest)        # src must come before dest
        in_degree[dest] += 1         # dest has one more prerequisite
    
    # Line 9-12: Initialize queue with source nodes
    queue = deque()
    for i in range(numCourses):
        if in_degree[i] == 0:        # Courses with no prerequisites
            queue.append(i)
    
    # Line 14-23: Process nodes in topological order
    result = []
    while queue:
        current = queue.popleft()
        result.append(current)        # Line 17: Add to result when all prerequisites satisfied
        
        # Line 19-22: Update neighbors' in-degrees
        for neighbor in adj[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:  # All prerequisites completed
                queue.append(neighbor)
    
    # Line 25-26: Check if all courses can be taken
    return result if len(result) == numCourses else []

Edge Case Handling:

• Example 1 (2, [[1,0]]):

  • Line 6: adj[0] = [1], in_degree[1] = 1
  • Line 11: queue starts with [0] (in_degree[0] = 0)
  • Process 0 → result = [0], queue 1’s in_degree becomes 0 → enqueue 1
  • Process 1 → result = [0,1] ✓

• Example 3 (1, []):

  • Empty prerequisites → Line 11: queue = [0]
  • Process 0 → result = [0] ✓

• Cycle Detection (2, [[1,0],[0,1]]):

  • Both nodes have in_degree = 1
  • Line 11: empty queue → Line 25: return [] ✓

---

5. Complexity War Room

Hardware-Aware Analysis:

• With numCourses ≤ 2000, adjacency list uses ~2000 × (avg degree) × 4 bytes.
• Worst-case 4M edges → ~16MB memory, fitting comfortably in L3 cache.
• BFS queue operations are O(1) amortized, making it cache-friendly.

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n!·m)	O(n)	10/10	❌ Fails n>10
Kahn’s (BFS)	O(V+E)	O(V+E)	9/10	✅ Preferred
DFS Recursive	O(V+E)	O(V)	8/10	✅ Acceptable
DFS Iterative	O(V+E)	O(V)	7/10	✅ Robust

Trade-off Analysis:

• Kahn’s Algorithm: Easier to understand, naturally handles disconnected graphs, explicit cycle detection
• DFS: More elegant, better for finding all topological orders, but recursion depth concerns for large n

---

6. Pro Mode Extras

Variants Section:

1. Course Schedule III (LC 630): Courses have durations and deadlines → weighted scheduling
2. Parallel Course Scheduling: Take k courses simultaneously → topological sort with concurrency
3. Course Schedule IV (LC 1462): Answer queries about prerequisite relationships → transitive closure
4. Alien Dictionary (LC 269): Similar topological sort but with character ordering

Interview Cheat Sheet:

• First Mention: “This is a topological sort problem on a directed graph”
• Cycle Detection: “If we cannot reduce all in-degrees to zero, a cycle exists”
• Space-Time: “O(V+E) time and space for adjacency list representation”
• Edge Cases: “Handle empty graph, single node, and disconnected components”
• Optimization: “Kahn’s algorithm naturally detects cycles during BFS traversal”

Advanced Insights:

• The problem is equivalent to checking if the graph is a DAG and finding its topological order
• Multiple valid solutions exist because topological sort is not unique for DAGs with multiple source nodes
• The BFS approach (Kahn’s) produces a specific ordering (level-by-level), while DFS produces a different ordering based on traversal sequence
• For large graphs, iterative DFS avoids recursion limits and is more robust