Course Schedule II

Medium

Kahn's algorithm, keeping the order

Problem

Return an order to finish all courses given prerequisites, or empty if impossible.

In simple words

Topological sort with Kahn's algorithm gives a legal order, or nothing if a cycle blocks it.

The idea

Repeatedly take a course whose in-degree has fallen to zero, append it to the order, and decrement its dependents. If the output is shorter than the course count, a cycle blocked it and no order exists.

The trick

In-degree zero means every prerequisite is already scheduled.
Return an empty list when the output is incomplete.
DFS postorder reversed gives an equally valid order.

←→stepspaceplay

indegrees[0,1,2,1]

1/6

Optimal

timeO(V+E)spaceO(V+E)

Cycle ⇒ impossible.

1q = every course whose indegree is 02while q not empty:3  c = q.pop(); processed += 14  for nb in adj[c]: indeg[nb] -= 1; if now 0, q.push(nb)5return processed == numCourses

Input

nodes: 4, 4 edges

Memory

indegrees: [0,1,2,1]
processed: —

Output

finish: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: n = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output:: [0, 1, 2, 3]
Explanation:: A valid order finishing all courses.

Example 2

Input:: n = 2, prerequisites = [[1,0]]
Output:: [0, 1]
Explanation:: Take 0 then 1.

Example 3

Input:: n = 2, prerequisites = [[1,0],[0,1]]
Output:: []
Explanation:: Cycle → empty order.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.