Determine feasible task ordering

You are given n tasks labeled 0..n−1 and a list of dependency pairs (a, b) meaning task a requires task b to be completed first. Implement functions to (1) determine whether all tasks can be completed and (2) return any valid execution order if it exists. Analyze time and space complexity and discuss how your solution behaves on large sparse versus dense dependency graphs.

Determine feasible task ordering

You are given n tasks labeled 0..n-1 and a list of dependency pairs (a, b), where each pair means task a requires task b to be completed first.

Implement a function taskOrder(n, dependencies) that returns any valid execution order of all tasks if one exists, or an empty list if it is impossible to complete all tasks (i.e., the dependencies contain a cycle).

The returned list both answers part (1) — all tasks can be completed iff the returned list is non-empty (or n == 0) — and part (2) — the list itself is a valid order.

Approach: Model the tasks as a directed graph with an edge b -> a for every pair (a, b) (b must come before a). Run Kahn's algorithm (BFS topological sort): repeatedly pick a task with in-degree 0, append it to the order, and decrement the in-degree of its dependents. If you emit all n tasks, the order is valid; otherwise a cycle exists and you return an empty list.

To make the output deterministic, seed the queue with the in-degree-0 tasks in ascending index order and always pop from the front (FIFO).

Examples:

• n = 2, dependencies = [[1, 0]] -> [0, 1] (task 1 needs task 0 first).
• n = 4, dependencies = [[1, 0], [2, 0], [3, 1], [3, 2]] -> [0, 1, 2, 3] (diamond).
• n = 2, dependencies = [[1, 0], [0, 1]] -> [] (mutual dependency cycle).

Complexity on sparse vs. dense graphs: Let V = n and E = len(dependencies). The algorithm is O(V + E) time and O(V + E) space. On a large sparse graph (E close to V) it is effectively linear in the number of tasks and very memory-light. On a dense graph (E close to V^2, e.g. a near-total ordering) both adjacency storage and the per-edge in-degree decrements grow quadratically, so time and space are dominated by E ~ V^2; an adjacency-matrix variant would waste O(V^2) space even when sparse, which is why an adjacency list is preferred.

Constraints

• 1 <= n <= 10^5
• 0 <= len(dependencies) <= 10^5
• Each dependency is a pair [a, b] with 0 <= a, b < n and a != b
• There may be duplicate dependency pairs; the answer must still be a valid topological order
• Return an empty list when the tasks cannot all be completed (the dependency graph has a cycle)

Hints

1. Build a directed graph where the edge points from the prerequisite to the dependent: for pair (a, b), add b -> a. Then any task with in-degree 0 has no remaining prerequisites and can run now.
2. Use Kahn's algorithm (BFS topological sort): start from all in-degree-0 tasks, and each time you 'complete' a task, decrement the in-degree of its dependents and enqueue any that reach 0.
3. If you manage to output fewer than n tasks, some tasks are stuck in a cycle and can never be completed — return an empty list. For deterministic output, seed and process the queue in ascending index order.