The problem
Given numCourses and prerequisite pairs [a, b] meaning "take b before a", return any valid order to take all courses, or an empty array if impossible (a cycle exists).
Stuck? Reveal hints one at a time
How to approach it
- 1Build adjacency list b → a and count in-degrees (number of unmet prerequisites) per course.
- 2Queue every course whose in-degree is 0 — nothing blocks them.
- 3Pop a course, append it to the order, and decrement the in-degree of each dependent; enqueue dependents that reach 0.
- 4If the final order contains all courses, return it; otherwise a cycle blocked some courses — return [].
Key insight
If the queue empties before every course is placed, the leftover courses form (or depend on) a cycle — no valid order exists.
The solution
Watch out for
- Edge direction trips people: [a, b] means b BEFORE a, so the edge is b → a.
- Using Array.shift() on huge inputs is O(n) per pop in JS — use an index pointer for strict O(V+E).