We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Build Array from Permutation

Number: 2048

Difficulty: Easy

Paid? No

Companies: Google, Bloomberg, Amazon, Apple, Meta

Problem Description

Given a zero-based permutation array nums, construct an answer array ans of the same length where each element ans[i] is assigned the value nums[nums[i]]. In other words, for every index i, set ans[i] = nums[nums[i]]. The array nums is a permutation of integers ranging from 0 to nums.length - 1.

Key Insights

  • The problem is a simple simulation: use the given nums array to build a new array where each element is determined by another indexed lookup in nums.
  • A direct approach uses extra memory O(n): simply iterate through the array and build a new array with ans[i] = nums[nums[i]].
  • For the follow-up with O(1) extra space, modify the original array in-place by encoding both the new and the old value in each element. This can be done using modulo arithmetic, leveraging the fact that nums is a permutation.
  • Ensure careful handling of the encoding/decoding steps to extract the updated val without losing the original information.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(n) for the extra memory approach, and O(1) for the in-place modification approach (excluding the space for input/output).

Solution

The approach involves two main strategies. The first is straightforward: create a new array and for each index i, set ans[i] = nums[nums[i]]. This uses extra O(n) space.

For the in-place solution (O(1) space), use the modulo encoding trick:

  • Iterate over each index and update nums[i] by adding (nums[nums[i]] % n) multiplied by n. Here, n is the length of the array. This step encodes both the old and new values into the current element.
  • After all elements have been updated, iterate again to decode the new values by dividing each element by n.

Key data structures include arrays, and the main algorithmic approach is simulation combined with in-place encoding to optimize space usage.

Code Solutions

# Python solution with in-place modification using modulo arithmetic

def buildArray(nums):
    n = len(nums)
    # First pass: encode both old and new values in each element.
    for i in range(n):
        # Store the value at nums[nums[i]] (which could already be modified)
        # Use modulo to retrieve the original value.
        nums[i] += (nums[nums[i]] % n) * n
    # Second pass: decode the new value from each element.
    for i in range(n):
        nums[i] //= n
    return nums

# Alternative extra memory solution:
def buildArrayExtra(nums):
    return [nums[nums[i]] for i in range(len(nums))]

# Example usage:
if __name__ == "__main__":
    ex = [0, 2, 1, 5, 3, 4]
    print(buildArray(ex))  # Output: [0, 1, 2, 4, 5, 3]
← Back to All Questions