Determine task order with prerequisites

You are given n tasks labeled 0..n−1 and a list of prerequisite pairs (a, b) meaning task b must be completed before task a. Determine one valid order in which to complete all tasks, or report that it is impossible if dependencies contain a cycle. Describe the algorithm, data structures, and complexity, and explain how you would detect cycles and handle multiple valid orders.

Determine Task Order with Prerequisites

You are given an integer n representing tasks labeled 0 to n-1, and a list of prerequisite pairs prerequisites where each pair [a, b] means task b must be completed before task a.

Return one valid order in which all tasks can be completed. If the dependencies contain a cycle (making a valid ordering impossible), return an empty list.

This is a topological sort. When multiple valid orderings exist, return the one that is lexicographically smallest (always pick the smallest-labeled task among those whose prerequisites are all satisfied), so the answer is deterministic.

Example:

• n = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] -> [0, 1, 2, 3] (task 0 first, then 1 and 2, then 3).
• n = 2, prerequisites = [[0,1],[1,0]] -> [] (cycle: 0 needs 1 and 1 needs 0).

Constraints

• 0 <= n <= 10^5
• 0 <= prerequisites.length <= 10^5
• prerequisites[i] = [a, b] with 0 <= a, b < n
• A pair [a, b] means b must be completed before a
• Return [] if the prerequisite graph contains a cycle

Hints

1. Model tasks as nodes in a directed graph. For each pair [a, b], task b must come before a, so add a directed edge b -> a and increment the in-degree of a.
2. Use Kahn's algorithm (BFS topological sort): repeatedly take a task whose in-degree is 0, append it to the order, and decrement the in-degree of its dependents, adding any that reach 0.
3. A cycle exists exactly when you cannot place all n tasks (the final order has fewer than n elements). In that case return an empty list.
4. To make the result deterministic among multiple valid orderings, pick the smallest available task each step using a min-heap (priority queue) instead of a plain queue.