loading

Course Schedule II — Step-by-Step Visualization

mediumLeetCode #210GraphDFSBFSTopological Sort

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`. 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.

Algorithm Pattern

Topological Sort (Kahn's or DFS)

Key Idea

Unlike Course Schedule I, which only detects cycles, this problem requires the actual linear ordering. Using Kahn's Algorithm (BFS): 1. Calculate the in-degree of each node. 2. Add all nodes with 0 in-degree into a queue. 3. While the queue is not empty: pop a node, add it to the result, and decrement the in-degree of all its neighbors. If a neighbor reaches 0 in-degree, add it to the queue. If the final result has fewer nodes than `numCourses`, a cycle exists.

Step-by-Step Approach

  1. Build adjacency list and compute in-degrees for all nodes.
  2. Add nodes with 0 in-degree to a queue.
  3. While queue is not empty:
  4. Pop node `u`, append to `result`.
  5. For each neighbor `v` of `u`:
  6. Decrement `in_degree[v]`. If it becomes 0, add `v` to queue.
  7. If `len(result) == numCourses`, return `result`. Else return `[]`.

Common Gotchas

  • Multiple valid topological orders may exist.
  • A cycle anywhere in the graph will prevent some nodes from ever reaching 0 in-degree.

Related Problems

← All problems