Build Array from Permutation solution and explanation
Google
9 more videos on this problem
Build Array from Permutation | Leetcode solutions - 1920Algorithms Made Easy · 19:12 · 16K views
Build Array from Permutation | O(n) Space solution | Leetcode 1920 | O(1) link in DescriptionCodeClips with Abhishek Ranjan · 8:00 · 10K views
Build Array from Permutation | Follow Up Qn | Detailed Explanation | Leetcode 1920 |codestorywithMIKcodestorywithMIK · 25:13 · 6K views
LeetCode- Build Array from PermutationCode Tech Gyan · 7:22 · 4K views
Build Array from Permutation | LeetCode 1920 | C++Knowledge Center · 5:03 · 3K views
LEETCODE SOLUTION 1920 | Build Array from Permutation| Leetcode for BEGINNERS | EASY | JavascriptCodingForBeginners · 4:57 · 2K views
Leetcode 1920 - Build Array From Permutation | Solution ✅Brainstorming Code · 8:53 · 1K views
LeetCode 1920 : Build Array from Permutation | Solution in Java and C++Amit Manjarly · 6:33 · 642 views
1920. Build Array from Permutation | Leetcode Daily - PythonLeetcode Daily · 11:30 · 379 views
LeetCode 1920 | Build Array from Permutation | Easy Explanation | LeetCode SolutionsCODE WITH PUSHPRAJ · 9:31 · 306 views
The problem
Given a zero-based permutation nums (0-indexed), build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.
A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).
Example 1:
Input: nums = [0,2,1,5,3,4]
Output: [0,1,2,4,5,3]
Explanation: The array ans is built as follows:
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
= [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
= [0,1,2,4,5,3]
Example 2:
Input: nums = [5,0,1,2,3,4]
Output: [4,5,0,1,2,3]
Explanation: The array ans is built as follows:
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
= [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]
= [4,5,0,1,2,3]
Constraints:
1 <= nums.length <= 10000 <= nums[i] < nums.length- The elements in
numsare distinct.
Follow-up: Can you solve it without using an extra space (i.e., O(1) memory)?
Approach overview
Problem Overview: You receive a zero-indexed permutation array nums. Build a new array ans such that ans[i] = nums[nums[i]]. Every value in nums appears exactly once, which guarantees all indices are valid.
Approach 1: Naive Simulation using Extra Array (Time: O(n), Space: O(n))
Create a new array ans with the same length as nums. Iterate from i = 0 to n - 1, and directly assign ans[i] = nums[nums[i]]. This works because nums is a permutation, so every value is a valid index. The method is straightforward and mirrors the problem statement exactly. Most developers implement this first because it is easy to reason about and avoids modifying the input array.
This approach relies only on sequential iteration over the array and simple indexing operations. It runs in linear time since each element is processed once, but it allocates an additional array of size n.
Approach 2: In-Place Encoding without Extra Space (Time: O(n), Space: O(1))
The key insight is that both the old value and the new value can be stored in the same index using mathematical encoding. Since every value in the permutation is in the range [0, n-1], you can temporarily encode the new value into the existing element using nums[i] += n * (nums[nums[i]] % n). The modulo operation retrieves the original value even if it has already been encoded.
After this first pass, each element stores both values: the original value and the encoded target value. A second pass divides every element by n to extract the final result. This method keeps everything inside the same array and avoids extra memory. The logic is a classic simulation trick combined with index encoding.
Recommended for interviews: Start with the extra array solution because it shows clear understanding of the problem and achieves optimal O(n) time. Follow up with the in-place encoding optimization if the interviewer asks about reducing memory usage. Demonstrating the encoding trick shows stronger array manipulation skills and awareness of space optimization techniques.
Approach 1: Naive Approach using Extra Array
The simplest approach is to create a new array to store the result. For each element nums[i], simply set ans[i] to nums[nums[i]]. This approach is straightforward and utilizes an extra array with the same length as the input array.
def build_array(nums):
return [nums[nums[i]] for i in range(len(nums))]
nums = [0, 2, 1, 5, 3, 4]
ans = build_array(nums)
print(ans)import java.util.Arrays;
public class Main {
public static int[] buildArray(int[] nums) {
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
ans[i] = nums[nums[i]];
}
return ans;
}
public static void main(String[] args) {
int[] nums = {0, 2, 1, 5, 3, 4};
System.out.println(Arrays.toString(buildArray(nums)));
}
}#include <vector>
#include <iostream>
std::vector<int> buildArray(const std::vector<int>& nums) {
std::vector<int> ans(nums.size());
for (int i = 0; i < nums.size(); ++i) {
ans[i] = nums[nums[i]];
}
return ans;
}
int main() {
std::vector<int> nums = {0, 2, 1, 5, 3, 4};
std::vector<int> ans = buildArray(nums);
for (int i : ans) {
std::cout << i << " ";
}
return 0;
}function buildArray(nums) {
let ans = new Array(nums.length);
for (let i = 0; i < nums.length; i++) {
ans[i] = nums[nums[i]];
}
return ans;
}
let nums = [0, 2, 1, 5, 3, 4];
let ans = buildArray(nums);
console.log(ans);#include <stdio.h>
void buildArray(int* nums, int numsSize, int* ans) {
for (int i = 0; i < numsSize; i++) {
ans[i] = nums[nums[i]];
}
}
int main() {
int nums[] = {0, 2, 1, 5, 3, 4};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int ans[numsSize];
buildArray(nums, numsSize, ans);
for (int i = 0; i < numsSize; i++) {
printf("%d ", ans[i]);
}
return 0;
}using System;
public class Program {
public static int[] BuildArray(int[] nums) {
int[] ans = new int[nums.Length];
for (int i = 0; i < nums.Length; i++) {
ans[i] = nums[nums[i]];
}
return ans;
}
public static void Main() {
int[] nums = {0, 2, 1, 5, 3, 4};
int[] ans = BuildArray(nums);
Console.WriteLine(string.Join(" ", ans));
}
}The function build_array uses a list comprehension to generate the ans array. It iterates over each index i, assigning nums[nums[i]] to the result list.
Time Complexity: O(n) due to a single pass over the list.
Space Complexity: O(n) as a new list is created for results.
Approach 2: In-Place Encoding without Extra Space
This approach hinges on encoding two numbers into each indexed position in nums itself. This is possible by exploiting the fact that both numbers to be encoded are in a limited range (0 to n-1). For each index i, we store the old value and the new value in a single integer using a formula based on modular arithmetic.
def build_array_in_place(nums):
n = len(nums)
for i in range(n):
nums[i] = nums[i] + n * (nums[nums[i]] % n)
for i in range(n):
nums[i] //= n
nums = [0, 2, 1, 5, 3, 4]
build_array_in_place(nums)
print(nums)public class Main {
public static void buildArrayInPlace(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
nums[i] = nums[i] + n * (nums[nums[i]] % n);
}
for (int i = 0; i < n; i++) {
nums[i] /= n;
}
}
public static void main(String[] args) {
int[] nums = {0, 2, 1, 5, 3, 4};
buildArrayInPlace(nums);
for (int num : nums) {
System.out.print(num + " ");
}
}
}#include <vector>
#include <iostream>
void buildArrayInPlace(std::vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
nums[i] += n * (nums[nums[i]] % n);
}
for (int i = 0; i < n; ++i) {
nums[i] /= n;
}
}
int main() {
std::vector<int> nums = {0, 2, 1, 5, 3, 4};
buildArrayInPlace(nums);
for (int num : nums) {
std::cout << num << " ";
}
return 0;
}function buildArrayInPlace(nums) {
let n = nums.length;
for (let i = 0; i < n; i++) {
nums[i] = nums[i] + n * (nums[nums[i]] % n);
}
for (let i = 0; i < n; i++) {
nums[i] = Math.floor(nums[i] / n);
}
}
let nums = [0, 2, 1, 5, 3, 4];
buildArrayInPlace(nums);
console.log(nums);#include <stdio.h>
void buildArrayInPlace(int* nums, int numsSize) {
for (int i = 0; i < numsSize; i++) {
nums[i] = nums[i] + numsSize * (nums[nums[i]] % numsSize);
}
for (int i = 0; i < numsSize; i++) {
nums[i] /= numsSize;
}
}
int main() {
int nums[] = {0, 2, 1, 5, 3, 4};
int numsSize = sizeof(nums) / sizeof(nums[0]);
buildArrayInPlace(nums, numsSize);
for (int i = 0; i < numsSize; i++) {
printf("%d ", nums[i]);
}
return 0;
}using System;
public class Program {
public static void BuildArrayInPlace(int[] nums) {
int n = nums.Length;
for (int i = 0; i < n; i++) {
nums[i] += n * (nums[nums[i]] % n);
}
for (int i = 0; i < n; i++) {
nums[i] /= n;
}
}
public static void Main() {
int[] nums = {0, 2, 1, 5, 3, 4};
BuildArrayInPlace(nums);
Console.WriteLine(string.Join(" ", nums));
}
}In this in-place Python method, we encode information using the range limit of indices, performing two separate steps to simultaneously transform and retrieve transformed data.
Time Complexity: O(n) thanks to the twofold access across the elements.
Space Complexity: O(1) due to in-place manipulation.
Approach 3: Simulation
We can directly simulate the process described in the problem by constructing a new array ans. For each i, let ans[i] = nums[nums[i]].
The time complexity is O(n), where n is the length of the array nums. Ignoring the space consumption of the answer array, the space complexity is O(1).
function buildArray(nums: number[]): number[] {
return nums.map(x => nums[x]);
}func buildArray(nums []int) []int {
ans := make([]int, len(nums))
for i, num := range nums {
ans[i] = nums[num]
}
return ans
}impl Solution {
pub fn build_array(nums: Vec<i32>) -> Vec<i32> {
nums.iter().map(|&v| nums[v as usize]).collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Approach using Extra Array | Time Complexity: O(n) due to a single pass over the list. |
| In-Place Encoding without Extra Space | Time Complexity: O(n) thanks to the twofold access across the elements. |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Extra Array Simulation | O(n) | O(n) | Best for clarity and quick implementation in interviews or practice |
| In-Place Encoding Trick | O(n) | O(1) | When memory usage must be minimized or interviewer asks for constant space |
Frequently asked questions
Is Build Array from Permutation easy or hard?
Build Array from Permutation is classified as an Easy problem. The main idea is simple array indexing, though the follow-up in-place encoding optimization introduces a slightly more advanced trick for achieving O(1) extra space.
Build Array from Permutation Python/Java solution
In Python or Java, iterate through nums and assign ans[i] = nums[nums[i]]. Python uses a list for ans, while Java typically creates an int array of size n. Both implementations run in O(n) time and are commonly accepted solutions on coding platforms.
How to solve Build Array from Permutation in O(n)?
Iterate through the array once and compute ans[i] = nums[nums[i]]. Because nums is a permutation containing values from 0 to n-1, every lookup is valid and constant time. This produces the result in linear time with either an auxiliary array or an in-place encoding trick.
What is the best approach for Build Array from Permutation?
The most practical approach uses a simple extra array and computes ans[i] = nums[nums[i]] while iterating once through the array. It runs in O(n) time with O(n) space and is easy to implement. For space optimization, an in-place encoding trick achieves the same O(n) time using O(1) extra space.
Is Build Array from Permutation asked at Google/Amazon/Meta?
Problems of this style appear frequently in interviews at large tech companies because they test indexing logic and array manipulation. While this exact problem is considered easy, similar permutation and array transformation questions are common at companies like Amazon and Google.
What data structure is used in Build Array from Permutation?
The problem primarily uses arrays with direct index access. The optimal logic relies on array indexing and sometimes modular arithmetic to encode two values inside the same array element for the in-place solution.
What is the time complexity of Build Array from Permutation?
Both common solutions run in O(n) time because each element is processed a constant number of times. The basic simulation uses one pass to fill a new array, while the in-place encoding method uses two linear passes but still totals O(n).