How do you approach Course Schedule II (Find Order)?

Build the graph edge b -> a (prerequisite points at the course it unlocks) and count each course's indegree.

What is the time complexity of Course Schedule II (Find Order)?

Time complexity: O((V + E) log V) with the heap; O(V + E) with a plain queue if any order is acceptable.. Space complexity: O(V + E).

What are common mistakes on Course Schedule II (Find Order)?

Not detecting the cycle. If fewer nodes come out than went in there is no valid ordering, and that is usually the real question. Building the edges the wrong way round - prerequisite pairs are the classic reversal. Seeding the queue with every node instead of only those with zero indegree.

gitGood.dev

← Back to problems

Course Schedule II (Find Order)

MediumAlgorithms

Description

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

Return an ordering of courses you can take to finish them all. If that is impossible, return an empty array.

Tie-break rule: when several courses are available at the same time, always take the lowest-numbered one first. This makes the valid answer unique.

Example 1

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

Output: [0,1]

Example 2

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

Output: [0,1,2,3]

Example 3

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

Output: []

Constraints

- 1 <= numCourses <= 2000 - 0 <= prerequisites.length <= 5000 - prerequisites[i] = [a, b] with a != b, no duplicate pairs - Return [] if the prerequisites contain a cycle.

Course Schedule II (Find Order): approach, complexity and pitfalls

A medium topological sort problem, graded against 6 test cases (3 of them hidden).

The pattern: Topological Sort

Ordering a directed acyclic graph so every dependency comes first.

Reach for it when you see: Prerequisites, build order, task scheduling, or "can this be completed?"

If you are stuck

Show the 3-step hint ladder

Build the graph edge b -> a (prerequisite points at the course it unlocks) and count each course's indegree.
Kahn's algorithm: start from every course with indegree 0, pop one, append it to the order, and decrement its neighbours - pushing any that reach indegree 0.
For the lowest-numbered tie-break, keep the available set in a min-heap rather than a plain queue. If the finished order is shorter than numCourses, a cycle exists - return [].

The optimal approach

Show the approach: Kahn's algorithm, with a heap for determinism

Edges point from prerequisite to dependent (`b -> a`), and a course's indegree is the number of prerequisites it still needs. Courses with indegree 0 are takeable now.

Kahn's algorithm repeatedly removes an available course, appends it to the order, and decrements the indegree of everything it unlocks, adding newly-freed courses to the available set. Each edge is relaxed exactly once, so it is linear.

Cycle detection is free. If a cycle exists, every course in it keeps a positive indegree forever and never becomes available, so the loop ends early. Comparing the produced order's length against `numCourses` is the whole check - no separate DFS colouring pass.

Normally any topological order is acceptable, which makes the answer non-unique. The lowest-numbered tie-break pins it down: swap the FIFO queue for a min-heap so the smallest available course is always chosen. That is a common real-world requirement too, where builds want a reproducible order rather than merely a valid one.

Time: O((V + E) log V) with the heap; O(V + E) with a plain queue if any order is acceptable.
Space: O(V + E)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Topological Sort mistakes

These apply to the pattern as a whole, not just this problem.

Not detecting the cycle. If fewer nodes come out than went in there is no valid ordering, and that is usually the real question.
Building the edges the wrong way round - prerequisite pairs are the classic reversal.
Seeding the queue with every node instead of only those with zero indegree.