Problem Statement
You manage N microservices. Some services depend on others being deployed first (e.g., auth-service must be live before payment-service). You're given a list of dependency pairs [a, b] meaning "a must be deployed before b."
Return a valid deployment order. If the dependencies contain a cycle (making deployment impossible), detect it and return an empty list.
Constraints
1 <= N <= 10^50 <= dependencies.length <= 2 * 10^5- Services are labeled
0toN-1 - There may be multiple valid orders — return any
Example
Input:
N = 4
dependencies = [[0,1], [0,2], [1,3], [2,3]]
Output: [0, 1, 2, 3] (or [0, 2, 1, 3])
Explanation: Service 0 first, then 1 and 2 (both depend on 0), then 3 (depends on both).
Cycle case: dependencies = [[0,1], [1,2], [2,0]] → Output: [] (circular dependency, impossible)
The Insight — Topological Sort (Kahn's Algorithm)
Deployment order = topological sort of a directed graph. The elegant part is that the same algorithm detects cycles for free.
Kahn's algorithm (BFS-based):
- Compute the in-degree (number of prerequisites) of each service.
- Start with all services that have in-degree 0 (no dependencies) — these can deploy first.
- Repeatedly: pick a zero-in-degree service, add it to the order, and decrement the in-degree of everything depending on it. When something hits in-degree 0, it's ready.
- Cycle detection is automatic: if you processed fewer than N services at the end, a cycle exists (some services never reached in-degree 0 because they depend on each other).
That last point is the beauty — you don't need a separate cycle-detection pass. If the topological sort can't consume every node, the graph has a cycle. One algorithm, two answers.
Follow-ups
- Why does "processed count < N" guarantee a cycle?
- How would you return the SHORTEST deployment (fewest parallel stages)? (level-by-level BFS)
- If services can deploy in parallel, what's the minimum number of deployment rounds?
- How would you find WHICH services are involved in the cycle?