#1920
Build Array from Permutation
Easy Index mapping
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Given a permutation nums of 0..n-1, return ans where ans[i] = nums[nums[i]].
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: ans[i] = nums[nums[i]] — follow the pointer once.
Why this works: the simple version builds a new array. The in-place version stores two values in one slot (old + n × new), then divides by n.
Example: nums = [0, 2, 1, 5, 3, 4]
i=0: nums[0]=0 → nums[0]=0i=1: nums[1]=2 → nums[2]=1i=3: nums[3]=5 → nums[5]=4ans = [0, 1, 2, 4, 5, 3]
✦Hints open one at a time
The direct version is a one-line loop with a new array.
Follow-up: to do it in place, store two values in one slot: old + n × new.
↗Approach
The simple answer builds a new array. The in-place version writes nums[i] += n * (nums[nums[i]] % n) — the % n recovers the old value even after a slot was updated — then divides every slot by n.
</>Solution (Java)
class Solution {
public int[] buildArray(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
nums[i] += n * (nums[nums[i]] % n); // pack new value on top of the old one
}
for (int i = 0; i < n; i++) nums[i] /= n; // keep only the new value
return nums;
}
}!Common mistake
Doing the in-place update without % n, which reads already-modified values.
Complexity
- Time: O(n).
- Space: O(1) extra for the in-place version.
Topic: Arrays
