Build Array from Permutation

Easy

Asked by:

27 views

Topics:

Arrays

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 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 <= 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)?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `nums` array, specifically the maximum possible value of `n`?
What is the range of integer values that can be present within the `nums` array? Are negative numbers allowed?
Is the provided `nums` array guaranteed to be a valid permutation, meaning will all numbers from `0` to `n-1` be present exactly once?
Could you provide an example input and the corresponding expected output to ensure my understanding of the problem is correct?
Should I create a new array, or modify the input `nums` array in-place and return it? What is the expected space complexity?

Brute Force Solution

Approach

The brute force approach constructs a new arrangement by looking at each existing value and using it to find a corresponding value in the original arrangement. We create the new arrangement element by element based on the relationship given.

Here's how the algorithm would work step-by-step:

Go through each position in the arrangement one by one.
For the current position, find the value located at that position in the original arrangement.
Use that value as a position and go back to the original arrangement and grab the value located at that position.
Place that value into the same location in the new arrangement that we were working with.
Repeat this process for every position until the new arrangement is complete.

Code Implementation

def build_array_from_permutation(numbers):
    array_length = len(numbers)
    new_array = [0] * array_length

    for index in range(array_length):
        # Find the value at the current index.

        value_at_index = numbers[index]

        # Use that value as an index to find the corresponding value.

        new_array[index] = numbers[value_at_index]

    return new_array

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n. For each index i, it performs a fixed number of operations: accessing nums[i] and then accessing nums[nums[i]]. These are constant-time operations. Since this process is repeated for each of the n elements in the array, the overall time complexity is directly proportional to n, resulting in O(n).

Space Complexity

O(N) – The provided approach constructs a new arrangement (array) element by element. This new arrangement has the same size as the input arrangement, denoted as N. Therefore, the auxiliary space required is directly proportional to the size of the input array, requiring storage for N elements. This results in a linear relationship between input size and space used, resulting in O(N) space complexity.

Optimal Solution

Approach

The goal is to create a new arrangement of numbers based on an initial arrangement. The clever approach is to encode both the old and new values in the original arrangement, then extract the new values in a second step. This avoids using extra storage.

Here's how the algorithm would work step-by-step:

For each number in the original arrangement, combine it with its corresponding number from the new arrangement, storing both pieces of information into a single number within the original arrangement.
The combination must ensure that we can retrieve both the original and the new value separately.
Once all numbers have been combined, go through the arrangement again, this time extracting just the new values and replacing the combined values with these new values to complete the new arrangement.

Code Implementation

def build_array_from_permutation(nums):
    number_of_elements = len(nums)

    # Encode both the new and old values into the array.
    for index in range(number_of_elements):

        nums[index] += number_of_elements * (nums[nums[index]] % number_of_elements)

    # Extract the new values after encoding.
    for index in range(number_of_elements):

        # Shift encoded values to their correct position.
        nums[index] //= number_of_elements

    return nums

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n twice. The first iteration combines the original and new values into a single encoded value. The second iteration extracts the new values from the encoded values. Since both iterations are linear with respect to the input size n, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm modifies the input array in place without using any additional data structures that scale with the input size. It combines the old and new values directly within the existing array elements, and then extracts the new values, again in place. Thus, the auxiliary space required remains constant, regardless of the input array's length, N. This results in O(1) auxiliary space complexity because no extra memory is allocated based on the size of the input.

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an IllegalArgumentException, depending on desired behavior.
Input array with a single element	The algorithm should work correctly since ans[0] = nums[nums[0]].
Large input array (n close to the maximum integer value)	Ensure the index calculations and memory allocation for the 'ans' array don't cause integer overflow or memory exhaustion.
Input array contains values that are out of bounds (i.e., nums[i] >= n or nums[i] < 0)	Throw an IllegalArgumentException because the index access would result in an ArrayIndexOutOfBoundsException.
Input array contains duplicate values and the permutation contains cycles	The standard algorithm directly calculates the new array and handles cycles by design, without any explicit checks.
Input array where nums[i] == i for all i (identity permutation)	The algorithm correctly computes ans[i] = nums[nums[i]] = nums[i], effectively returning the same array.
Integer overflow when accessing nums[nums[i]]	Ensure the data type used for indexing can handle the maximum possible value of 'n' to prevent integer overflow.
Input array is a valid permutation, but creating 'ans' requires excessive memory	Consider in-place manipulation (if allowed and safe) or streaming/chunking for extremely large arrays to reduce memory footprint, otherwise throw OutOfMemoryError.

Null or empty input array

How to Handle:

Return an empty array or throw an IllegalArgumentException, depending on desired behavior.

Input array with a single element

How to Handle:

The algorithm should work correctly since ans[0] = nums[nums[0]].

Large input array (n close to the maximum integer value)

How to Handle:

Ensure the index calculations and memory allocation for the 'ans' array don't cause integer overflow or memory exhaustion.

Input array contains values that are out of bounds (i.e., nums[i] >= n or nums[i] < 0)

How to Handle:

Throw an IllegalArgumentException because the index access would result in an ArrayIndexOutOfBoundsException.

Input array contains duplicate values and the permutation contains cycles

How to Handle:

The standard algorithm directly calculates the new array and handles cycles by design, without any explicit checks.

Input array where nums[i] == i for all i (identity permutation)

How to Handle:

The algorithm correctly computes ans[i] = nums[nums[i]] = nums[i], effectively returning the same array.

Integer overflow when accessing nums[nums[i]]

How to Handle:

Ensure the data type used for indexing can handle the maximum possible value of 'n' to prevent integer overflow.

Input array is a valid permutation, but creating 'ans' requires excessive memory

How to Handle:

Consider in-place manipulation (if allowed and safe) or streaming/chunking for extremely large arrays to reduce memory footprint, otherwise throw OutOfMemoryError.