Build Array from Permutation

Build Array from Permutation

What is this problem about?

The "Build Array from Permutation interview question" is a straightforward array manipulation task. You are given a zero-based permutation array nums. Your task is to build a new array ans of the same length where each element ans[i] is equal to nums[nums[i]]. This problem tests your ability to access array elements using indices that are themselves stored within the array.

Why is this asked in interviews?

Companies like Microsoft, Meta, and Amazon use the "Build Array from Permutation coding problem" as a warm-up or introductory question. It assesses basic programming fluency, array indexing, and sometimes, the ability to optimize space. While the basic solution uses $O(n)$ space, a common follow-up is to solve it in-place with $O(1)$ extra space, which tests knowledge of mathematical encoding tricks.

Algorithmic pattern used

The primary pattern is Array Simulation.

1. Basic Approach: Create a new array and fill it using a single loop where ans[i] = nums[nums[i]].
2. Space Optimization (In-place): Use the formula a + b * k to store two numbers in one cell. Here, a is the original value and b is the new value (nums[nums[i]]). By using nums[i] = nums[i] + (nums[nums[i]] % n) * n, you can later retrieve the new value using integer division by n.

Example explanation

Input: nums = [0, 2, 1]

1. $i=0$: ans[0] = nums[nums[0]] = nums[0] = 0.
2. $i=1$: ans[1] = nums[nums[1]] = nums[2] = 1.
3. $i=2$: ans[2] = nums[nums[2]] = nums[1] = 2. Result: [0, 1, 2].

Common mistakes candidates make

• Space Complexity: Failing to mention the $O(n)$ space requirement for the naive solution.
• In-place Confusion: Trying to update the array in-place without encoding, which leads to using updated values for subsequent calculations and producing the wrong result.
• Integer Overflow: In the in-place encoding trick, forgetting that a + b * n might exceed the maximum integer limit if $n$ is very large.

Interview preparation tip

Always ask if an in-place solution is required. This shows you are thinking about memory efficiency. Master the "Array interview pattern" of using modulo and division to store multiple values in a single integer.