Apple: Smallest Valid Task Order from Dependency Pairs (Topological Sort)

Quick Overview

Given a number of tasks and dependency pairs, return the lexicographically smallest order that completes every task while respecting all dependencies, or an empty list when a cycle makes that impossible. Tests topological sorting, cycle detection and deterministic tie-breaking on large dependency graphs.

Smallest Valid Task Order from Dependency Pairs (Topological Sort)

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

A project consists of `n` tasks labeled `0` to `n - 1`, done one at a time. Some tasks depend on others: a dependency pair `[a, b]` means task `a` must be finished before task `b` can start. Return an order in which all `n` tasks can be done without violating any dependency. Several orders may be valid; return the lexicographically smallest one. If the dependencies make it impossible to finish every task, return an empty list. ### Function Signature ```python def task_order(n: int, dependencies: list[list[int]]) -> list[int]: ``` `dependencies[i] = [a, b]` means task `a` must come before task `b`. ### Rules - A valid order contains every task from `0` to `n - 1` exactly once, and for every pair `[a, b]`, task `a` appears before task `b`. - Order `x` is lexicographically smaller than order `y` if, at the first index where they differ, `x` has the smaller task label. - If no valid order exists because the dependencies contain a cycle, return `[]`. - The same pair may appear more than once; duplicates express the same constraint. ### Constraints - `1 <= n <= 10^5` - `0 <= len(dependencies) <= 2 * 10^5` - Each `dependencies[i]` has exactly two elements `[a, b]` - `0 <= a <= n - 1`, `0 <= b <= n - 1`, and `a != b` ### Examples **Example 1** ```text Input: n = 4, dependencies = [[1, 0], [2, 0], [3, 1], [3, 2]] Output: [3, 1, 2, 0] ``` Task 3 must precede tasks 1 and 2, and both of those must precede task 0. The valid orders are `[3, 1, 2, 0]` and `[3, 2, 1, 0]`; the first is lexicographically smaller. **Example 2** ```text Input: n = 3, dependencies = [[2, 0]] Output: [1, 2, 0] ``` Task 2 must precede task 0, and task 1 is unconstrained. The valid orders are `[1, 2, 0]`, `[2, 0, 1]` and `[2, 1, 0]`, and the smallest is `[1, 2, 0]`. Task 0 cannot come first even though it has the smallest label. **Example 3** ```text Input: n = 3, dependencies = [[0, 1], [1, 2], [2, 0]] Output: [] ``` Each of the three tasks must come before the next one around a cycle, so no order satisfies all three pairs.

Overview: Given a number of tasks and dependency pairs, return the lexicographically smallest order that completes every task while respecting all dependencies, or an empty list when a cycle makes that impossible. Tests topological sorting, cycle detection and deterministic tie-breaking on large dependency graphs.

A project consists of `n` tasks labeled `0` to `n - 1`, done one at a time. Some tasks depend on others: a dependency pair `[a, b]` means task `a` must be finished before task `b` can start. Implement `task_order(n, dependencies)`, which returns an order in which all `n` tasks can be done without violating any dependency. Several orders may be valid; return the lexicographically smallest one. If the dependencies make it impossible to finish every task, return an empty list. ### Rules - A valid order contains every task from `0` to `n - 1` exactly once, and for every pair `[a, b]`, task `a` appears before task `b`. - Order `x` is lexicographically smaller than order `y` if, at the first index where they differ, `x` has the smaller task label. - If no valid order exists because the dependencies contain a cycle, return `[]`. - The same pair may appear more than once; duplicates express the same constraint. ### Constraints - `1 <= n <= 10^5` - `0 <= len(dependencies) <= 2 * 10^5` - Each `dependencies[i]` has exactly two elements `[a, b]` - `0 <= a <= n - 1`, `0 <= b <= n - 1`, and `a != b` - Every label and length fits in a 32-bit signed integer; no value exceeds 2^31 - 1. ### Example 1 ```text Input: n = 4, dependencies = [[1, 0], [2, 0], [3, 1], [3, 2]] Output: [3, 1, 2, 0] ``` Task 3 must precede tasks 1 and 2, and both of those must precede task 0. The valid orders are `[3, 1, 2, 0]` and `[3, 2, 1, 0]`; the first is lexicographically smaller. ### Example 2 ```text Input: n = 3, dependencies = [[2, 0]] Output: [1, 2, 0] ``` Task 2 must precede task 0, and task 1 is unconstrained. The valid orders are `[1, 2, 0]`, `[2, 0, 1]` and `[2, 1, 0]`, and the smallest is `[1, 2, 0]`. Task 0 cannot come first even though it has the smallest label.

Constraints

1 <= n <= 10^5
0 <= len(dependencies) <= 2 * 10^5
Each dependencies[i] has exactly two elements [a, b]
0 <= a <= n - 1, 0 <= b <= n - 1, and a != b
The same pair may appear more than once; duplicates express the same constraint
Every label and length fits in a 32-bit signed integer

Examples

Input: (4, [[1, 0], [2, 0], [3, 1], [3, 2]])

Expected Output: [3, 1, 2, 0]

Explanation: Source Example 1: 3 first, then 1 before 2 by label, then 0. A DFS reverse-postorder gives the valid but larger [3, 2, 1, 0].

Input: (3, [[2, 0]])

Expected Output: [1, 2, 0]

Explanation: Source Example 2: task 0 is blocked by the larger label 2, so the smallest available task 1 goes first; sorting labels or picking 0 first is wrong.

Hints

Lexicographic comparison is decided at the first differing index, so making an earlier position smaller always matters more than anything that comes after it.
At any moment only some tasks are allowed to go next. Ask which of them should take the current position, and how to keep finding that task quickly as the allowed set changes.
If tasks remain but none of them is allowed to go next, think about what the remaining dependencies must contain. Also check that a repeated pair cannot leave a task waiting forever.

Approach

Algorithm: Kahn's topological sort driven by a min-heap instead of a FIFO queue. Build the successor lists and count each task's in-degree, counting every occurrence of a pair. Push every task with in-degree 0 into a min-heap. Repeatedly pop the smallest label, append it to the answer, and decrement the in-degree of each successor, pushing a successor once its in-degree reaches 0. If fewer than n tasks were placed, return [].

Invariant: the heap always holds exactly the unplaced tasks whose prerequisites have all been placed, that is, the tasks that may legally occupy the next position.

Correctness: lexicographic order is decided at the first index where two orders differ, so the answer must put the smallest legal task at each position, provided the remaining tasks can still be completed. Any task in the heap is legal next, and in an acyclic graph the remaining tasks always admit a valid completion, so placing the smallest available label never blocks the rest. By induction over positions, the greedy order matches the lexicographically smallest valid order at every index. If the heap empties while tasks remain, every remaining task waits on another remaining task. Following those prerequisites backwards must revisit a task, so there is a cycle, no valid order exists, and the function returns [].

Edge cases: n = 1 returns [0]. With no dependencies the answer is the identity order. A repeated pair raises the in-degree and later lowers it by the same amount, so it never leaves a task blocked. A cycle confined to one component still yields [] rather than a partial order. A FIFO queue or a DFS postorder produces a valid order that is not necessarily the smallest.

Time complexity:

O((n + m) log n), where m = len(dependencies)

Space complexity:

O(n + m)