Build Array from Permutation

Difficulty: Easy | Acceptance: 91.10% | Paid: No Topics: Array, Simulation

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. Return the constructed array ans.

A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).

• Examples
• Constraints
• Direct Simulation
• In-Place Encoding

Examples

Example 1:

Input: nums = [0,2,1,5,3,4]
Output: [0,1,2,4,5,3]
Explanation: 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: 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 <= 1000
0 <= nums[i] < nums.length
All integers in nums are unique.

Direct Simulation

Intuition The problem statement directly defines the relationship between the input array nums and the output array ans. We can simply iterate through the indices of nums and apply the formula ans[i] = nums[nums[i]] to fill a new array.

Steps

• Initialize a new array ans with the same length as nums.
• Iterate through each index i from 0 to n-1.
• For each index i, assign ans[i] the value of nums[nums[i]].
• Return the array ans.

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        for i in range(n):
            ans[i] = nums[nums[i]]
        return ans

Complexity

• Time: O(n) — We iterate through the array once.
• Space: O(n) — We allocate a new array of size n to store the result.
• Notes: This is the most straightforward and readable solution.

In-Place Encoding

Intuition We can optimize space complexity by modifying the input array in place to store both the original value and the new value. Since 0 <= nums[i] < n, we can use the formula nums[i] = nums[i] + (nums[nums[i]] % n) * n to encode the new value. Later, we can retrieve the new value by dividing by n.

Steps

• Get the length n of the array.
• Iterate through the array. For each index i, update nums[i] to nums[i] + (nums[nums[i]] % n) * n. The modulo operation ensures we retrieve the original value at nums[nums[i]] even if it has been modified.
• Iterate through the array again. For each index i, update nums[i] to nums[i] / n (integer division). This extracts the new value.
• Return nums.

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(n):
            nums[i] = nums[i] + (nums[nums[i]] % n) * n
        for i in range(n):
            nums[i] = nums[i] // n
        return nums

Complexity

• Time: O(n) — We iterate through the array twice.
• Space: O(1) — We modify the array in place and use only a constant amount of extra space.
• Notes: This approach trades some readability for constant space complexity. It is useful when memory is extremely constrained.