LeetCode
LeetCode 1920: Build Array from Permutation Solution in Python
An efficient Python solution using list comprehension, achieving linear time and space complexity.
The LeetCode 1920 problem requires us to create an array ans of the same length as the input array nums, which is a zero-based permutation. The value at each index i in ans should be determined by ans[i] = nums[nums[i]]. This operation is to be performed for each index i in the range 0 <= i < nums.length. The input nums is a permutation of distinct integers ranging from 0 to nums.length - 1, inclusive.
class Solution:
def buildArray(self, nums: List[int]) -> List[int]:
return [nums[nums[i]] for i in range(len(nums))]Understanding the Logic
The solution employs a list comprehension to iterate over the indices of the input array nums using for i in range(len(nums)). This iteration generates a sequence of numbers from 0 to the length of nums minus one, corresponding to each element’s index within nums. Within the list comprehension, nums[nums[i]] accesses the element at index i of nums, which itself is used as an index to access another element within the same array.
This double indexing follows the permutation specified by the input array to construct the output array. Each element at index i in the output array is determined by the value of nums at the index specified by the value of nums at i, thus mapping each index to its new value according to the permutation. The result of this operation is a new list that is returned as the output of the buildArray method, which directly corresponds to the permutation pattern defined by the input array nums.
Build Array from Permutation Complexity Analysis
The time complexity of this Python solution for LeetCode’s Build Array from Permutation problem is linear or O(n), where n is the number of elements in the input array nums. This linear time complexity arises because the solution iterates over each element of nums exactly once to construct the new array, with each iteration performing a constant time operation of indexing into nums.
The space complexity is also linear or O(n), attributed to the space required for storing the output array. This space complexity assessment focuses on the additional space required by the method’s execution to produce its output, also known as auxiliary space.
