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.lengthnums are distinct.
Follow-up: Can you solve it without using an extra space (i.e., O(1) memory)?
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.
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]].
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.
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.
Time Complexity: O(n) because of two linear passes over the array.
Space Complexity: O(1) as no additional space is used.
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).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C
| 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 | — |
| 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 |
1920. Build Array from Permutation | Zero to FAANG Kunal | Assignment Solution | Leetcode | Shapnesh • Programmers Zone • 19,835 views views
Watch 9 more video solutions →Practice Build Array from Permutation with our built-in code editor and test cases.
Practice on FleetCode