Build Array from Permutation
EasyPrompt
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)?
Approaches
2 approaches with complexity analysis and trade-offs.
This is a straightforward approach where we create a new array to store the results. We iterate through the input array nums, and for each index i, we calculate nums[nums[i]] and place it into the corresponding index of the new array.
Algorithm
- Get the length of
nums, let's call itn. - Create a new integer array
ansof sizen. - Iterate with an index
ifrom0ton-1. - Inside the loop, calculate
nums[nums[i]]. - Assign this result to
ans[i]. - After the loop, return the
ansarray.
Walkthrough
The problem asks us to build an array ans where ans[i] = nums[nums[i]]. The most direct way to achieve this is to allocate a new array, say ans, with the same length as nums.
We then loop from i = 0 to nums.length - 1. In each iteration, we compute the value nums[nums[i]]. Note that since we are reading from the original, unmodified nums array and writing to the new ans array, we don't have to worry about overwriting values that are needed for later calculations.
The computed value is then assigned to ans[i]. After the loop finishes, the ans array will contain all the required values, and we can return it.
class Solution { public int[] buildArray(int[] nums) { int n = nums.length; int[] ans = new int[n]; for (int i = 0; i < n; i++) { ans[i] = nums[nums[i]]; } return ans; }}Complexity
Time
O(n), where n is the length of the `nums` array. We iterate through the array once to build the `ans` array.
Space
O(n), as we use an extra array `ans` of the same size as the input array to store the results.
Trade-offs
Pros
Very simple and easy to understand.
The logic directly translates the problem statement into code.
Cons
Uses extra space, which might not be desirable for large inputs or strict memory constraints.
Does not satisfy the follow-up requirement of an O(1) space solution.
This approach solves the problem without using any extra space, fulfilling the follow-up requirement. The key idea is to store two values (the original and the new value) at each array index simultaneously. This is achieved by using a mathematical encoding/decoding scheme. We iterate through the array twice: once to encode the new values and a second time to decode them into the final result.
Algorithm
- Encoding Pass: Iterate through
numsfromi = 0ton-1.- For each index
i, the original value isa = nums[i]. The new value we want to store isb = nums[nums[i]]. - However, the value at
nums[nums[i]]might have already been encoded from a previous step. To get its original value, we computenums[nums[i]] % n. - So, the new value for index
iisb = nums[nums[i]] % n. - We update
nums[i]to store both its original value and this new value:nums[i] = nums[i] + n * b.
- For each index
- Decoding Pass: Iterate through
numsagain fromi = 0ton-1.- Each
nums[i]now holds an encoded valueoriginal_value + n * new_value. - To get the final result, we just need the
new_value, which can be extracted by integer division:nums[i] = nums[i] / n.
- Each
Walkthrough
To solve the problem in O(1) space, we must modify the input array nums in-place. A naive in-place update like nums[i] = nums[nums[i]] would fail because it might overwrite an original value that is needed for a later calculation.
The trick is to store both the original value and the new value at each index i. Since all numbers in nums are in the range [0, n-1], we can use the formula a + n * b to store two numbers a and b (both less than n) in a single integer. Here, a can be retrieved by (a + n*b) % n, and b can be retrieved by (a + n*b) / n.
The algorithm proceeds in two passes as described above. After the second pass, nums will be transformed into the desired output array.
class Solution { public int[] buildArray(int[] nums) { int n = nums.length; // Encode the result in each number // nums[i] = old_val + n * new_val for (int i = 0; i < n; i++) { // new_val is the original value at nums[nums[i]] // which can be retrieved by nums[nums[i]] % n nums[i] = nums[i] + n * (nums[nums[i]] % n); } // Decode the result for (int i = 0; i < n; i++) { nums[i] = nums[i] / n; } return nums; }}Complexity
Time
O(n), where n is the length of the array. We perform two separate passes over the array, which results in O(n) + O(n) = O(2n), which simplifies to O(n).
Space
O(1), as we modify the array in-place and do not use any additional data structures that scale with the input size.
Trade-offs
Pros
Highly space-efficient, meeting the O(1) space complexity requirement.
An elegant solution that demonstrates a useful encoding trick.
Cons
The logic is more complex and less intuitive than the extra-space approach.
It modifies the input array, which might not be permissible in all contexts.
Solutions
Solution
class Solution {public 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; }}/** * @param {number[]} nums * @return {number[]} */ var buildArray = function ( nums,) { let ans = []; for (let i = 0; i < nums.length; ++i) { ans[i] = nums[nums[i]]; } return ans;};class Solution {public: vector<int> buildArray(vector<int> &nums) { vector<int> ans; for (int &num : nums) { ans.push_back(nums[num]); } return ans; }};class Solution: def buildArray( self, nums: List[int]) -> List[int]: return [nums[num] for num in nums]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.