Problem Informations

• Problem Index: 1920
• Problem Link: Build Array from Permutation
• Topics: Array, Simulation

Problem Description

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 \leq 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 1:

Input: nums = [0,2,1,5,3,4]
Output: [0,1,2,4,5,3]
Explanation: The array ans is built as follows: 
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
    = [0,1,2,4,5,3]

Example 2:

Input: nums = [5,0,1,2,3,4]
Output: [4,5,0,1,2,3]
Explanation: The array ans is built as follows:
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]
    = [4,5,0,1,2,3]

Constraints:

• $1 \leq nums.length \leq 1000$
• $0 \leq 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)?

Intuition

The problem involves constructing a new array from a given permutation of integers. The primary task is to use each index of the array to map to another index in the same array and fetch the value at that mapped index. This type of problem requires understanding the permutation nature of the array, leveraging its zero-based indexing, and forming a new array using the specified transformation rule.

Approach

To solve this problem, we will take advantage of the permutation properties of the input array nums. Since nums is a zero-based permutation, each element nums[i] is a distinct integer ranging from 0 to nums.length - 1. Given this property, we are guaranteed that there will be no out-of-bound errors or duplicate entries.

1. Initialization: First, we determine the length of the input array nums. We then initialize an empty array result of the same length to store the transformed values.

2. Transformation Rule: We iterate over each index i in the array nums. For each index i, we set result[i] to nums[nums[i]]. This operation effectively uses the current element nums[i] as an index to fetch the value from nums, creating a new sequence in the result array.

3. Result Compilation: After populating the result array by iterating over all indices, we return result as the final output.

This approach transforms the array in $O(n)$ time complexity, where $n$ is the length of the array, as it involves a single pass through the array to compute the result. The algorithm also uses $O(n)$ space to store the resultant array. Given the constraints, this approach is efficient and straightforward, utilizing the specific nature of permutations to carry out the transformation.

Code

C++

class Solution {
public:
    // Function to build a rearranged array based on given permutation rule
    vector<int> buildArray(vector<int>& nums) {
        int length = nums.size();  // Get the length of the nums array
        vector<int> result(length); // Initialize the result array with the same length

        // Iterate through each element in nums to build the result array
        for (int i = 0; i < length; i++) {
            result[i] = nums[nums[i]]; // Set each element to nums[nums[i]]
        }

        return result; // Return the constructed array
    }
};

Python

class Solution:
    # Function to build a rearranged array based on given permutation rule
    def buildArray(self, nums):
        length = len(nums)  # Get the length of the nums array
        result = [0] * length  # Initialize the result array with the same length

        # Iterate through each element in nums to build the result array
        for i in range(length):
            result[i] = nums[nums[i]]  # Set each element to nums[nums[i]]

        return result  # Return the constructed array

Complexity

• Time complexity: $O(n)$

  The time complexity of the given function is $O(n)$, where $n$ is the length of the input array nums. This is because the function iterates through the array nums once, performing a constant-time operation for each element to populate the result array.

• Space complexity: $O(n)$

  The space complexity is $O(n)$ due to the creation of the result array, which is of the same length as the input array nums. Aside from the input and output arrays, no additional space is used.