1920. Build Array from Permutation

Problem Statement

link: LeetCode.cn LeetCode 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:

Input: nums = [0,2,1,5,3,4] Output: [0,1,2,4,5,3]

Input: nums = [5,0,1,2,3,4] Output: [4,5,0,1,2,3]

Constraints: 1 <= nums.length <= 1000 0 <= nums[i] < nums.length The elements in nums are distinct.

Follow-up: Can you solve it without using an extra space (i.e., O(1) memory)?

Solution Approach

To build the array ans from the permutation nums, update each element in nums by combining the current value and the value at the index specified by nums[i], and then extract the result by dividing each element by 1000.

Algorithm

1. Update Elements: Modify each element nums[i] to include both the current value and the value from nums[nums[i]], using a scaling factor (e.g., 1000) to keep both values in the same element.
2. Extract Result: Divide each modified element by the scaling factor to retrieve the desired values from nums[nums[i]].
3. Preserve Original Values: Ensure that the initial values of nums are preserved during the update phase so that the final extraction is accurate.

   Complexity

   time complexity: O(n) space complexity: O(1)

Implement

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

    
    

Twitter  facebook  Email