Introduction

Course Schedule II is an extension of Course Schedule.

You are given:

numCourses
prerequisites[][]

Goal:

Return a valid order to complete all courses.

If it is impossible:

Return []

Example

Input:

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

Output:

[0,1,2,3]

Another Valid Output:

 [0,2,1,3]

Key Observation

Course Schedule I asks:

Can we finish all courses?

Course Schedule II asks:

Can we finish all courses?

If cycle exists:

No valid ordering exists.

Algorithm

1. Build graph
2. Calculate indegree
3. Push indegree 0 nodes
4. Perform BFS
5. Store answer
6. Reduce indegrees
7. Return order

Dry Run

Graph:

0 → 1
↓
2
1 → 3
2 → 3

Indegree:

0 = 0
1 = 1
2 = 1
3 = 2

Queue:

[0]

Process:

0
↓
1,2
↓
3

Answer:

[0,1,2,3]

Approach : Topological Sort (Kahn's Algorithm)

Explanation

For every course:

  1. Build dependency graph.
  2. Track indegrees.
  3. Start BFS from indegree 0 nodes.
  4. Store traversal order.
  5. Return ordering if all nodes are visited.

Practice

Complexity Analysis

Topological Sort (Kahn's Algorithm)Time Complexity: O(V + E)
Space Complexity: O(V + E)

Why This Problem is Important

  • Topological Sort
  • Kahn's Algorithm
  • Graph Traversal
  • BFS
  • Dependency Resolution

Common Beginner Mistakes

  • Reversing edge direction
  • Wrong indegree updates
  • Forgetting to store order
  • Returning partial answers
  • Ignoring cycles

Interview Tip

Always explain:

Course Schedule I
→ Check existence

Course Schedule II
→ Return ordering

Both use the same Topological Sort algorithm.

Related Questions

  • Course Schedule
  • Alien Dictionary
  • Parallel Courses
  • Minimum Height Trees
  • Graph Valid Tree

Final Takeaway

Course Schedule II is a classic Topological Sort problem.

It teaches:

  • Kahn's Algorithm
  • Graph Traversal
  • Dependency Ordering
  • BFS on DAGs

Mastering Course Schedule II makes advanced dependency and graph-ordering interview problems significantly easier.