Follow the Index Table
MediumArrays & Hashing
Problem
A routing table table is a permutation of 0..n-1: from slot i a packet jumps to slot table[i]. The network team wants the two-hop table, where slot i holds table[table[i]] computed from the original table.
Transform table in place using O(1) extra space. The function returns nothing.
Example 1
- Input:
- table = [0, 2, 1, 5, 3, 4]
- Output:
- [0, 1, 2, 4, 5, 3]
Slot 3: table[3] = 5, then table[5] = 4.
Example 2
- Input:
- table = [5, 0, 1, 2, 3, 4]
- Output:
- [4, 5, 0, 1, 2, 3]
Constraints
- 1 ≤ n ≤ 10^5
- table is a permutation of 0..n-1.
- O(1) extra space.
Hint
Show the first hint
Overwriting table[i] directly destroys a value that another slot may still need to read.
Walkthrough
How to approach it
01Clarify before coding
- Is it really a permutation? Yes, every value 0..n-1 appears exactly once.
- Is a copy of the array allowed? No, O(1) extra space.
- Is overflow a concern? Values reach at most n², about 10^10: fine in Python and in JavaScript numbers, but would need 64-bit integers in Java/C++.
02Brute force
Copy the table and write result[i] = copy[copy[i]].
Cost: O(n) time but O(n) extra space, which the problem forbids.
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.