#1920

Easy

LeetCode Problem Workspace

Build Array from Permutation

The problem asks to build an array from a given permutation using an efficient approach.

Problem Statement

You are given a zero-based permutation nums of length n, where nums[i] is a distinct integer in the range [0, n-1]. Your task is to build a new array ans of the same length, where each element ans[i] is calculated as nums[nums[i]]. Return the array ans.

The problem guarantees that the input nums array contains only distinct integers, and the values of nums will always be in the range from 0 to nums.length - 1. This ensures that the indices can be directly accessed and used for the calculations.

Examples

Example 1

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

Output: [0,1,2,4,5,3]

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]

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.

Solution Approach

Simulate the Array Mapping

The problem boils down to simulating the process described in the statement. For each index i in the nums array, compute nums[nums[i]] and store this value in the corresponding position of the result array ans. This ensures the mapping is correctly followed and works in linear time, O(n).

Handle Space Constraints

To meet the O(1) space requirement, modify the array in place if possible, using a temporary variable or auxiliary space to store intermediate values without using extra arrays. This ensures space efficiency while maintaining correctness.

Optimize for Edge Cases

Be aware of edge cases such as the smallest input array (with a single element), as well as the largest possible input size. Ensure your solution works efficiently with the given constraints, taking into account the range of possible values for nums.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity of the solution is O(n) because we iterate through the nums array once to build the ans array. The space complexity is O(1) if we modify the array in place, without using extra space other than temporary variables.

What Interviewers Usually Probe

Does the candidate directly simulate the process described in the statement?
Does the candidate maintain O(1) space complexity in their solution?
Does the candidate handle edge cases and large input sizes correctly?

Common Pitfalls or Variants

Common pitfalls

Confusing the problem with a more complex array manipulation task, forgetting to follow the direct simulation approach.
Using extra space beyond O(1), which violates the problem’s constraints on space efficiency.
Overlooking edge cases such as very small or very large arrays, causing the solution to fail in certain scenarios.

Follow-up variants

Modify the problem to handle multi-dimensional arrays.
Consider implementing a more complex simulation with different mapping rules.
Increase the size of the array significantly, ensuring the solution scales efficiently.

FAQ

How can I solve the Build Array from Permutation problem efficiently?

You can solve it efficiently by directly simulating the array mapping described in the problem statement, iterating over the array in linear time.

What is the time complexity of this problem?

The time complexity is O(n) because we loop through the input array once to build the result array.

How do I meet the O(1) space complexity requirement?

You can meet the O(1) space complexity requirement by modifying the array in place or using minimal extra space, like a temporary variable.

What happens if I use extra space for the result array?

Using extra space would violate the problem’s constraints, and you would lose points for not adhering to the O(1) space requirement.

How can I handle edge cases in this problem?

You should test the solution with small arrays (such as length 1) and very large arrays to ensure the solution works across all possible input sizes.

terminal

Solution

Solution 1: Simulation

We can directly simulate the process described in the problem by constructing a new array $\textit{ans}$. For each $i$, let $\textit{ans}[i] = \textit{nums}[\textit{nums}[i]]$.

1

2

3

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        return [nums[num] for num in nums]

Continue Practicing

#1914 cyclically rotating a grid #1929 concatenation of array #1894 find the student that will replace the chalk