190. Course Schedule II

🔗 LeetCode Problem: 210. Course Schedule II
📊 Difficulty: Medium
🏷️ Topics: Graph, DFS, BFS, Topological Sort

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 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: 
  Total 2 courses. To take course 1, need course 0 first.
  Valid order: [0, 1] ✅

Example 2:

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

Explanation:
  Multiple valid orders exist:
  - [0,1,2,3]
  - [0,2,1,3] ✅ (one valid answer)

  Both are correct!

Example 3:

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

Explanation:
  Only one course, no prerequisites.
  Just take it! ✅

Constraints: - 1 <= numCourses <= 2000 - 0 <= prerequisites.length <= numCourses * (numCourses - 1) - prerequisites[i].length == 2 - 0 <= aᵢ, bᵢ < numCourses - aᵢ != bᵢ - All the pairs [aᵢ, bᵢ] are distinct.

🌳 Visual Understanding - The Complete Picture

The Problem We're Solving 🤔

Same as Course Schedule, but now RETURN THE ORDER! 📋

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

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

Course Schedule asked: "Can we finish?" ✅/❌
Course Schedule II asks: "WHAT ORDER?" 📊

Valid ordering: [0, 1, 2, 3] or [0, 2, 1, 3]
Both respect all prerequisites! ✅

Building Understanding Through Examples 📚

Example 1: Simple chain

prerequisites = [[1,0]]

Graph:
  0 → 1

Order: [0, 1] ✅
  Step 1: Take 0 (no prerequisites)
  Step 2: Take 1 (prerequisite 0 completed)

Simple and clear! 🎯

Example 2: Diamond graph

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

Graph:
       0
      / \
     1   2
      \ /
       3

Multiple valid orders:
  [0, 1, 2, 3] ✅ Take 1 before 2
  [0, 2, 1, 3] ✅ Take 2 before 1

Both valid because:
  - 0 has no prerequisites (take first)
  - 1 and 2 both need 0 (can do in any order)
  - 3 needs both 1 and 2 (take last)

Return ANY valid order! 📊

Example 3: Impossible (cycle)

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

Graph:
  0 ⇄ 1 (cycle!)

No valid order exists! ❌
Return: [] (empty array)

Same as Course Schedule returning false!

Visual: Topological Order

Graph:
       0
      / \
     1   2
      \ /
       3

Level-by-level view:
  Level 0: {0} - no dependencies
  Level 1: {1, 2} - depend on level 0
  Level 2: {3} - depends on level 1

One valid order: Process level by level!
  [0, 1, 2, 3] or [0, 2, 1, 3] ✅

This is TOPOLOGICAL ORDERING! 🎯

The Pattern Emerges 💡

Key observations: 🔍

1️⃣ Extension of Course Schedule 📚
   Same cycle detection
   PLUS: collect the ordering!

2️⃣ Topological Sort Output 📊
   Course Schedule: boolean
   Course Schedule II: actual order

3️⃣ Two Approaches Still Work 🛠️
   DFS: Post-order collection
   BFS (Kahn's): Processing order IS the answer!

4️⃣ Return Empty on Cycle 🔄
   If cycle detected: return []
   If DAG: return valid order

5️⃣ Multiple Valid Answers ✨
   Any topological order works!
   Just return ONE valid order

🧠 The Journey From Brute Force to Optimal

Part 1: The Connection - "Building on Course Schedule!" 🤔

💭 We already solved the hard part!

Course Schedule (Problem 189):
  ✅ Build graph
  ✅ Detect cycles
  ✅ Return true/false

Course Schedule II:
  ✅ Build graph (same!)
  ✅ Detect cycles (same!)
  🆕 COLLECT the ordering!
  🆕 Return order or []

The NEW part: Collecting the order! 📋

Two approaches from before:
  1. DFS with three states
  2. BFS (Kahn's algorithm)

Both need modification to collect order! 🔧

Part 2: The DFS Approach - "Post-order is topological!" 💭

🤔 DFS insight: Post-order traversal gives topological order!

Why post-order?
  When we finish exploring a node:
    - All its dependencies explored
    - All courses it depends on done
    - Safe to add to order!

Example:
  Graph: 0 → 1 → 2

  DFS from 0:
    Explore 0 → 1 → 2
    Finish 2 first (no dependencies)
    Finish 1 next (2 done)
    Finish 0 last (1 done)

  Post-order: [2, 1, 0]
  Reverse: [0, 1, 2] ✅ Valid topological order!

Key modification:
  When marking node VISITED:
    Add to result list!

  After DFS completes:
    Reverse the list!

  This gives topological order! 🎯

Algorithm:
  List<Integer> order = new ArrayList<>();

  void dfs(node):
    mark VISITING
    for each neighbor:
      if VISITING: return false (cycle)
      if UNVISITED: dfs(neighbor)
    mark VISITED
    order.add(node)  // Add in post-order! 🔑
    return true

  Collections.reverse(order)  // Reverse for correct order!
  return order

Simple extension of Course Schedule! ✨

Part 3: The BFS Approach - "Processing order IS the answer!" 💡

🤔 BFS (Kahn's) insight: Even simpler!

The order we PROCESS courses = valid topological order! 🎯

Why?
  Kahn's algorithm processes in topological order:
    1. Start with zero in-degree (no dependencies)
    2. Process them
    3. Remove edges, find new zero in-degree
    4. Repeat

  The processing order respects all dependencies! ✅

Example:
  Graph: 0 → 1 → 2

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

  Step 1: Process 0 (in-degree 0)
          order = [0]
          Update in-degrees: [1: 0, 2: 1]

  Step 2: Process 1 (in-degree 0)
          order = [0, 1]
          Update in-degrees: [2: 0]

  Step 3: Process 2 (in-degree 0)
          order = [0, 1, 2] ✅

  This IS the topological order! No reversal needed!

Key modification:
  int[] order = new int[numCourses];
  int index = 0;

  while (queue not empty):
    course = queue.poll()
    order[index++] = course  // Add to result! 🔑

    // Update in-degrees as before...

  if (index == numCourses):
    return order  // All processed! ✅
  else:
    return new int[0]  // Cycle! ❌

Even simpler than DFS! No reversal needed! 🌟

Part 4: The Comparison - "Which to use?" 💡

🤔 DFS vs BFS for Course Schedule II:

DFS Approach:
  ✅ Natural cycle detection
  ✅ Familiar recursion
  ❌ Need to reverse list
  ❌ Post-order concept might confuse

  Result collection:
    Add in post-order → reverse

BFS Approach (Kahn's):
  ✅ Processing order IS answer (no reverse!)
  ✅ Clearer logic
  ✅ Iterative (no stack overflow)
  ✅ More intuitive

  Result collection:
    Add while processing → done!

For Course Schedule II:
  BFS is CLEANER! 🎯

  Processing order naturally gives topological sort!
  No reversal, no post-order confusion!

Recommendation: Use BFS (Kahn's)! ⭐

Both work and both O(V + E), but BFS is cleaner
for problems that need the actual ordering! 📊

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

✨ This solidifies the topological sort pattern!

Course Schedule (189):
  Input: Graph (prerequisites)
  Output: Boolean (possible?)
  Method: Cycle detection

Course Schedule II (190): ← YOU ARE HERE
  Input: Graph (prerequisites)
  Output: Ordering (what order?)
  Method: Topological sort with output

Pattern evolution:
  Level 1: Detect if ordering exists
  Level 2: Return the actual ordering

Many problems follow this pattern:
  - Alien Dictionary: Return alphabet order
  - Sequence Reconstruction: Verify unique order
  - Parallel Courses: Track levels/time

Template for "return ordering" problems:

BFS Template:
  Calculate in-degrees
  Queue up zero in-degree nodes

  List<Integer> result = new ArrayList<>();
  while (queue not empty):
    node = queue.poll()
    result.add(node)  // Collect order! 🔑

    Update neighbors' in-degrees
    Add newly-zero to queue

  return result.size() == n ? result : empty

DFS Template:
  List<Integer> result = new ArrayList<>();

  For each unvisited:
    if (hasCycle): return empty

  // In DFS:
  When finishing node:
    result.add(node)

  Collections.reverse(result)
  return result

Pattern mastered! 🌟

🎯 Approach 1: BFS (Kahn's Algorithm) - Recommended ⭐

The Key Insight 💡

Use Kahn's algorithm where processing order IS topological order! 🌊 Calculate in-degrees, queue zero in-degree courses 📊. Process courses: add to result, decrease neighbors' in-degrees, queue newly-zero ✅. If processed all courses, return order 📋. Otherwise return empty array (cycle) 🔄. No reversal needed - processing order is answer! Time: O(V+E) ⚡, Space: O(V+E) 📦!

Cleanest approach! ✨

Complete Implementation

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // ═══════════════════════════════════════════════════
        // KAHN'S ALGORITHM - CLEANEST FOR THIS PROBLEM! ⭐
        // ═══════════════════════════════════════════════════
        // Processing order IS topological order
        // No reversal needed!
        // ═══════════════════════════════════════════════════

        // ═══════════════════════════════════════════════════
        // 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]++;  // One more prerequisite
        }

        // ═══════════════════════════════════════════════════
        // QUEUE 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! ✅
            }
        }

        // ═══════════════════════════════════════════════════
        // RESULT ARRAY 📋
        // ═══════════════════════════════════════════════════
        int[] order = new int[numCourses];
        int index = 0;

        // ═══════════════════════════════════════════════════
        // BFS: PROCESS COURSES IN TOPOLOGICAL ORDER 🌊
        // ═══════════════════════════════════════════════════
        while (!queue.isEmpty()) {
            int course = queue.poll();

            // ───────────────────────────────────────────────
            // ADD TO RESULT 📝
            // ───────────────────────────────────────────────
            // This course can be taken now!
            // Add to ordering!
            // ───────────────────────────────────────────────
            order[index++] = 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: return order ✅
        // If some remain: cycle exists, return empty ❌
        // ═══════════════════════════════════════════════════
        if (index == numCourses) {
            return order;  // Success! 🎓
        } else {
            return new int[0];  // Cycle detected! 🔄
        }
    }
}

Why This Works 🎯

Processing order = topological order: 🌊 - Kahn's processes in dependency order - Zero in-degree → no unmet dependencies - Safe to "take" course now! - Order respects all prerequisites ✅

No reversal needed: ⚡ - Unlike DFS which gives post-order - BFS gives correct order directly! - Cleaner and more intuitive!

Cycle detection built-in: 🔄 - If cycle: some courses never reach zero in-degree - index < numCourses at end - Return empty array!

🎯 Approach 2: DFS with Post-order Collection

The Key Insight 💡

Use DFS with post-order collection 🔍. Add course to result when marking VISITED (all dependencies done) ✅. After all DFS, reverse the result 🔄. Reversed post-order = topological order! 📊 If cycle detected, return empty array ❌. Time: O(V+E) ⚡, Space: O(V+E) 📦!

Classic approach! ✨

Complete Implementation

class Solution {
    // ═══════════════════════════════════════════════════════
    // THREE STATES FOR CYCLE DETECTION 🔄
    // ═══════════════════════════════════════════════════════
    private static final int UNVISITED = 0;
    private static final int VISITING = 1;
    private static final int VISITED = 2;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // ═══════════════════════════════════════════════════
        // DFS POST-ORDER COLLECTION APPROACH 🔍
        // ═══════════════════════════════════════════════════

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

        for (int[] prereq : prerequisites) {
            int course = prereq[0];
            int prerequisite = prereq[1];
            graph.get(prerequisite).add(course);
        }

        // ═══════════════════════════════════════════════════
        // STATE TRACKING & RESULT LIST 📊
        // ═══════════════════════════════════════════════════
        int[] state = new int[numCourses];
        List<Integer> order = new ArrayList<>();

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

        // ═══════════════════════════════════════════════════
        // REVERSE POST-ORDER TO GET TOPOLOGICAL ORDER 🔄
        // ═══════════════════════════════════════════════════
        Collections.reverse(order);

        // ═══════════════════════════════════════════════════
        // CONVERT TO ARRAY 📋
        // ═══════════════════════════════════════════════════
        int[] result = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            result[i] = order.get(i);
        }

        return result;
    }

    // ═══════════════════════════════════════════════════════
    // DFS HELPER WITH POST-ORDER COLLECTION 🔍
    // ═══════════════════════════════════════════════════════
    private boolean hasCycle(List<List<Integer>> graph, int[] state, 
                             int course, List<Integer> order) {
        // ───────────────────────────────────────────────────
        // MARK AS VISITING 🟡
        // ───────────────────────────────────────────────────
        state[course] = VISITING;

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

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

        // ───────────────────────────────────────────────────
        // MARK AS VISITED & ADD TO POST-ORDER 📝
        // ───────────────────────────────────────────────────
        // All dependencies of this course are done!
        // Safe to add to ordering!
        // ───────────────────────────────────────────────────
        state[course] = VISITED;
        order.add(course);  // Post-order collection! 🔑

        return false;  // No cycle!
    }
}

Why This Works 🎯

Post-order gives reverse topological order: 📊 - When course finishes: all dependencies done - Add to list at this point - Results in reverse order!

Reversal gives correct order: 🔄 - Last finished = no dependencies → should be first! - First finished = most dependencies → should be last! - Reverse to get correct topological order!

Cycle detection same as before: ✅ - Three states work identically - VISITING → VISITING = cycle - Return empty if cycle detected!

🔍 Detailed Dry Run

Let's trace Approach 1 (BFS) on Example 2:

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

Calculate in-degrees:
  Course 0: 0 prerequisites → in-degree = 0
  Course 1: 1 prerequisite (0) → in-degree = 1
  Course 2: 1 prerequisite (0) → in-degree = 1
  Course 3: 2 prerequisites (1,2) → in-degree = 2

In-degree array: [0, 1, 1, 2]

BFS Processing 🌊

╔═════════════════════════════════════════════════╗
║ 🔍 INITIALIZATION                               ║
╠═════════════════════════════════════════════════╣
║ Find courses with in-degree 0:                 ║
║   Course 0: in-degree 0 ✅ Add to queue        ║
║   Course 1: in-degree 1 ❌                     ║
║   Course 2: in-degree 1 ❌                     ║
║   Course 3: in-degree 2 ❌                     ║
║                                                 ║
║ queue = [0]                                     ║
║ order = []                                      ║
║ index = 0                                       ║
╚═════════════════════════════════════════════════╝

╔═════════════════════════════════════════════════╗
║ 🌊 ITERATION 1: Process course 0               ║
╠═════════════════════════════════════════════════╣
║ Poll: course 0                                  ║
║                                                 ║
║ ───────────────────────────────────────────────║
║ ADD TO RESULT 📝                               ║
║ ───────────────────────────────────────────────║
║ order[0] = 0                                    ║
║ order = [0, _, _, _]                           ║
║ index = 1                                       ║
║                                                 ║
║ ───────────────────────────────────────────────║
║ UPDATE NEIGHBORS 📉                            ║
║ ───────────────────────────────────────────────║
║ Course 0's neighbors: [1, 2]                   ║
║                                                 ║
║   Neighbor 1:                                   ║
║     in-degree[1]-- → 1-1 = 0 ✅               ║
║     Now ready! Add to queue                     ║
║                                                 ║
║   Neighbor 2:                                   ║
║     in-degree[2]-- → 1-1 = 0 ✅               ║
║     Now ready! Add to queue                     ║
║                                                 ║
║ queue = [1, 2]                                  ║
║ in-degree = [0, 0, 0, 2]                       ║
╚═════════════════════════════════════════════════╝

╔═════════════════════════════════════════════════╗
║ 🌊 ITERATION 2: Process course 1               ║
╠═════════════════════════════════════════════════╣
║ Poll: course 1                                  ║
║                                                 ║
║ ADD TO RESULT 📝                               ║
║ order[1] = 1                                    ║
║ order = [0, 1, _, _]                           ║
║ index = 2                                       ║
║                                                 ║
║ UPDATE NEIGHBORS 📉                            ║
║ Course 1's neighbors: [3]                      ║
║                                                 ║
║   Neighbor 3:                                   ║
║     in-degree[3]-- → 2-1 = 1                   ║
║     Still has dependency (course 2)            ║
║     Don't add to queue yet                      ║
║                                                 ║
║ queue = [2]                                     ║
║ in-degree = [0, 0, 0, 1]                       ║
╚═════════════════════════════════════════════════╝

╔═════════════════════════════════════════════════╗
║ 🌊 ITERATION 3: Process course 2               ║
╠═════════════════════════════════════════════════╣
║ Poll: course 2                                  ║
║                                                 ║
║ ADD TO RESULT 📝                               ║
║ order[2] = 2                                    ║
║ order = [0, 1, 2, _]                           ║
║ index = 3                                       ║
║                                                 ║
║ UPDATE NEIGHBORS 📉                            ║
║ Course 2's neighbors: [3]                      ║
║                                                 ║
║   Neighbor 3:                                   ║
║     in-degree[3]-- → 1-1 = 0 ✅               ║
║     Now ready! Add to queue                     ║
║                                                 ║
║ queue = [3]                                     ║
║ in-degree = [0, 0, 0, 0]                       ║
╚═════════════════════════════════════════════════╝

╔═════════════════════════════════════════════════╗
║ 🌊 ITERATION 4: Process course 3               ║
╠═════════════════════════════════════════════════╣
║ Poll: course 3                                  ║
║                                                 ║
║ ADD TO RESULT 📝                               ║
║ order[3] = 3                                    ║
║ order = [0, 1, 2, 3] ✅                        ║
║ index = 4                                       ║
║                                                 ║
║ UPDATE NEIGHBORS 📉                            ║
║ Course 3's neighbors: [] (none)                ║
║ No neighbors to update                          ║
║                                                 ║
║ queue = [] (empty!)                             ║
║                                                 ║
║ BFS Complete! ✅                                ║
╚═════════════════════════════════════════════════╝

FINAL RESULT 🎉

╔═══════════════════════════════════════════════╗
║         🎉 FINAL RESULT: [0,1,2,3]            ║
╠═══════════════════════════════════════════════╣
║                                               ║
║  All courses processed! ✅                    ║
║  index = 4 = numCourses ✅                    ║
║                                               ║
║  Valid topological ordering: [0, 1, 2, 3]    ║
║                                               ║
║  Verification:                                ║
║    Course 0: No prerequisites → taken first  ║
║    Course 1: Needs 0 → 0 before 1 ✅         ║
║    Course 2: Needs 0 → 0 before 2 ✅         ║
║    Course 3: Needs 1,2 → 1,2 before 3 ✅     ║
║                                               ║
║  All prerequisites satisfied! 🎓              ║
║                                               ║
║  Note: [0,2,1,3] also valid!                 ║
║  (1 and 2 can swap - both depend only on 0)  ║
║                                               ║
╚═══════════════════════════════════════════════╝

🔑 Key Observations:

Processing order IS the answer: 📋 No reversal needed with BFS!
In-degrees track readiness: 📊 Zero in-degree = ready to take
Queue ensures correct order: 🌊 Dependencies satisfied before processing
Index check detects cycles: 🔍 index < numCourses would mean cycle
Clean and intuitive: ✨ BFS is perfect for this problem!

📊 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

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

Approach 2 (DFS):
  DFS visit each course once: O(V)
  Explore each edge once: O(E)
  Reverse list: O(V)
  Total: O(V + E) ✅

Both: O(V + E) - same as Course Schedule! ⚡

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, total E entries

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

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

Both: O(V + E) 📦

Same as Course Schedule!
Just added result array/list (O(V))
which doesn't change overall complexity!

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

Core Pattern: Topological Sort with Output 📋

// Template for topological sort with ordering
class Solution {
    // BFS approach (Kahn's) - RECOMMENDED for output
    public int[] topologicalSortBFS(int n, int[][] edges) {
        List<List<Integer>> graph = buildGraph(n, edges);
        int[] inDegree = calculateInDegrees(n, edges);

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

        int[] result = new int[n];
        int index = 0;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            result[index++] = node;  // Collect order! 🔑

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

        return index == n ? result : new int[0];
    }

    // DFS approach - needs reversal
    public int[] topologicalSortDFS(int n, int[][] edges) {
        List<List<Integer>> graph = buildGraph(n, edges);
        int[] state = new int[n];
        List<Integer> order = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (state[i] == UNVISITED) {
                if (hasCycle(graph, state, i, order)) {
                    return new int[0];
                }
            }
        }

        Collections.reverse(order);  // Reverse post-order! 🔄
        return order.stream().mapToInt(Integer::intValue).toArray();
    }
}

When to Use This Pattern 🎯

✅ Need actual topological ordering (not just existence)
✅ Return one valid order (not all)
✅ Dependencies between items
✅ Cycle detection + ordering
✅ Prerequisite-based problems

Recognition triggers: 🔍 - "Return the ordering" or "return order" 📋 - "One valid order" (any valid answer) ✨ - Same as Course Schedule but need ordering 📊 - Topological sort with output 🎯

Key insight: BFS (Kahn's) cleaner for output problems! 💡

Direct Applications:

Course Schedule (LC 207) - Medium 📚 • What's similar: Same graph, same cycle detection 🔄 • What's different: Boolean output, not ordering ✅/❌ • Key insight: Prerequisite problem! 🎯
Alien Dictionary (LC 269) - Hard 👽 • What's similar: Topological sort with output 📋 • What's different: Build graph from word comparison 🔍 • Key insight: Extract dependencies first! 💡
Parallel Courses II (LC 1494) - Hard 🎓 • What's similar: Course dependencies, topological sort 📚 • What's different: Minimize semesters, k courses/semester 📊 • Key insight: Topological levels + optimization! ⚡
Sequence Reconstruction (LC 444) - Medium 🔢 • What's similar: Topological sort, unique ordering 🎯 • What's different: Verify sequences give unique order ✅ • Key insight: Check uniqueness during Kahn's! 🔑

Pattern Progression: 📈

Level 1: Detect Ordering Exists ✅/❌
  └─ Course Schedule (LC 207)

Level 2: Return One Valid Ordering 📋 ← HERE 🎯
  ├─ Course Schedule II (LC 210)
  ├─ Alien Dictionary (LC 269)
  └─ Minimum Height Trees (LC 310)

Level 3: Advanced Topological Sort 🌟
  ├─ Parallel Courses II (LC 1494)
  ├─ Sequence Reconstruction (LC 444)
  └─ Sort Items by Groups (LC 1203)

📝 Quick Revision Notes

🎯 Core Concept

Course Schedule II returns actual topological ordering using BFS (Kahn's) or DFS 📋. BFS is CLEANER: processing order IS answer (no reversal!) 🌊. Calculate in-degrees, queue zero in-degree courses 📊. Process: add to result, decrease neighbors' in-degrees, queue newly-zero ✅. If processed all, return order 🎓. Otherwise empty array (cycle) 🔄. DFS works but needs post-order collection + reversal 🔃. Time: O(V+E) ⚡, Space: O(V+E) 📦. BFS recommended! ⭐

⚡ Quick Implementation (BFS - Recommended)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
  public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<Integer> res = new ArrayList<>();

    // Approach 1 - BFS (kahn)
    res = bfs(numCourses, prerequisites, res); // GOTCHA
    Collections.reverse(res);

    // // Approach 2 - DFS (plus stack)
    // if (dfs(numCourses, prerequisites, res)) { // GOTCHA
    // return new int[0];
    // }

    return res.stream().mapToInt(i -> i).toArray();
  }

  private boolean dfs(int numCourses, int[][] prerequisites, List<Integer> res) {
    // 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, res)) { // has cycle?
          return true;
        }
      }
    }

    return false;
  }

  private boolean dfsUtil(int course, int[] state, ArrayList<ArrayList<Integer>> graph, List<Integer> res) {
    // 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, res)) {
          return true;
        }
      }
    }

    // Step 6: Mark the node as visited
    state[course] = 2;
    res.add(course); // course added to res

    return false;
  }

  private List<Integer> bfs(int numCourses, int[][] prerequisites, List<Integer> res) {
    // 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();
      res.add(course); // course added to res
      coursesTaken++; // course taken

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

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

    return coursesTaken == numCourses ? res : new ArrayList<>();
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(Arrays.toString(s.findOrder(2, new int[][] { { 1, 0 } })));
    System.out.println(Arrays.toString(s.findOrder(4, new int[][] { { 1, 0 }, { 2, 0 }, { 3, 1 }, { 3, 2 } })));
    System.out.println(Arrays.toString(s.findOrder(1, new int[][] {})));
    System.out.println(Arrays.toString(s.findOrder(3, new int[][] { { 0, 2 }, { 1, 2 }, { 2, 0 } })));
  }
}

🔑 Key Insights

BFS vs DFS for Ordering: 🏆

BFS (Kahn's Algorithm): ⭐ RECOMMENDED

Processing order = topological order!
  while (queue not empty):
    course = queue.poll()
    result[index++] = course  // Add directly! ✅

No reversal needed! 🎯

Advantages:
  ✅ Cleaner code
  ✅ More intuitive
  ✅ No reversal step
  ✅ Direct ordering

DFS (Post-order):

Post-order = reverse topological order!
  void dfs(node):
    // ... explore neighbors ...
    result.add(node)  // Add in post-order

  Collections.reverse(result)  // Must reverse! 🔄

Disadvantages:
  ❌ Need reversal step
  ❌ Less intuitive
  ❌ Post-order concept confusing

For ordering problems: USE BFS! 🎯

Why Processing Order Works: 💡

Kahn's algorithm processes in dependency order:

Step 1: Process nodes with in-degree 0
  - These have NO dependencies
  - Safe to process first! ✅

Step 2: Remove processed nodes
  - Decrease neighbors' in-degrees
  - Find NEW zero in-degree nodes

Step 3: Process newly-ready nodes
  - Their dependencies now satisfied
  - Safe to process! ✅

Step 4: Repeat until done

The order we process = valid topological order!

Example:
  Graph: A → B → C

  Round 1: Process A (in-degree 0)
           order = [A]
           B now in-degree 0

  Round 2: Process B
           order = [A, B]
           C now in-degree 0

  Round 3: Process C
           order = [A, B, C] ✅

Processing order respects A→B→C! 🎯

Multiple Valid Orders: ✨

Many problems have multiple valid topological orders!

Example:
       A
      / \
     B   C
      \ /
       D

Valid orders:
  [A, B, C, D] ✅
  [A, C, B, D] ✅

Why? B and C both depend only on A
     Can take in either order!

The problem: "Return ANY valid order"
  Don't need all orders
  Don't need specific order
  Just ONE that works! 🎯

Our BFS returns one valid order
  (Based on queue processing order)
  That's perfect! ✅

Empty Array for Cycles: 🔄

Key difference from Course Schedule:

Course Schedule: return false (boolean)
Course Schedule II: return [] (empty array)

Why empty array signals cycle:
  If cycle exists:
    Some courses never reach in-degree 0
    Never added to queue
    Never processed
    index < numCourses

  Return new int[0] (empty array)

Clean way to signal "impossible"! 📋

Check at end:
  return index == numCourses ? order : new int[0];

Simple and elegant! ✨

🎪 Memory Aid

"BFS gives order as we go" 🌊
"No reversal needed, smooth flow" ⚡
"DFS collects then must reverse the show" 🔄
"For ordering problems, BFS is pro" 🏆 ✨

⚠️ Don't Forget

Use BFS for ordering - cleaner than DFS! ⭐
Processing order IS answer - no reversal needed! 🌊
Add to result while processing - not after! 📝
Check index == numCourses - detects cycles! 🔍
Return empty array on cycle - not null! 📋
Multiple valid orders exist - return any one! ✨

You've mastered Course Schedule II - topological sort with output! 🌟📚✨

190. Course Schedule II

Problem Statement

🌳 Visual Understanding - The Complete Picture

The Problem We're Solving 🤔

Building Understanding Through Examples 📚

The Pattern Emerges 💡

🧠 The Journey From Brute Force to Optimal

Part 1: The Connection - "Building on Course Schedule!" 🤔

Part 2: The DFS Approach - "Post-order is topological!" 💭

Part 3: The BFS Approach - "Processing order IS the answer!" 💡

Part 4: The Comparison - "Which to use?" 💡

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

🎯 Approach 1: BFS (Kahn's Algorithm) - Recommended ⭐

The Key Insight 💡

Complete Implementation

Why This Works 🎯

🎯 Approach 2: DFS with Post-order Collection

The Key Insight 💡

Complete Implementation

Why This Works 🎯

🔍 Detailed Dry Run

BFS Processing 🌊

FINAL RESULT 🎉

📊 Complexity Analysis

Time Complexity: O(V + E) ⚡

Space Complexity: O(V + E) 📦

🔗 Related Problems & Patterns

Core Pattern: Topological Sort with Output 📋

When to Use This Pattern 🎯

Related LeetCode Problems 📚

📝 Quick Revision Notes

🎯 Core Concept

⚡ Quick Implementation (BFS - Recommended)

🔑 Key Insights

🎪 Memory Aid

⚠️ Don't Forget