Build Array from Permutation: Double Indexing in One Pass

Build Array from Permutation is LeetCode 1920. You are given a zero-based permutation nums (meaning nums is a rearrangement of the integers from 0 to nums.length - 1). Build and return an array ans of the same length where ans[i] = nums[nums[i]] for each index i.

Example: nums = [0, 2, 1, 5, 3, 4] produces ans = [0, 1, 2, 4, 5, 3]. Each position in the output is determined by a double lookup into the input array.

The problem is asking you to follow each value as a pointer. nums[i] gives you an intermediate index, and you read the value at that intermediate index to get the final answer. Because nums is a permutation, every intermediate index is valid and in bounds. No range checking needed.

The approach

The key insight is that you do not need to think about this problem in terms of rearranging or sorting. It is a pure simulation: for each index, do exactly what the problem says.

For every index i from 0 to n - 1:

1. Read nums[i] to get an intermediate index.
2. Read nums[nums[i]] to get the final value.
3. Store that value in ans[i].

That is it. One pass through the array, one lookup per index, and you are done. The permutation guarantee means every value in nums is a valid index, so you never go out of bounds.

Visual walkthrough

Let's trace through nums = [0, 2, 1, 5, 3, 4] step by step. At each index, the blue cell shows where we are reading from (i), the orange cell shows the intermediate index (nums[i]), and the green cells in the answer row show values we have already placed.

Notice how each step is independent. The value you write at ans[3] does not depend on what you wrote at ans[0]. Every lookup goes back to the original nums array, so you can process the indices in any order and still get the same result.

The solution

def buildArray(nums):
    return [nums[nums[i]] for i in range(len(nums))]

Here is what each part does:

1. List comprehension. Iterates i from 0 to len(nums) - 1 and builds the result in a single expression.
2. Double indexing. nums[nums[i]] performs the two-step lookup: first get the intermediate index, then read the value at that index.
3. Return directly. No need for a separate ans variable or append loop. The comprehension builds and returns the array in one shot.

If you prefer a more explicit version:

def buildArray(nums):
    ans = []
    for i in range(len(nums)):
        ans.append(nums[nums[i]])
    return ans

Both produce the same result. The list comprehension is just more concise.

Complexity analysis

Time: O(n) where n is the length of the array. You visit each index exactly once. Each visit does a constant-time double lookup. Total work is linear.

Space: O(n) for the output array ans. If you do not count the output as extra space (which many problems do not), the working space is O(1) since you only use the loop variable i.

The building blocks

This problem is built from one core building block:

Array as index map. When an array contains valid indices into itself, you can follow values as pointers. nums[i] is not just a value, it is an address. This "array as its own lookup table" pattern appears in many permutation problems. Array Nesting (LeetCode 565) follows indices to find cycle lengths. First Missing Positive (LeetCode 41) uses values as target indices to place elements. Whenever the constraint says "values are in the range [0, n-1]," you can treat the array as a self-referencing map.

The double-indexing here is the simplest form of this pattern: one hop through the index map. Harder problems chain multiple hops or detect cycles. But the underlying idea is identical. Values are indices, and you follow them.

Edge cases

• Identity permutation. nums = [0, 1, 2, 3] produces ans = [0, 1, 2, 3]. Every element points to itself, so nums[nums[i]] equals nums[i] equals i.
• Single element. nums = [0] produces ans = [0]. The only valid permutation of length 1 is the identity.
• Two-element swap. nums = [1, 0] produces ans = [0, 1]. Index 0 points to 1, which points to 0. Index 1 points to 0, which points to 1. The double lookup unscrambles the swap.
• Reverse permutation. nums = [4, 3, 2, 1, 0]. ans[0] = nums[4] = 0, ans[1] = nums[3] = 1, and so on. Each double hop lands back on the original index.

From understanding to recall

The solution is one line. But the concept behind it, treating array values as indices and chaining lookups, is the part worth internalizing. Under time pressure, you need to see ans[i] = nums[nums[i]] and immediately know what it means: read the value, use it as an index, read again.

Spaced repetition makes this automatic. Type the solution from scratch today. Do it again in three days. Then a week later. After a few reps, the double-indexing pattern will feel natural, and you will recognize it instantly when harder permutation problems use the same idea under a different disguise.

Related posts

• Rotate Array - Another array rearrangement problem where elements move to new positions based on a computed index
• Permutations - Generating all permutations of an array, the backtracking counterpart to this problem's permutation consumption
• Shuffle an Array - Randomly rearranging array elements, another take on permutation-based index mapping