Compute build order from dependencies

Given a set of package build dependencies, output a valid build order so that each package is built only after all of its dependencies. The input is a list of (package, dependency) pairs or an adjacency list. Return one valid order, or report that no order exists if there is a cycle. Explain your algorithm, analyze time and space complexity, handle edge cases such as disconnected components and duplicate dependencies, and compare a BFS in-degree approach (Kahn's algorithm) with a DFS post-order approach, justifying your choice.

Compute Build Order from Dependencies

You are given n packages labeled 0 to n - 1 and a list of build dependencies. Each pair [a, b] means package a depends on package b, so b must be built before a.

Return one valid build order such that every package appears only after all of its dependencies. If no valid order exists (the dependency graph contains a cycle), return an empty list.

To make the answer unique and easy to grade, when several packages are simultaneously ready to be built, always pick the one with the smallest label first.

Duplicate dependency pairs may appear and must be treated as a single edge. Packages with no dependencies (including fully disconnected ones) are still part of the output.

Example 1

Input:  n = 4, dependencies = [[1,0],[2,0],[3,1],[3,2]]
Output: [0, 1, 2, 3]

Package 0 has no dependency, 1 and 2 depend on 0, and 3 depends on both 1 and 2.

Example 2

Input:  n = 2, dependencies = [[1,0],[0,1]]
Output: []

0 and 1 depend on each other — a cycle, so no order exists.

Example 3

Input:  n = 3, dependencies = []
Output: [0, 1, 2]

No dependencies; all three are independent components, returned in label order.

Constraints

• 0 <= n <= 10^4
• 0 <= dependencies.length <= 10^5
• Each dependency is a pair [a, b] with 0 <= a, b < n and a != b
• Duplicate dependency pairs may appear and count as one edge
• Among packages that are simultaneously ready, build the smallest-label one first
• Return [] if and only if the dependency graph contains a cycle

Hints

1. Model packages as nodes and each dependency [a, b] as a directed edge b -> a (b must come before a). The build order is a topological sort of this graph.
2. Use Kahn's algorithm: repeatedly take a node with in-degree 0, append it to the order, and decrement the in-degree of its successors. Deduplicate edges first so duplicate pairs don't inflate in-degrees.
3. For the deterministic 'smallest label first' rule, replace the plain queue with a min-heap of ready nodes. If at the end you have placed fewer than n nodes, some nodes were stuck in a cycle — return an empty list.
4. The alternative DFS post-order approach pushes a node onto a stack after visiting all its dependencies, then reverses the stack; it detects cycles via a recursion/'in-progress' marker. Kahn's is often preferred here because in-degree tracking makes the smallest-label tie-break and cycle reporting straightforward without deep recursion.