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)?
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]].
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) because of two linear passes over the array.
Space Complexity: O(1) as no additional space is used.
| 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. |
Build Array from Permutation | Leetcode solutions - 1920 • Algorithms Made Easy • 12,816 views views
Watch 9 more video solutions →Practice Build Array from Permutation with our built-in code editor and test cases.
Practice on FleetCode