Tasks Ready on Day One
EasyGraphs
Problem
A project has n tasks numbered 0 to n - 1. Each entry [a, b] of deps means task a must be finished before task b can begin.
Return, in ascending order, every task that can be started immediately because nothing has to come before it.
Example 1
- Input:
- n = 5, deps = [[0, 2], [1, 2], [2, 3]]
- Output:
- [0, 1, 4]
Tasks 2 and 3 wait on other tasks; 0, 1 and 4 wait on nothing.
Example 2
- Input:
- n = 3, deps = [[0, 1], [1, 2], [2, 0]]
- Output:
- []
Every task waits on another one, so nothing can start.
Example 3
- Input:
- n = 3, deps = []
- Output:
- [0, 1, 2]
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ deps.length ≤ 2·10^5
- 0 ≤ a, b < n
- Dependencies may repeat; a = b means a task waits on itself.
Hint
Show the first hint
Which part of a dependency [a, b] tells you that a task is blocked?
Walkthrough
How to approach it
01Clarify before coding
- Does [a, b] block a or b? It blocks b: a must come first.
- Should a task in a cycle be reported? No: it has a prerequisite, so it cannot start immediately.
- What order should the output use? Ascending task number.
02Brute force
For each task t, scan the whole dependency list looking for an entry whose second element is t.
Cost: O(n·m): 2·10^10 checks at the limits.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.