Coding · Graphs and grids
Course Schedule II
- Appears on company lists
- Medium
- Senior
- 1 source
Company-tagged lists or prep guides name it; no candidate write-up was found.
Solve it in the playground, with tests
There are numCourses courses labelled 0 to numCourses - 1, and each pair [a, b] means course b must be finished before course a. Return an order in which all courses can be taken, or an empty list if the pairs contain a cycle and no order exists. For numCourses = 5 and pairs [[1,4],[2,4],[3,1],[3,2],[0,3]] one valid order is [4,1,2,3,0]. Any valid order is correct in an interview, so the reference here is deterministic: it starts with free courses in increasing label order and visits each course's dependants in the order the pairs were given.
Restated in our own words, not a quote from Netflix or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I ask which way the pair points: in [a, b], is b the prerequisite of a? Can the same pair appear twice, can a course require itself, and can a course have no relationships at all? How large can the numbers of courses and pairs be? If more than one order exists, is any order accepted? And what exactly should I return when no order exists?
Assumptions: [a, b] means b comes first, duplicate pairs and self-pairs can occur, isolated courses still appear in the answer, any valid order is accepted but I produce a deterministic one, a cycle returns an empty list, and sizes reach a few thousand courses and pairs. A linear-time solution that avoids deep recursion is welcome.
Brute force
Say the obvious answer and why it is too slow.
One brute force tries every ordering of the courses and checks every pair against each ordering. That is O(n!) orderings times the pair check, hopeless beyond about ten courses. A smarter brute force repeats a scan: look through all courses for one that is not taken yet and whose prerequisites have all been taken, take it, and start over. Each round scans every course and its prerequisites, and there are n rounds, so the cost is O(V·(V+E)). For a few thousand courses with many pairs that is tens of millions of steps, workable here but wasteful, and it hides the structure of the problem. The waste is rescanning courses that are plainly not ready yet. A better method tracks readiness incrementally, which is what indegree counting does.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(V·(V+E))
- Time
- O(V + E)
- Space
- O(V + E)
This is topological sorting, done with Kahn's algorithm. Treat each pair as a directed edge from the prerequisite to the course that needs it. A valid order exists exactly when the graph has no cycle, and an order is any arrangement in which every edge points forward.
For each course I track its indegree, the number of prerequisites not yet taken. A course with indegree zero is ready. I put all ready courses into a queue. Then I repeatedly take the front course, add it to the order, and for each course that depends on it I reduce that course's indegree by one; if it reaches zero it has just become ready, so I queue it. Since the order list is also the queue, one array does both jobs, with a read pointer chasing the end.
Why it is correct: a course enters the order only after its indegree has reached zero, which happens only after each of its prerequisites was processed, so every edge points forward in the output. For a cycle, no course on it ever reaches zero, because each one waits on another course of the cycle. Those courses never enter the order, so the order ends up shorter than numCourses and I return an empty list. A duplicate pair counts twice when the indegree counts are built and decrements twice when processed, so it cancels out.
Out loud: peel off courses with nothing left to wait for, and if I get stuck before everything is peeled, there is a cycle. Each course and each pair is handled once, so the time is O(V + E).
Walk it through
A dry run on the example, step by step.
| step | take | indegree 0..4 | ready queue | order so far |
|---|---|---|---|---|
| 0 | - | 1 1 1 2 0 | 4 | (empty) |
| 1 | 4 | 1 0 0 2 0 | 1,2 | 4 |
| 2 | 1 | 1 0 0 1 0 | 2 | 4,1 |
| 3 | 2 | 1 0 0 0 0 | 3 | 4,1,2 |
| 4 | 3 | 0 0 0 0 0 | 0 | 4,1,2,3 |
| 5 | 0 | 0 0 0 0 0 | (empty) | 4,1,2,3,0 |
Take five courses with pairs [[1,4],[2,4],[3,1],[3,2],[0,3]]. Counting prerequisites gives indegree values 1, 1, 1, 2, 0 for courses 0 to 4, so only course 4 is ready. Taking 4 frees courses 1 and 2, in the order the pairs were given. Taking 1 lowers course 3 from two waiting prerequisites to one. Taking 2 lowers it to zero, so 3 joins the queue. Taking 3 frees course 0, and taking 0 ends the run. The order has five entries, which equals numCourses, so no cycle was found. The result is [4,1,2,3,0]. The indegree column in the trace shows each count falling to zero exactly when its course becomes ready.
The code
Runnable JavaScript, checked against test cases.
function findOrder(numCourses, prerequisites) {
const dependents = Array.from({ length: numCourses }, () => []);
const indegree = new Array(numCourses).fill(0);
for (const [course, prerequisite] of prerequisites) {
dependents[prerequisite].push(course);
indegree[course]++;
}
const order = [];
for (let course = 0; course < numCourses; course++) {
if (indegree[course] === 0) order.push(course);
}
for (let head = 0; head < order.length; head++) {
for (const next of dependents[order[head]]) {
indegree[next]--;
if (indegree[next] === 0) order.push(next);
}
}
return order.length === numCourses ? order : [];
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
- No pairs: every course starts ready, so the answer is the labels in increasing order.
- One course: the answer is [0] with no pairs, and an empty list if the course requires itself.
- Self-pair [0,0]: the course waits on itself, never reaches zero, and the order comes out short.
- Duplicate pairs: the same pair counted twice is decremented twice, so the course still becomes ready.
- Cycle in only part of the graph: the other courses are processed, but the order is still short, so the whole answer is an empty list.
- Long chain: the queue loop is iterative, so there is no recursion depth to overflow.
Follow-ups to expect
Where the interviewer pushes next.
- How would you solve it with depth-first search, and how do you detect a cycle there?
- How would you return the lexicographically smallest valid order?
- How would you find the minimum number of semesters if you may take any number of courses at once?
- How would you report which courses form the cycle instead of just returning an empty list?
- How would the approach change if new pairs arrive one by one over time?
Where candidates slip
The mistakes this problem punishes.
- Reversing the edge direction by reading [a, b] as a before b.
- Returning the partial order when a cycle exists instead of an empty list.
- Forgetting courses that have no pairs at all, which have indegree zero and still belong in the order.
- Using
shift()on a large queue in a loop, which is O(n) per call in the worst case. - Writing a depth-first version with a single visited flag, which reports false cycles or misses real ones.
- Building the adjacency list and the indegree array from different sides of the pair.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.