Build Array from Permutation

1. Define the problem

Given a zero-based permutation nums (each value from 0 to nums.length - 1 appears exactly once), build a new array ans of the same length where ans_i = nums[nums_i] . Return the array ans, computing each position by using nums itself as a lookup table , twice in a row.

Constraints

1 ≤ nums.length ≤ 1000
0 ≤ nums_i < nums.length
The elements in nums are distinct

Example

Inputnums = [0, 2, 1, 5, 3, 4]

Output[0, 1, 2, 4, 5, 3]

Explanation ans₀ = nums[nums₀] = nums₀ = 0, ans₁ = nums[nums₁] = nums₂ = 1, and so on.

2. Know the words first

In plain terms

Lookup table: A collection where you use a value as a position to instantly find another value, instead of searching for it.

3. Visualize the solution

Look up nums[i] then look that result up again in nums

Statusinit

i=1: nums[1]=2, then nums[2]=1. ans[1]=1.

What happens in this step

i = 1
nums[1] = 2
nums[nums[1]] = nums[2] = 1
ans[1] = 1

Step 1 of 4

Steps to visualize

For each index i, first read the value nums_i.
Use that value as a new index back into nums to get nums[nums_i].
Store that result at ans_i.
Repeat for every index to build the full ans array.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Look up nums[i] then look that result up again in nums

Statusinit

i=1: nums[1]=2, then nums[2]=1. ans[1]=1.

What happens in this step

i = 1
nums[1] = 2
nums[nums[1]] = nums[2] = 1
ans[1] = 1

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function buildArray(nums) {
  const ans = new Array(nums.length);

  for (let i = 0; i < nums.length; i++) {
    ans[i] = nums[nums[i]];
  }

  return ans;
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [0, 2, 1, 5, 3, 4]`	`[0, 1, 2, 4, 5, 3]`	example from the docstring
`nums = [5, 0, 1, 2, 3, 4]`	`[4, 5, 0, 1, 2, 3]`	a rotated permutation
`nums = [0]`	`[0]`	smallest valid input, a single element mapping to itself
`nums = [1, 0]`	`[0, 1]`	boundary case, exactly two elements swapped
`nums = [0, 1, 2, 3]`	`[0, 1, 2, 3]`	the identity permutation, every value maps to itself
`nums = [3, 2, 1, 0]`	`[0, 1, 2, 3]`	a fully reversed permutation

Build Array from Permutation