Build Array from Permutation - Solution & Explanation
Problem Statement
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.
The function buildArray takes an array nums and its size, and directly constructs the array ans by iterating over each element. For each index i, it sets ans[i] to nums[nums[i]].
Complexity
Time Complexity: O(n) because we iterate through the array once.
Space Complexity: O(n) since we use an extra array of the same length.
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.
This solution encodes both old and new numbers inside each original array element. Using the formula nums[i] = nums[i] + n * (nums[nums[i]] % n), each element is divided by n in a second pass to extract the transformed values.
Complexity
Time Complexity: O(n) because of two linear passes over the array.
Space Complexity: O(1) as no additional space is used.
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).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C
Complexity Comparison
| Approach | Complexity |
|---|---|
| Naive Approach using Extra Array | Time Complexity: O(n) because we iterate through the array once. |
| In-Place Encoding without Extra Space | Time Complexity: O(n) because of two linear passes over the array. |
| Simulation | — |
Detailed 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 |
Video Solution
Build Array from Permutation | Leetcode solutions - 1920 • Algorithms Made Easy • 16,029 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Build Array from Permutation easy or hard?
Build Array from Permutation Python/Java solution
How to solve Build Array from Permutation in O(n)?
What is the best approach for Build Array from Permutation?
Is Build Array from Permutation asked at Google/Amazon/Meta?
What data structure is used in Build Array from Permutation?
What is the time complexity of Build Array from Permutation?
Ready to solve this problem?
Practice Build Array from Permutation with our built-in code editor and test cases.
Practice on FleetCode