Build Array From Permutation - Leetcode Solution

Problem: Given a zero-based permutation nums, 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).

Solution: To solve this problem, we need to iterate over the given permutation array nums and create a new array ans such that ans[i] = nums[nums[i]] for each i from 0 to nums.length - 1.

Algorithm:

1. Initialize an empty array ans of the same length as nums.
2. Iterate over nums from 0 to n-1 and set ans[i] = nums[nums[i]].

Let's look at the implementation of this algorithm in Python:

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

In the above code, we first initialized an empty array ans of the same length as nums, and then we iterated over nums from 0 to n-1 and set ans[i] = nums[nums[i]].

Time Complexity: O(n) Space Complexity: O(n)

Let's look at an example to understand this solution better:

Example: nums = [0, 2, 1, 5, 3, 4] n = 6

Initially, ans = [0, 0, 0, 0, 0, 0]

At i = 0, ans[0] = nums[nums[0]] = nums[0] = 0, ans = [0, 0, 0, 0, 0, 0] At i = 1, ans[1] = nums[nums[1]] = nums[1] = 1, ans = [0, 1, 0, 0, 0, 0] At i = 2, ans[2] = nums[nums[2]] = nums[2] = 2, ans = [0, 1, 2, 0, 0, 0] At i = 3, ans[3] = nums[nums[3]] = nums[4] = 3, ans = [0, 1, 2, 3, 0, 0] At i = 4, ans[4] = nums[nums[4]] = nums[3] = 5, ans = [0, 1, 2, 3, 5, 0] At i = 5, ans[5] = nums[nums[5]] = nums[5] = 4, ans = [0, 1, 2, 3, 5, 4]

Hence the final output is [0, 1, 2, 3, 5, 4].

1