Show problems as
Classic problem #210MediumDepth-First SearchBreadth-First SearchGraph TheoryTopological Sort

Course Schedule II

Real-world version: Module Build Order
Tracked in this browser only
Read Course Schedule II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstCycle Detection · Graphs, animated step by step

A release engineer compiles a project whose moduleCount modules are labelled 0 through moduleCount - 1. Each module is compiled exactly once. Every entry [x, y] of dependencies says that module y has to finish compiling before module x may start.

Plenty of sequences can satisfy the same dependency set, so the build tool fixes one: whenever more than one module is unblocked, it always takes the lowest-numbered candidate. That rule makes the answer the lexicographically smallest valid sequence. Return that sequence.

If the dependencies leave no way to compile every module, return an empty array.

Examples

Example 1

Input
moduleCount = 3, dependencies = [[1, 0]]
Output
[0, 1, 2]

Module 0 gates module 1 while module 2 is free from the start, and always grabbing the lowest unblocked label produces 0, 1, 2.

Example 2

Input
moduleCount = 5, dependencies = [[2, 0], [3, 2], [1, 3], [4, 1]]
Output
[0, 2, 3, 1, 4]

The entries chain the modules single file, so only one sequence exists no matter which candidate rule is applied.

Example 3

Input
moduleCount = 2, dependencies = [[0, 1], [1, 0]]
Output
[]

Each of the two modules waits on the other, so neither can ever start and the array comes back empty.

Constraints

  • 1 <= moduleCount <= 2000
  • 0 <= dependencies.length <= moduleCount * (moduleCount - 1)
  • dependencies[i].length == 2
  • 0 <= x, y < moduleCount
  • x != y
  • No pair [x, y] is repeated
  • Among all valid sequences, return the lexicographically smallest

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def build_order(moduleCount: int, dependencies: list[list[int]]) -> list[int]:
Java
public int[] buildOrder(int moduleCount, int[][] dependencies)

More on the same topics