Course Schedule II

You must take numCourses courses (0 .. numCourses-1). prerequisites[i] = [a, b] means course b must be taken before course a. Return a valid order in which to take all courses; if several are valid, return the lexicographically smallest. If finishing all courses is impossible (a cycle), return an empty array.

Hints

· Stuck? Reveal one nudge at a time.

Build the prerequisite graph (edge b -> a) and topologically sort it.

Use Kahn's algorithm; emit the smallest ready course from a min-heap for the smallest order.

If fewer than numCourses get emitted, a cycle exists — return [].

Common doubts

A plain queue gives some valid order; the min-heap always emits the smallest ready course, producing the lexicographically smallest schedule.

If Kahn's outputs fewer than numCourses courses, the leftovers are in a cycle — return an empty array.

Yes — empty means impossible; a single-element order means that one course has no prerequisites.

Interview follow-ups

· What an interviewer asks next.

Reverse of DFS finish times gives a topological order, though not the lexicographically smallest without extra care.

That's exponential in general; you'd enumerate via backtracking over ready sets.

Fun facts

LeetCode 210 — Course Schedule I with the actual schedule returned.
This is exactly how build tools compute a compilation order.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0, 1, 2, 3]
0 first; then 1 before 2; then 3.

Example 2

Input: numCourses = 2, prerequisites = [[0,1],[1,0]]
Output: []
A cycle makes any order impossible.

Constraints

- 1 <= numCourses <= 10^5 - 0 <= prerequisites.length <= 10^5 - no duplicate prerequisite pairs

This is Course Schedule I plus the actual order. Build the prerequisite graph ([a, b] ⇒ edge b → a) and run Kahn's algorithm, outputting courses as their in-degree reaches 0. If a cycle blocks some courses (fewer than numCourses get output), return [].

Several courses may be ready at once, so for the lexicographically smallest order always emit the smallest-labelled ready course — a min-heap. The brute version rescans for the smallest ready course each step (O(V²)); the heap version is O((V+E) log V).

Prerequisites

Before you start

· Concepts used directly in the solution.

Kahn's algorithm. order courses as prerequisites clear.

Min-heap tie-break. smallest ready course for lexicographic order.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Which order if several are valid?”

Lexicographically smallest.

“What if it's impossible?”

Return an empty array.

The ideal opening — say it like this

I run Kahn's on the prerequisite graph, emitting the smallest ready course from a min-heap.

If fewer than numCourses come out, a cycle exists — return empty.

Understand the problem

Worked example — numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

ready {0} -> 0; ready {1,2} -> 1 then 2; ready {3} -> 3
order = [0, 1, 2, 3]

Key observations

1Aha

Order = topological order

Of the prerequisite DAG.

2Aha

Min-heap for smallest order

Emit the smallest ready course each step.

3Aha

Incomplete ⇒ empty

A cycle prevents ordering all courses.

Brute force vs optimal

	Smallest-zero scan	Kahn's + min-heap
Pick next	scan all courses	pop the heap
Time	O(V²)	O((V+E) log V)
Cycle	return []	return []

Both produce the same lexicographically-smallest order (or empty). Full code is in the Approaches selector below.

Summary

Key takeaway

Kahn's on the prerequisite graph, emitting the smallest ready course (min-heap) — the lexicographically smallest order. Empty if a cycle blocks completion. O((V+E) log V).

heap of indeg-0 courses; pop smallest, output, decrement successors
if output count < numCourses -> []