189. Course Schedule

🔗 LeetCode Problem: 207. Course Schedule
📊 Difficulty: Medium
🏷️ Topics: Graph, DFS, BFS, Topological Sort, Cycle Detection

Problem Statement

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] = [aᵢ, bᵢ] indicates that you must take course bᵢ first if you want to take course aᵢ.

• 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: 
  Total 2 courses: 0 and 1
  To take course 1, you need to take course 0 first
  Schedule: 0 → 1
  Possible! ✅

Example 2:

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

Explanation:
  To take course 1, need course 0
  To take course 0, need course 1
  Circular dependency! ❌
  Impossible!

Constraints: - 1 <= numCourses <= 2000 - 0 <= prerequisites.length <= 5000 - prerequisites[i].length == 2 - 0 <= aᵢ, bᵢ < numCourses - All the pairs prerequisites[i] are unique.

---

🌳 Visual Understanding - The Complete Picture

The Problem We're Solving 🤔

Courses with prerequisites form a dependency graph: 📚➡️📚

Example:
  numCourses = 4
  prerequisites = [[1,0], [2,0], [3,1], [3,2]]

Meaning:
  [1,0]: To take 1, must take 0 first (0 → 1)
  [2,0]: To take 2, must take 0 first (0 → 2)
  [3,1]: To take 3, must take 1 first (1 → 3)
  [3,2]: To take 3, must take 2 first (2 → 3)

Graph visualization:
       0
      / \
     ↓   ↓
     1   2
      \ /
       ↓
       3

Question: Can we complete all courses? 🤔

Answer: YES! ✅
Schedule: 0 → 1 → 2 → 3
(or 0 → 2 → 1 → 3)

Building Understanding Through Examples 📚

Example 1: Simple chain (possible)

prerequisites = [[1,0]]

Graph:
  0 → 1

Schedule:
  Step 1: Take course 0 ✅
  Step 2: Take course 1 ✅

All courses completed! 🎓
Answer: true

Example 2: Circular dependency (impossible)

prerequisites = [[1,0], [0,1]]

Graph:
  0 ⇄ 1

Dependency cycle:
  Course 0 needs 1
  Course 1 needs 0
  ⟳ Circular! ❌

Can't start anywhere!
Answer: false

Example 3: Complex DAG (possible)

prerequisites = [[1,0], [2,1], [3,2], [1,3]]

Graph:
       0
       ↓
       1 ←─┐
       ↓   │
       2   │
       ↓   │
       3 ──┘

Wait... 1 → 3 → 1? That's a cycle! ❌

Actually:
  [1,0]: 0 → 1
  [2,1]: 1 → 2
  [3,2]: 2 → 3
  [1,3]: 3 → 1 (creates cycle!)

Cycle detected: 1 → 2 → 3 → 1 ⟳
Answer: false

Example 4: No prerequisites (always possible)

numCourses = 3
prerequisites = []

No dependencies at all!
Take in any order: 0, 1, 2 or 2, 1, 0, etc.
Answer: true ✅

The Pattern Emerges 💡

Key observations: 🔍

1️⃣ Directed Graph Problem 🎯
   Courses = nodes
   Prerequisites = directed edges
   [a,b] means b → a (b must come before a)

2️⃣ Cycle Detection! 🔄
   Cycle = impossible schedule
   DAG (no cycle) = possible schedule

3️⃣ Topological Sort Connection 📊
   Valid schedule = topological ordering
   Exists only if graph is DAG!

4️⃣ Two Approaches 🛠️
   DFS: Detect cycles directly
   BFS (Kahn's): Topological sort attempt

5️⃣ Return Boolean 🎲
   Just need true/false
   Don't need actual schedule!

---

🧠 The Journey From Brute Force to Optimal

Part 1: The Obvious Try - "Generate all orderings?" 🤔

💭 First thought: "Try all possible course orderings!"

Brute force:
  Generate all permutations of courses
  For each permutation:
    Check if prerequisites satisfied
    If yes: return true

  If no permutation works: return false

Example:
  numCourses = 3
  prerequisites = [[1,0], [2,1]]

  Permutations to try:
    [0,1,2]: 0→1 ✅, 1→2 ✅ → Valid! ✅
    [0,2,1]: 0→1 ❌ (1 comes after 2)
    [1,0,2]: 1 needs 0, but 1 comes first ❌
    [1,2,0]: Same problem ❌
    [2,0,1]: 2 needs 1, but 1 comes last ❌
    [2,1,0]: 2 needs 1 ✅, 1 needs 0 ❌

  Found valid: [0,1,2] → return true

Problem: EXPONENTIAL! 😱

Time complexity:
  n! permutations
  Each takes O(E) to verify (E = prerequisites)
  Total: O(n! × E) 🐌

For 10 courses: 3,628,800 permutations! ❌
For 20 courses: 2.4 × 10^18 permutations! 💀

Completely infeasible! 🚫

Part 2: The Realization - "It's cycle detection!" 💭

🤔 Key insight: Cycles make completion impossible!

Why cycles are the problem:
  A → B → C → A

  To take A, need C
  To take C, need B  
  To take B, need A
  ⟳ Infinite loop! Can't start!

Reframe the problem:
  "Can finish all courses?"
  ⟺
  "Is the dependency graph acyclic?" (DAG)

  If DAG: ✅ Can finish (topological order exists)
  If has cycle: ❌ Cannot finish

So we need: CYCLE DETECTION! 🔄

This is a GRAPH problem!
  Nodes: Courses
  Edges: Prerequisites
  Question: Is graph a DAG?

Two classic approaches:
  1. DFS with cycle detection
  2. BFS (Kahn's algorithm) - topological sort

Both: O(V + E) time! ⚡
Much better than O(n!)! 🚀

Part 3: The DFS Approach - "Three states for cycle detection!" 💡

🤔 DFS cycle detection using THREE states:

State meanings:
  UNVISITED (0): Haven't explored yet ⚪
  VISITING (1): Currently exploring (on path) 🟡
  VISITED (2): Completely explored ✅

Why three states?
  Two states (visited/unvisited) insufficient!
  Need to track "currently on recursion path"

  VISITING state = "on current DFS path"
  If we reach VISITING node again = CYCLE! 🔄

Example trace:
  Graph: 0 → 1 → 2 → 3

  DFS from 0:
    Mark 0 VISITING 🟡
    Explore neighbor 1:
      Mark 1 VISITING 🟡
      Explore neighbor 2:
        Mark 2 VISITING 🟡
        Explore neighbor 3:
          Mark 3 VISITING 🟡
          No neighbors
          Mark 3 VISITED ✅
        Back to 2
        Mark 2 VISITED ✅
      Back to 1
      Mark 1 VISITED ✅
    Back to 0
    Mark 0 VISITED ✅

  No cycles! Return true! ✅

Example with cycle:
  Graph: 0 → 1 → 2 → 1

  DFS from 0:
    Mark 0 VISITING 🟡
    Explore neighbor 1:
      Mark 1 VISITING 🟡
      Explore neighbor 2:
        Mark 2 VISITING 🟡
        Explore neighbor 1:
          1 is VISITING! 🔴
          CYCLE DETECTED! ⟳
          Return false ❌

Three states are KEY! 🔑

Part 4: The BFS Approach - "Kahn's algorithm!" 💡

🤔 Alternative: BFS-based topological sort (Kahn's algorithm)

Key idea: Process nodes with no dependencies first!

Algorithm:
  1. Calculate in-degree for each node
     (in-degree = number of prerequisites)

  2. Start with nodes that have in-degree 0
     (no prerequisites - can take immediately)

  3. Process these nodes:
     - "Take" the course
     - Decrease in-degree of dependent courses
     - If dependent course now has in-degree 0, add to queue

  4. If processed all courses: DAG! ✅
     If some remain: cycle exists! ❌

Example:
  Graph: 0 → 1 → 2

  In-degrees: [0: 0, 1: 1, 2: 1]

  Step 1: Queue = [0] (in-degree 0)
          Process 0, decrease in-degree of 1
          In-degrees: [0: -, 1: 0, 2: 1]
          Queue = [1]

  Step 2: Process 1, decrease in-degree of 2
          In-degrees: [0: -, 1: -, 2: 0]
          Queue = [2]

  Step 3: Process 2
          Queue = []

  Processed 3 courses = all! ✅
  Return true!

Example with cycle:
  Graph: 0 → 1 → 0 (cycle)

  In-degrees: [0: 1, 1: 1]

  Queue = [] (no in-degree 0!)
  Can't process anything!
  Processed 0 courses ≠ total
  Return false! ❌

Both approaches work! Choose based on preference! 🎯

Part 5: The Pattern - "Topological sort problems!" 🎯

✨ This is a TOPOLOGICAL SORT problem!

Pattern recognition:
  ✅ Dependencies between items
  ✅ Need to order items respecting dependencies
  ✅ Check if valid ordering exists
  ✅ Detect circular dependencies

Related problems with same pattern:
  - Course Schedule (this one)
  - Course Schedule II (return actual order)
  - Alien Dictionary (deduce alphabet order)
  - Sequence Reconstruction (verify unique order)

Two standard approaches:

1. DFS + Cycle Detection:
   - Three-state tracking
   - If cycle: return false
   - If no cycle: return true
   - Time: O(V + E) ⚡

2. BFS (Kahn's Algorithm):
   - In-degree tracking
   - Process zero in-degree nodes
   - Count processed nodes
   - Time: O(V + E) ⚡

Both have same complexity!
DFS: More intuitive for cycle detection
BFS: Naturally gives topological order

For this problem (just true/false):
  Either works perfectly! 🎯

Time: O(V + E) where V = courses, E = prerequisites
Space: O(V + E) for graph representation

Pattern mastered! 🌟

---

🎯 Approach 1: DFS with Cycle Detection

The Key Insight 💡

Use DFS with three-state tracking to detect cycles 🔄. States: UNVISITED (0), VISITING (1), VISITED (2) 🟡✅. Start DFS from each unvisited course 🚀. If reach VISITING node = cycle found! ❌ If all DFS complete without cycle = DAG! ✅ Return true if no cycles, false otherwise 🎯. Time: O(V+E) ⚡, Space: O(V+E) 📦!

Direct cycle detection! ✨

Complete Implementation

class Solution {
    // ═══════════════════════════════════════════════════════
    // THREE STATES FOR CYCLE DETECTION 🔄
    // ═══════════════════════════════════════════════════════
    private static final int UNVISITED = 0;  // Not explored ⚪
    private static final int VISITING = 1;   // On current path 🟡
    private static final int VISITED = 2;    // Fully explored ✅

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // ═══════════════════════════════════════════════════
        // DFS CYCLE DETECTION APPROACH 🔍
        // ═══════════════════════════════════════════════════
        // Build graph and detect cycles using DFS
        // If cycle found: return false ❌
        // If no cycle: return true ✅
        // ═══════════════════════════════════════════════════

        // ═══════════════════════════════════════════════════
        // BUILD ADJACENCY LIST 🏗️
        // ═══════════════════════════════════════════════════
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        // ───────────────────────────────────────────────────
        // Add edges: [a,b] means b → a
        // ───────────────────────────────────────────────────
        for (int[] prereq : prerequisites) {
            int course = prereq[0];
            int prerequisite = prereq[1];
            graph.get(prerequisite).add(course);  // prereq → course
        }

        // ═══════════════════════════════════════════════════
        // STATE TRACKING 📊
        // ═══════════════════════════════════════════════════
        int[] state = new int[numCourses];  // All start UNVISITED (0)

        // ═══════════════════════════════════════════════════
        // DFS FROM EACH UNVISITED COURSE 🚀
        // ═══════════════════════════════════════════════════
        for (int course = 0; course < numCourses; course++) {
            if (state[course] == UNVISITED) {
                if (hasCycle(graph, state, course)) {
                    return false;  // Cycle detected! ❌
                }
            }
        }

        // ═══════════════════════════════════════════════════
        // NO CYCLES FOUND! ✅
        // ═══════════════════════════════════════════════════
        return true;  // Can finish all courses! 🎓
    }

    // ═══════════════════════════════════════════════════════
    // DFS HELPER: DETECT CYCLE 🔍
    // ═══════════════════════════════════════════════════════
    private boolean hasCycle(List<List<Integer>> graph, int[] state, int course) {
        // ───────────────────────────────────────────────────
        // MARK AS VISITING (on current path) 🟡
        // ───────────────────────────────────────────────────
        state[course] = VISITING;

        // ───────────────────────────────────────────────────
        // EXPLORE ALL NEIGHBORS 🧭
        // ───────────────────────────────────────────────────
        for (int neighbor : graph.get(course)) {
            if (state[neighbor] == VISITING) {
                // ───────────────────────────────────────────
                // BACK EDGE! Cycle detected! 🔴
                // ───────────────────────────────────────────
                return true;  // Found cycle! ⟳
            }

            if (state[neighbor] == UNVISITED) {
                // ───────────────────────────────────────────
                // Continue DFS 🔍
                // ───────────────────────────────────────────
                if (hasCycle(graph, state, neighbor)) {
                    return true;  // Cycle in subtree!
                }
            }

            // If VISITED: already fully explored, skip ✅
        }

        // ───────────────────────────────────────────────────
        // MARK AS VISITED (fully explored) ✅
        // ───────────────────────────────────────────────────
        state[course] = VISITED;

        return false;  // No cycle from this course!
    }
}

Why This Works 🎯

Three states enable cycle detection: 🔄 - UNVISITED: Haven't explored yet - VISITING: Currently on DFS path (KEY!) - VISITED: Completely explored

VISITING state detects cycles: 🔑 - If we reach VISITING node = back edge - Back edge = cycle in directed graph! - Return false immediately!

VISITED prevents re-exploration: ⚡ - Already processed, no cycle from here - Skip without recursing - Saves time!

---

🎯 Approach 2: BFS (Kahn's Algorithm)

The Key Insight 💡

Use Kahn's algorithm for topological sort attempt 🌊. Calculate in-degree for each course (count prerequisites) 📊. Start with courses having in-degree 0 (no prerequisites) ✅. Process them: "take" course, decrease neighbors' in-degrees, add newly-zero to queue 🔄. Count processed courses 📏. If count = total, DAG! ✅ Otherwise cycle exists! ❌ Time: O(V+E) ⚡, Space: O(V+E) 📦!

Topological sort approach! ✨

Complete Implementation

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // ═══════════════════════════════════════════════════
        // KAHN'S ALGORITHM (BFS TOPOLOGICAL SORT) 🌊
        // ═══════════════════════════════════════════════════
        // Try to build topological order
        // If successful (all processed): DAG ✅
        // If incomplete: cycle exists ❌
        // ═══════════════════════════════════════════════════

        // ═══════════════════════════════════════════════════
        // BUILD ADJACENCY LIST 🏗️
        // ═══════════════════════════════════════════════════
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        // ═══════════════════════════════════════════════════
        // CALCULATE IN-DEGREES 📊
        // ═══════════════════════════════════════════════════
        int[] inDegree = new int[numCourses];

        for (int[] prereq : prerequisites) {
            int course = prereq[0];
            int prerequisite = prereq[1];

            graph.get(prerequisite).add(course);  // prereq → course
            inDegree[course]++;  // course has one more prerequisite
        }

        // ═══════════════════════════════════════════════════
        // FIND COURSES WITH NO PREREQUISITES 🔍
        // ═══════════════════════════════════════════════════
        Queue<Integer> queue = new LinkedList<>();

        for (int course = 0; course < numCourses; course++) {
            if (inDegree[course] == 0) {
                queue.offer(course);  // Can take immediately! ✅
            }
        }

        // ═══════════════════════════════════════════════════
        // BFS: PROCESS COURSES 🌊
        // ═══════════════════════════════════════════════════
        int processedCount = 0;

        while (!queue.isEmpty()) {
            int course = queue.poll();
            processedCount++;  // "Take" this course ✅

            // ───────────────────────────────────────────────
            // DECREASE IN-DEGREE OF DEPENDENT COURSES 📉
            // ───────────────────────────────────────────────
            for (int dependent : graph.get(course)) {
                inDegree[dependent]--;

                // ───────────────────────────────────────────
                // IF NOW READY, ADD TO QUEUE 🎯
                // ───────────────────────────────────────────
                if (inDegree[dependent] == 0) {
                    queue.offer(dependent);
                }
            }
        }

        // ═══════════════════════════════════════════════════
        // CHECK IF ALL COURSES PROCESSED ✅
        // ═══════════════════════════════════════════════════
        // If processed all: no cycle (DAG) ✅
        // If some remain: cycle exists ❌
        // ═══════════════════════════════════════════════════
        return processedCount == numCourses;
    }
}

Why This Works 🎯

In-degree tracks prerequisites: 📊 - in-degree[i] = number of courses needed before i - When in-degree = 0, course is ready!

BFS processes in topological order: 🌊 - Start with zero in-degree (no dependencies) - Process course, "remove" edges - Newly-zero courses become ready - Natural topological ordering!

Count reveals cycles: 🔍 - If DAG: can process all courses - If cycle: some courses never reach zero in-degree - processedCount < total = cycle! ❌

---

🔍 Detailed Dry Run

Let's trace Approach 1 (DFS) on a complex example:

numCourses = 4
prerequisites = [[1,0], [2,0], [3,1], [3,2]]

╔══════════════════════════════════════════════════════════════╗
║                            SETUP                             ║
╚══════════════════════════════════════════════════════════════╝

Build graph from prerequisites:
  [1,0]: 0 → 1
  [2,0]: 0 → 2
  [3,1]: 1 → 3
  [3,2]: 2 → 3

Adjacency list:
  0: [1, 2]
  1: [3]
  2: [3]
  3: []

Graph visualization:
       0
      / \
     ↓   ↓
     1   2
      \ /
       ↓
       3

State array: [0, 0, 0, 0] (all UNVISITED)

DFS Exploration 🔍

╔═════════════════════════════════════════════════╗
║ 🔍 DFS FROM COURSE 0                           ║
╠═════════════════════════════════════════════════╣
║ state[0] = UNVISITED → Start DFS               ║
║                                                 ║
║ ───────────────────────────────────────────────║
║ hasCycle(graph, state, 0):                     ║
║ ───────────────────────────────────────────────║
║                                                 ║
║ Mark 0 as VISITING 🟡                          ║
║ state = [1, 0, 0, 0]                           ║
║                                                 ║
║ Explore neighbors of 0: [1, 2]                 ║
║                                                 ║
║   ╔═══════════════════════════════════════════╗║
║   ║ Neighbor 1:                               ║║
║   ║ state[1] = UNVISITED → Recurse           ║║
║   ║                                           ║║
║   ║ hasCycle(graph, state, 1):                ║║
║   ║                                           ║║
║   ║ Mark 1 as VISITING 🟡                    ║║
║   ║ state = [1, 1, 0, 0]                     ║║
║   ║                                           ║║
║   ║ Explore neighbors of 1: [3]              ║║
║   ║                                           ║║
║   ║   ╔═══════════════════════════════════╗  ║║
║   ║   ║ Neighbor 3:                       ║  ║║
║   ║   ║ state[3] = UNVISITED → Recurse   ║  ║║
║   ║   ║                                   ║  ║║
║   ║   ║ hasCycle(graph, state, 3):        ║  ║║
║   ║   ║                                   ║  ║║
║   ║   ║ Mark 3 as VISITING 🟡            ║  ║║
║   ║   ║ state = [1, 1, 0, 1]             ║  ║║
║   ║   ║                                   ║  ║║
║   ║   ║ Neighbors of 3: [] (empty)       ║  ║║
║   ║   ║ No neighbors to explore          ║  ║║
║   ║   ║                                   ║  ║║
║   ║   ║ Mark 3 as VISITED ✅             ║  ║║
║   ║   ║ state = [1, 1, 0, 2]             ║  ║║
║   ║   ║                                   ║  ║║
║   ║   ║ Return false (no cycle)          ║  ║║
║   ║   ╚═══════════════════════════════════╝  ║║
║   ║                                           ║║
║   ║ Back to course 1                          ║║
║   ║ No cycle found from 3 ✅                  ║║
║   ║                                           ║║
║   ║ Mark 1 as VISITED ✅                     ║║
║   ║ state = [1, 2, 0, 2]                     ║║
║   ║                                           ║║
║   ║ Return false (no cycle)                   ║║
║   ╚═══════════════════════════════════════════╝║
║                                                 ║
║ Back to course 0                                ║
║ No cycle from neighbor 1 ✅                    ║
║                                                 ║
║   ╔═══════════════════════════════════════════╗║
║   ║ Neighbor 2:                               ║║
║   ║ state[2] = UNVISITED → Recurse           ║║
║   ║                                           ║║
║   ║ hasCycle(graph, state, 2):                ║║
║   ║                                           ║║
║   ║ Mark 2 as VISITING 🟡                    ║║
║   ║ state = [1, 2, 1, 2]                     ║║
║   ║                                           ║║
║   ║ Explore neighbors of 2: [3]              ║║
║   ║                                           ║║
║   ║   Neighbor 3:                             ║║
║   ║   state[3] = VISITED ✅                  ║║
║   ║   Already fully explored, skip!          ║║
║   ║                                           ║║
║   ║ Mark 2 as VISITED ✅                     ║║
║   ║ state = [1, 2, 2, 2]                     ║║
║   ║                                           ║║
║   ║ Return false (no cycle)                   ║║
║   ╚═══════════════════════════════════════════╝║
║                                                 ║
║ Back to course 0                                ║
║ No cycle from neighbor 2 ✅                    ║
║                                                 ║
║ All neighbors explored, no cycles!              ║
║                                                 ║
║ Mark 0 as VISITED ✅                           ║
║ state = [2, 2, 2, 2]                           ║
║                                                 ║
║ Return false (no cycle from course 0)           ║
╚═════════════════════════════════════════════════╝

╔═════════════════════════════════════════════════╗
║ 🔍 CHECK REMAINING COURSES                     ║
╠═════════════════════════════════════════════════╣
║ Course 1: state[1] = VISITED ✅ Skip           ║
║ Course 2: state[2] = VISITED ✅ Skip           ║
║ Course 3: state[3] = VISITED ✅ Skip           ║
║                                                 ║
║ All courses checked!                            ║
║ No cycles found anywhere! ✅                    ║
╚═════════════════════════════════════════════════╝

FINAL RESULT 🎉

╔═══════════════════════════════════════════════╗
║         🎉 FINAL RESULT: true                 ║
╠═══════════════════════════════════════════════╣
║                                               ║
║  Graph is a DAG (no cycles)! ✅               ║
║  Can finish all courses! 🎓                   ║
║                                               ║
║  Valid schedule exists:                       ║
║    0 → 1 → 2 → 3                             ║
║    or 0 → 2 → 1 → 3                          ║
║                                               ║
║  State progression:                           ║
║    Start: [0, 0, 0, 0] (all UNVISITED)       ║
║    End:   [2, 2, 2, 2] (all VISITED)         ║
║                                               ║
║  No VISITING state encountered twice! 🔑      ║
║  No cycles detected! ⟳❌                      ║
║                                               ║
╚═══════════════════════════════════════════════╝

🔑 Key Observations:

1. Three-state tracking worked perfectly: 🟡✅ VISITING → VISITED progression

2. DFS explored all paths: 🔍 Complete graph traversal

3. VISITED optimization: ⚡ Course 3 skipped second time (already explored)

4. No back edges detected: 🎯 Never reached VISITING node from VISITING path

5. Result: DAG confirmed: ✅ Can complete all courses!

---

📊 Complexity Analysis

Time Complexity: O(V + E) ⚡

Where:
  V = numCourses (vertices)
  E = prerequisites.length (edges)

Both approaches (DFS and BFS):

Build graph: O(E)
  - Process each prerequisite once
  - Add to adjacency list

Approach 1 (DFS):
  - Visit each course once: O(V)
  - Explore each edge once: O(E)
  - Total: O(V + E) ✅

Approach 2 (BFS):
  - Calculate in-degrees: O(E)
  - BFS processes each course once: O(V)
  - Process each edge once: O(E)
  - Total: O(V + E) ✅

Overall: O(V + E) for both! ⚡

Example: 2000 courses, 5000 prerequisites
  Time: 2000 + 5000 = 7000 operations
  Very efficient! 🚀

Space Complexity: O(V + E) 📦

Space usage:

1. Graph (adjacency list): O(V + E) 🏗️
   - V lists (one per course)
   - Total E entries across all lists

2. Approach 1 (DFS):
   - State array: O(V)
   - Recursion stack: O(V) worst case
   - Total: O(V + E) ✅

3. Approach 2 (BFS):
   - In-degree array: O(V)
   - Queue: O(V) worst case
   - Total: O(V + E) ✅

Both approaches: O(V + E) 📦

Example: 2000 courses, 5000 prerequisites
  Graph: ~7000 space
  Additional: 2000 space
  Total: ~9000 space units
  Reasonable! ✅

---

🔗 Related Problems & Patterns

Core Pattern: Topological Sort & Cycle Detection 🔄

// Template for topological sort problems
class Solution {
    // DFS approach with cycle detection
    public boolean topologicalSortDFS(int n, int[][] edges) {
        List<List<Integer>> graph = buildGraph(n, edges);
        int[] state = new int[n];  // Three states

        for (int i = 0; i < n; i++) {
            if (state[i] == UNVISITED) {
                if (hasCycle(graph, state, i)) {
                    return false;  // Cycle found
                }
            }
        }
        return true;  // DAG
    }

    // BFS approach (Kahn's algorithm)
    public boolean topologicalSortBFS(int n, int[][] edges) {
        List<List<Integer>> graph = buildGraph(n, edges);
        int[] inDegree = new int[n];

        // Calculate in-degrees
        for (int[] edge : edges) {
            inDegree[edge[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            count++;

            for (int neighbor : graph.get(node)) {
                if (--inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        return count == n;
    }
}

When to Use This Pattern 🎯

✅ Dependencies between items
✅ Check if ordering is possible
✅ Detect circular dependencies
✅ Topological ordering needed
✅ Prerequisite relationships

Recognition triggers: 🔍 - "Prerequisites" or "dependencies" 📚 - "Order" or "sequence" 📊 - "Can finish all" or "is possible" ✅ - "Circular dependency" detection 🔄 - Directed graph with constraints 🎯

Key insight: Topological sort exists ⟺ DAG (no cycles)! 💡

Related LeetCode Problems 📚

Direct Applications:

1. Course Schedule II (LC 210) - Medium 📚 • What's similar: Same prerequisites, cycle detection 🔄 • What's different: Return actual order, not just boolean 📊 • Key insight: Add ordering during DFS/BFS! ✨

2. Alien Dictionary (LC 269) - Hard 👽 • What's similar: Build graph, topological sort 🌊 • What's different: Deduce graph from word order 🔍 • Key insight: Compare adjacent words for edges! 💡

3. Sequence Reconstruction (LC 444) - Medium 🔢 • What's similar: Topological sort, unique ordering 🎯 • What's different: Verify if sequences give unique order ✅ • Key insight: Check uniqueness during Kahn's! 🔑

4. Minimum Height Trees (LC 310) - Medium 🌳 • What's similar: Graph, remove leaves (like in-degree 0) 🌊 • What's different: Undirected graph, find centers 🎯 • Key insight: Topological sort variation! ⚡

Pattern Evolution: 📈

Level 1: Basic Cycle Detection 🔄
  ├─ Course Schedule (LC 207) ← HERE 🎯
  └─ Detect cycle in directed graph

Level 2: Topological Sort Output 📊
  ├─ Course Schedule II (LC 210)
  ├─ Alien Dictionary (LC 269)
  └─ Sequence Reconstruction (LC 444)

Level 3: Advanced Variations 🌟
  ├─ Parallel Courses (LC 1136, 1494)
  ├─ Sort Items by Groups (LC 1203)
  └─ Find All Recipes (LC 2115)

---

📝 Quick Revision Notes

🎯 Core Concept

Course Schedule detects if courses can be completed using cycle detection 🔄. Prerequisites form directed graph (course dependencies) 📚➡️📚. Cycle = impossible (circular dependency) ❌. DAG = possible (valid schedule exists) ✅. Two approaches: DFS with three states (UNVISITED, VISITING, VISITED) or BFS (Kahn's) with in-degree tracking 🌊. Both O(V+E) time ⚡. Return true if DAG, false if cycle! This is topological sort pattern! 🎯

⚡ Quick Implementation (DFS)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
  public boolean canFinish(int numCourses, int[][] prerequisites) {
    // // Approach 1 - BFS (kahn)
    // return bfs(numCourses, prerequisites);

    // Approach 2 - DFS (plus stack)
    return dfs(numCourses, prerequisites);
  }

  private boolean dfs(int numCourses, int[][] prerequisites) {
    // Step 1: create graph (list of list) - no indegrees
    ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    for (int i = 0; i < numCourses; i++) {
      graph.add(new ArrayList<>());
    }

    for (int i = 0; i < prerequisites.length; i++) {
      graph.get(prerequisites[i][0]).add(prerequisites[i][1]);
    }

    // State 2: Create and track status of nodes (0, 1, 2) with 0 being default.
    // 0 - UNVISITED, 1 - VISITING and 2 - VISITED
    int[] state = new int[numCourses];

    // State 3: Loop every course and detch to find cycle.
    // If loop found, return false. Else, return true.
    for (int i = 0; i < numCourses; i++) {
      if (state[i] == 0) {
        if (dfsUtil(i, state, graph)) { // has cycle?
          return false;
        }
      }
    }

    return true;
  }

  private boolean dfsUtil(int course, int[] state, ArrayList<ArrayList<Integer>> graph) {
    // Step 4: change the state of course being visited or considered.
    state[course] = 1;

    for (int depCourse : graph.get(course)) {
      // Step 5: check the state of dependent course.
      // If cycle is there, it gets detected here.
      if (state[depCourse] == 1) {
        return true;
      }

      // Prevents infinite loop (acts as visited)
      if (state[depCourse] == 0) {
        // Else, do a DFS from here.
        if (dfsUtil(depCourse, state, graph)) {
          return true;
        }
      }
    }

    // Step 6: Mark the node as visited
    state[course] = 2;

    return false;
  }

  private boolean bfs(int numCourses, int[][] prerequisites) {
    // Step 1: create graph (list of list) and indegrees (array).
    ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    int[] indegrees = new int[numCourses];

    for (int i = 0; i < numCourses; i++) {
      graph.add(new ArrayList<>());
    }

    for (int i = 0; i < prerequisites.length; i++) {
      graph.get(prerequisites[i][0]).add(prerequisites[i][1]);
      indegrees[prerequisites[i][1]]++;
    }

    // Step 2: find courses with no dependencies (indegrees with 0 value)
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
      if (indegrees[i] == 0) {
        queue.offer(i);
      }
    }

    // Step 3: explore queue
    int coursesTaken = 0;
    while (!queue.isEmpty()) {
      int course = queue.poll();
      coursesTaken++; // course taken

      for (int depCourse : graph.get(course)) {
        indegrees[depCourse]--;

        if (indegrees[depCourse] == 0) { // no dependancy anymore
          queue.offer(depCourse);
        }
      }
    }

    return coursesTaken == numCourses;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.canFinish(2, new int[][] { { 1, 0 } })); // true
    System.out.println(s.canFinish(2, new int[][] { { 1, 0 }, { 0, 1 } })); // false
  }
}

🔑 Key Insights

Three States are Essential: 🔑

Why three states for DFS cycle detection?

UNVISITED (0): Haven't explored ⚪
VISITING (1): Currently on DFS path 🟡
VISITED (2): Completely explored ✅

Example showing why two states fail:
  Graph: 0 → 1 → 2, 0 → 2

With only two states (visited/unvisited):
  DFS from 0:
    Visit 0 (mark visited)
    Go to 1:
      Visit 1 (mark visited)
      Go to 2:
        Visit 2 (mark visited) ✅
    Back to 0, try other neighbor 2:
      2 is visited! 
      Think it's a cycle? ❌ WRONG!

The problem: Can't distinguish:
  - Back edge (cycle): VISITING → VISITING
  - Cross edge (no cycle): VISITING → VISITED

With three states:
  When at 0, going to 2:
    2 is VISITED (not VISITING)
    Not a cycle! ✅

VISITING = "on current path" 🔑
Only VISITING → VISITING is a cycle! 🔄

Edge Direction Matters: ➡️

CRITICAL: [a, b] means b → a!

Example: [1, 0]
  Means: "To take 1, need 0 first"
  Edge: 0 → 1 (not 1 → 0!)

When building graph:
  prerequisites[i] = [course, prerequisite]
  graph.get(prerequisite).add(course) ✅

NOT: graph.get(course).add(prerequisite) ❌

Getting direction wrong = wrong answer! 🚫

DFS vs BFS Trade-offs: ⚖️

DFS Approach (Three States):
  ✅ More intuitive for cycle detection
  ✅ Natural recursion
  ✅ Easier to understand "back edge"
  ❌ Recursion stack space (deep graphs)

BFS Approach (Kahn's Algorithm):
  ✅ Iterative (no stack overflow risk)
  ✅ Naturally gives topological order
  ✅ Clear in-degree logic
  ❌ Slightly more code

Both: O(V + E) time, O(V + E) space

For Course Schedule (just true/false):
  Either works perfectly! 🎯

For Course Schedule II (need order):
  BFS slightly easier (order is processing order)
  DFS needs post-order collection

Topological Sort Existence: 📊

KEY THEOREM:
  Topological sort exists ⟺ Graph is DAG

Why cycles prevent topological sort:
  A → B → C → A (cycle)

  In topological order:
    A must come before B (A → B)
    B must come before C (B → C)
    C must come before A (C → A)

  Contradiction! Can't satisfy all! ❌

This problem leverages this theorem:
  Can finish courses ⟺ DAG ⟺ No cycles

Just check for cycles! 🎯

🎪 Memory Aid

"Three states track the path we roam" 🟡✅⚪
"VISITING marks the journey home" 🔄
"If VISITING found again, there's a cycle shown" 🔴
"No cycles? DAG! Courses can be known" 🎓 ✨

⚠️ Don't Forget

• Three states in DFS - UNVISITED, VISITING, VISITED! 🟡✅
• Edge direction - [a,b] means b→a (prerequisite first)! ➡️
• VISITING → VISITING - that's the cycle! 🔴
• Count in BFS - if count < total, cycle exists! 📊
• Both O(V+E) - same complexity for DFS and BFS! ⚡
• Topological sort - exists only for DAGs! 🎯

---

You've mastered Course Schedule - topological sort and cycle detection pattern! 🌟📚✨