Build Array from Permutation
What is zerobased permutation ?
A zerobased 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 zerobased permutation of length n
is a unique arrangement of all integers from 0
to n1
.
For instance, if you have an array of length 5, a zerobased 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:


Let’s break it down:
range(len(nums))
: This generates a sequence of indices for our listnums
.nums[nums[i]]
: For each indexi
, we find the value atnums[i]
, which is another index innums
. We then use this index to find the corresponding value innums
.[nums[nums[i]] for i in range(len(nums))]
: We use list comprehension to apply the operation to each index innums
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:
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.
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.