The earliest valid task order

Graphs Mid-level Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

import heapq
rules = [[2, 0], [2, 1], [0, 3]]
after: dict[int, list[int]] = {i: [] for i in range(4)}
waiting = [0] * 4
for a, b in rules:
    after[a].append(b)
    waiting[b] += 1
ready = [t for t in range(4) if waiting[t] == 0]
heapq.heapify(ready)
order = []
while ready:
    t = heapq.heappop(ready)
    order.append(t)
    for nxt in after[t]:
        waiting[nxt] -= 1
        if waiting[nxt] == 0:
            heapq.heappush(ready, nxt)
print(order)

Options[2, 0, 1, 3][0, 1, 2, 3][2, 0, 3, 1]

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [2, 0, 1, 3]

Right: only 2 is free at first; then 0 is smaller than 1, and 0 frees 3.

At every step the heap hands back the smallest ready task, which builds the smallest valid order.

Why not the others?

B [0, 1, 2, 3]. 0 and 1 both wait for 2.
C [2, 0, 3, 1]. After 0, both 1 and 3 are ready, and 1 is smaller.

30-second answer

Kahn's algorithm with a min-heap instead of a queue: among the tasks that are currently unblocked, always take the smallest number. That choice is safe because taking any other ready task first would make the order larger at this position. O((V + E) log V) time and O(V + E) space.

Practise saying it · 45 s. No recording, just a timer

Explain the smallest topological order.

Say your answer out loud, then check which of these points you covered:

Kahn with a min-heap
Greedy choice is safe
Empty list on a cycle

Deep dive

With a plain queue you get some valid order; the heap picks the smallest one deterministically.

If the result is shorter than n, the rules contain a cycle; return [] as agreed.

Deterministic output makes the function easy to test, which is worth saying.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

import heapq


def earliest_order(n: int, rules: list[list[int]]) -> list[int]:
    after: list[list[int]] = [[] for _ in range(n)]
    waiting = [0] * n
    for before, task in rules:
        after[before].append(task)
        waiting[task] += 1
    ready = [t for t in range(n) if waiting[t] == 0]
    heapq.heapify(ready)
    order = []
    while ready:
        t = heapq.heappop(ready)
        order.append(t)
        for nxt in after[t]:
            waiting[nxt] -= 1
            if waiting[nxt] == 0:
                heapq.heappush(ready, nxt)
    return order if len(order) == n else []

Common mistakes

Sorting the tasks first and then running a queue-based Kahn, which does not guarantee the smallest order.
Returning a partial order when there is a cycle.

Senior take & follow-ups

Explain why the greedy choice of the smallest ready task is safe.

Follow-up questions

Think of your answer first, then open the hint.

How would you count all valid orders?
Show hint
Backtracking over ready tasks, or DP over subsets for small n.
What if each task has a duration and many can run at once?
Show hint
Track earliest start times: longest path in the DAG.

What each operation costs: Breadth First Search · Depth First Search · Topological Sort · Dijkstra Algorithm

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.