---
###### tags: `Leetcode`
---
# Leetcode 1920. Build Array from Permutation

[link](https://leetcode.com/problems/build-array-from-permutation/)

---

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 <= 1000
- 0 <= nums[i] < nums.length
- The elements in nums are distinct.

---

題意: 給定一個陣列，建立一個相同長度的陣列ans，其中ans[i] = nums[nums[i]]

---

Iterate the array. For each item i, append nums[nums[i]] to the new array.

#### Solution 1

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

        return lst

O(T): O(n)
O(S): O(n)

---

Let’s assume an element is a and another element is b, both the elements are less than n. So if an element a is incremented by b*n, the element becomes a + b*n. So, when a + b*n is divided by n, the value is b and a + b*n % n is a.

#### Solution 2

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

        for i in range(n):
            nums[i] //= n

        return nums

O(T): O(n)
O(S): O(1)
reference: https://dev.to/vishnureddys/build-array-from-permutation-solution-to-leetcode-problem-357l