FAANGPrep Sprint
Course Schedule
Decide whether every course can be finished, by counting how many Kahn's algorithm can take before a prerequisite cycle stops it.
Examples
Take course 0, then course 1.
Each course needs the other first, so neither can ever be taken.
Problem Understanding
There are numCourses courses labeled 0 to numCourses - 1. You are given prerequisites array where [a, b] means taking course b is mandatory before a.
Return true if you can finish all courses, false otherwise (i.e., if there is a cycle).
Strategy (Kahn's Algorithm)
A course can be taken once all of its prerequisites have been. Count down to that moment for every course:
Turn each pair
[course, prereq]into an edgeprereq → course, and count each course's prerequisites (its in-degree).Queue every course whose count is 0 — nothing stands in its way.
Take the front course and add one to taken; each course it unlocks loses one prerequisite, and any that reaches 0 joins the queue.
When the queue is empty, every course can be finished exactly when taken == numCourses. A course on a prerequisite cycle — or after one — never reaches 0.
Interactive Visualization
ARROW = PREREQUISITE → COURSE · NUMBER ABOVE = PREREQUISITES STILL UNTAKEN · RED = HELD BACK BY A CYCLE
COUNT PREREQUISITES
taken
0/5
queued
0
Answer
—
queue (front first)
Empty
taken
None yet
Turn 5 pairs into edges prerequisite → course, and count each course's prerequisites: [0, 1, 1, 1, 2]
Next
Queue the courses with no prerequisites: [0]
prerequisites
courses
Each arrow runs from a prerequisite to the course it unlocks — the pair [1, 0] is drawn 0 → 1. The number above a course is how many of its prerequisites are still untaken.
Watch the taken counter beside the figure: every course that leaves the queue adds one. The answer is nothing more than whether it reaches numCourses. Try Blocked — courses 0 and 4 are taken, then the queue runs dry with 1, 2 and 3 in red: 1 and 2 need each other, and 3 needs 2.