FAANGPrep Sprint

Course Schedule II

Return an order in which every course can be taken — Kahn's algorithm writes it out, and a prerequisite cycle empties it.

MediumSolve on LeetCode

Examples

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

Output:[0,1]

Explain:

Course 0 has no prerequisites; course 1 needs 0.

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

Output:[0,1,2,3]

Explain:

LeetCode prints [0,2,1,3]; both respect every pair, and any valid order is accepted.

Input:numCourses = 1, prerequisites = []

Output:[0]

Explain:

One course and nothing to wait for.

Problem Understanding

There are numCourses courses labelled 0 to numCourses - 1, and prerequisites[i] = [a, b] means you must take course b before course a.

Return an ordering of the courses in which you could take all of them. If several orders work, return any one; if it is impossible — because some prerequisites form a cycle — return an empty array.

It is Course Schedule with the answer written out: instead of asking whether every course can be taken, return the order you took them in.

Strategy (Kahn's Algorithm)

The Course Schedule method, keeping the order instead of only counting it:

Turn each pair [course, prereq] into an edge prereq → course, and count each course's prerequisites.
Queue every course with no prerequisites.
Take the front course and append it to the order; each course it unlocks loses one prerequisite, and any that reaches 0 joins the queue.
If the order holds all numCourses courses, return it. Otherwise a cycle kept some courses out of the queue for good — return [].

Interactive Visualization

ARROW = PREREQUISITE → COURSE · NUMBER ABOVE = PREREQUISITES STILL UNTAKEN · RED = HELD BACK BY A CYCLE

COUNT PREREQUISITES

ordered

0/4

queued

Answer

—

queue (front first)

Empty

order

Nothing yet

Turn 4 pairs into edges prerequisite → course, and count each course's prerequisites: [0, 1, 1, 2]

Queue the courses with no prerequisites: [0]

prerequisites

courses

Each arrow runs from a prerequisite to the course it unlocks, and the number above a course is how many of its prerequisites are still untaken. A course joins the order beside the figure the moment it leaves the queue, so the order is the answer being written.

Load Example 2: this run gives [0, 1, 2, 3] where LeetCode prints [0, 2, 1, 3] — 1 and 2 are both freed by 0, and either may go first. Load Cycle to see the order stop short and the answer become [].