Practice/Uber/Package Installation Order

Package Installation Order

CodingMust

Problem

You are building a software system with multiple modules that have dependencies on each other. Before a module can be built, all of its dependencies must be built first.

Given the total number of modules (numbered from 0 to modules - 1) and a list of dependency pairs, determine a valid order in which to build all modules. Each dependency pair [a, b] means that module a depends on module b, so module b must be built before module a.

If there is a circular dependency that makes it impossible to build all modules, return null (or None in Python).

Requirements

1. Return an array containing the build order for all modules
2. Each module must appear exactly once in the result
3. For every dependency pair [a, b], module b must appear before module a in the result
4. If a valid build order is impossible due to circular dependencies, return null
5. If multiple valid build orders exist, any one of them is acceptable

Constraints

• 1 ≤ modules ≤ 1000
• 0 ≤ dependencies.length ≤ 5000
• dependencies[i].length == 2
• 0 ≤ dependencies[i][0], dependencies[i][1] < modules
• All dependency pairs are unique
• No module depends on itself directly (no [a, a] pairs)
• Expected time complexity: O(modules + dependencies.length)
• Expected space complexity: O(modules + dependencies.length)

Examples

Example 1:

` Input: modules = 4, dependencies = [[1, 0], [2, 1], [3, 2]] Output: [0, 1, 2, 3] Explanation:

• Module 0 has no dependencies
• Module 1 depends on module 0
• Module 2 depends on module 1
• Module 3 depends on module 2 This forms a linear chain, so we build them in order: 0 → 1 → 2 → 3 `

Example 2:

Input: modules = 3, dependencies = [[0, 1], [1, 2], [2, 0]] Output: null Explanation: There is a circular dependency cycle: 0 → 1 → 2 → 0 This makes it impossible to determine a valid build order.

Example 3:

` Input: modules = 5, dependencies = [[1, 0], [2, 0], [3, 1], [4, 2]] Output: [0, 1, 2, 3, 4] (or [0, 2, 1, 4, 3] or other valid orderings) Explanation:

• Module 0 has no dependencies, build it first
• Modules 1 and 2 both depend only on 0, so build them next (either order works)
• Module 3 depends on 1, and module 4 depends on 2 Multiple valid build orders exist. `