Build Array from Permutation

What is zero-based permutation ?

A zero-based permutation of an array (or list) refers to an arrangement where the indices themselves are the elements of the array, and all indices from 0 to the length of the array minus one (inclusive) are present exactly once.

In simpler terms, a zero-based permutation of length n is a unique arrangement of all integers from 0 to n-1.

For instance, if you have an array of length 5, a zero-based permutation could be [3, 1, 4, 0, 2]. This is a permutation because every index from 0 to 4 appears in the array exactly once.

This problem can be solved by traversing the array and applying the given operation for each element at index i.

Here is the Python solution that uses a simple list comprehension:

1
2
3

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

Let’s break it down:

  1. range(len(nums)): This generates a sequence of indices for our list nums.

  2. nums[nums[i]]: For each index i, we find the value at nums[i], which is another index in nums. We then use this index to find the corresponding value in nums.

  3. [nums[nums[i]] for i in range(len(nums))]: We use list comprehension to apply the operation to each index in nums and collect the results in a new list. This list is our final result.

This solution traverses the array only once, so its time complexity is O(n), where n is the length of the input array. The space complexity is also O(n), as we create a new array to store the result.

This problem can be dissected into two key concepts or building blocks:

  1. Indexing: We need to understand how to correctly index elements in the list. Indexing is an essential part of Python and many other programming languages. The problem requires double indexing, where we use the value of an element as the index to another element.

  2. List Comprehension: The entire problem can be solved in a single line of Python code using list comprehension. This feature of Python enables us to succinctly create lists based on existing lists. In this problem, list comprehension can be used to create the new array where each element is determined by double indexing the original array.

Together, these two concepts form the building blocks of the solution to this problem.