Level-Ordered Dependency Build Order

Problem Statement

You are tasked with building a dependency manager for a task-based build system. You are given n tasks, labeled 0 to n-1, and a list of dependencies where [u, v] indicates that task u must be completed before task v can begin.

Your goal is to return the tasks grouped by "levels." A task can be assigned to a level if all its dependencies have been completed in previous levels. Tasks with no dependencies belong in level 0. If a valid ordering is impossible due to a circular dependency, return an empty list.

Function Signature

def get_build_levels(n: int, dependencies: List[List[int]]) -> List[List[int]]:

Constraints

• 1 <= n <= 10,000
• 0 <= len(dependencies) <= 100,000
• dependencies[i] are distinct pairs.

Examples

Example 1: Input: n = 4, dependencies = [[0, 1], [0, 2], [1, 3], [2, 3]] Output: [[0], [1, 2], [3]] Explanation: Task 0 starts at level 0. Tasks 1 and 2 depend on 0, so they start at level 1. Task 3 depends on 1 and 2, starting at level 2.

Example 2: Input: n = 2, dependencies = [[0, 1], [1, 0]] Output: [] Explanation: A cycle exists (0 -> 1 -> 0), so no valid order exists.

Edge Cases

• Disconnected components (e.g., tasks with no dependencies that don't relate to each other).
• n = 1 with no dependencies.
• Empty dependencies list.