Build Array from Permutation

Easy
191.

Build Array from Permutation

EasyArraySimulationAmazonMicrosoft

Build Array from Permutation is an easy coding problem on arrays and simulation, asked in Amazon and Microsoft interviews.

Given a zero-based permutation nums, build an array ans of the same length where ans[i] = nums[nums[i]], and return it.

A zero-based permutation of length n contains every number from 0 to n - 1 exactly once.

Example 1

Input
nums = [0,2,1,5,3,4]
Output
[0,1,2,4,5,3]
Explanation
ans[1] = nums[nums[1]] = nums[2] = 1.

Example 2

Input
nums = [5,0,1,2,3,4]
Output
[4,5,0,1,2,3]

Example 3

Input
nums = [0]
Output
[0]

Constraints

  • 1 <= nums.length <= 40
  • 0 <= nums[i] < nums.length
  • nums is a permutation.

Follow-up: Can you build the answer in place, in O(1) extra space?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var buildArray = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

Build Array from Permutation — Problem & Solution

Build Array from Permutation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Build Array from Permutation is an easy coding problem on arrays and simulation, asked in Amazon and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Arrays, Simulation
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a zero-based permutation nums, build an array ans of the same length where ans[i] = nums[nums[i]], and return it.

A zero-based permutation of length n contains every number from 0 to n - 1 exactly once.

Example 1

Input: nums = [0,2,1,5,3,4]
Output: [0,1,2,4,5,3]
Explanation: ans[1] = nums[nums[1]] = nums[2] = 1.

Example 2

Input: nums = [5,0,1,2,3,4]
Output: [4,5,0,1,2,3]

Example 3

Input: nums = [0]
Output: [0]

Constraints

  • 1 <= nums.length <= 40
  • 0 <= nums[i] < nums.length
  • nums is a permutation.

Follow-up: Can you build the answer in place, in O(1) extra space?

Hints for Build Array from Permutation

  1. Hint 1

    Read nums[i], then use that as an index back into nums — a double lookup per position.

  2. Hint 2

    Do not overwrite as you go unless you encode both values in one slot; the later reads need the original array.

  3. Hint 3

    The in-place trick stores old + n * new in each slot and divides by n in a second pass.

How to solve Build Array from Permutation

Each output is a double lookup: ans[i] = nums[nums[i]].

Approach

  1. For each i, read nums[i] and use it as an index back into nums.

Why it works

Because nums is a permutation, nums[i] is always a valid index, and reading from the original array keeps every lookup correct.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Overwriting nums while iterating corrupts later reads; the in-place trick stores old + n·new and divides out in a second pass.

Reference solution

Python

def buildArray(nums):
    return [nums[nums[i]] for i in range(len(nums))]

Java

public static int[] buildArray(int[] nums) {
    int[] out = new int[nums.length];
    for (int i = 0; i < nums.length; i++) out[i] = nums[nums[i]];
    return out;
}

C++

vector<int> buildArray(vector<int>& nums) {
    vector<int> out;
    for (size_t i = 0; i < nums.size(); i++) out.push_back(nums[nums[i]]);
    return out;
}

JavaScript

var buildArray = function(nums) {
    const out = [];
    for (let i = 0; i < nums.length; i++) out.push(nums[nums[i]]);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays