Reverse Every Arrow
EasyGraphs
Problem
A build system has n packages numbered 0 to n - 1. Each entry [u, v] of arrows means package u points to package v. No arrow is listed twice.
Build a reversed copy of the graph as adjacency lists: entry v of the result lists, in ascending order, every package u such that [u, v] is an arrow.
Example 1
- Input:
- n = 3, arrows = [[0, 1], [0, 2], [1, 2]]
- Output:
- [[], [0], [0, 1]]
Only 0 points to 1; both 0 and 1 point to 2.
Example 2
- Input:
- n = 4, arrows = [[3, 0], [2, 0], [1, 0]]
- Output:
- [[1, 2, 3], [], [], []]
Example 3
- Input:
- n = 2, arrows = []
- Output:
- [[], []]
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ arrows.length ≤ 2·10^5
- 0 ≤ u, v < n
Hint
Show the first hint
Reversing an arrow [u, v] means u must be listed under v.
Walkthrough
How to approach it
01Clarify before coding
- Can an arrow point from a package to itself? Yes; it stays a self-arrow.
- Must each list be sorted? Yes, ascending.
- Are packages without incoming arrows included? Yes, with an empty list.
02Brute force
For each package v, scan all arrows and collect every u with target v, then sort.
Cost: O(n · m): 2·10^10 steps 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.