Build Array from Permutation | Leetcode solutions - 1920
Build Array from Permutation - Video Solution
Watch 10 video solutions for Build Array from Permutation, a easy level problem involving Array, Simulation. This walkthrough by Algorithms Made Easy has 16,029 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 |