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.
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; }}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.