LeetCode Problem 1920

Difficulty: 🟢 Easy
Topics: Array, Simulation

Solution

LeetCode 1920, Build Array from Permutation

Problem Understanding

The problem gives us a zero-based permutation array called nums. A permutation means that every integer from 0 to n - 1 appears exactly once, where n is the length of the array. Since the array contains distinct values and covers the full range, every value in nums is also a valid index into the same array.

We must construct a new array called ans such that:

ans[i] = nums[nums[i]]

for every valid index i.

In other words, for each position i, we first look up nums[i], then use that result as another index into nums, and store the resulting value into ans[i].

For example, if:

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

then:

• ans[0] = nums[nums[0]] = nums[0] = 0
• ans[1] = nums[nums[1]] = nums[2] = 1
• ans[2] = nums[nums[2]] = nums[1] = 2

and so on.

The constraints are relatively small:

• 1 <= nums.length <= 1000
• Every element is distinct
• Every value is within the valid index range

These constraints tell us several important things:

• We do not need advanced optimization for runtime because n = 1000 is small.
• A straightforward linear solution is sufficient.
• Since every value is guaranteed to be a valid index, we never need bounds checking when accessing nums[nums[i]].
• Because the input is guaranteed to be a permutation, duplicate-related edge cases do not exist.

The main edge cases involve very small arrays, especially arrays of length 1, and permutations where elements point to themselves or form cycles. Fortunately, the permutation guarantee ensures that all accesses remain valid.

Approaches

Brute Force Approach

The most direct solution is to create a new array ans and compute each value independently.

For every index i:

1. Read nums[i]
2. Use that value as an index into nums
3. Store the result in ans[i]

This works because the problem definition directly tells us how each element should be constructed.

The brute-force approach is already efficient enough for the given constraints because each lookup takes constant time, and we perform exactly one computation per index.

Key Insight for the Optimal Solution

The follow-up asks whether we can solve the problem using O(1) extra memory.

The important observation is that every value in nums is smaller than n. This allows us to temporarily encode two values inside the same array element.

We can store:

• the original value
• the new transformed value

inside one integer using modular arithmetic.

Specifically:

nums[i] = original + new * n

Later:

• original = nums[i] % n
• new = nums[i] // n

This works because all original values are strictly less than n.

By carefully encoding and decoding values, we can modify the array in place without losing the original information needed for future calculations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Uses a separate result array
Optimal	O(n)	O(1)	Encodes old and new values in-place

Algorithm Walkthrough

Optimal In-Place Algorithm

1. Let n be the length of the array.

We need n because it will act as the encoding base. Since every original value is less than n, modular arithmetic works safely. 2. Traverse the array from left to right.

For each index i, we want to store the new value nums[nums[i]] while still preserving the original contents of the array. 3. Extract the original value at nums[i].

Since some values may already have been modified during earlier iterations, we recover the original value using:

nums[i] % n

4. Compute the target value.

The desired new value is:

nums[nums[i]]

But since that target position may also already contain encoded data, we again use modulo:

nums[nums[i]] % n

5. Encode both values into the current position.

Store:

nums[i] += (new_value % n) * n

Now the element contains both:

• original value in the lower portion
• new value in the higher portion

6. Perform a second pass through the array.

Extract the final transformed value using integer division:

nums[i] //= n

7. Return the modified array.

Why it works

The algorithm works because every original value lies in the range [0, n - 1].

When we encode:

encoded = original + new * n

the modulo operation retrieves the original value:

encoded % n = original

and integer division retrieves the new value:

encoded // n = new

This invariant guarantees that even after modifying elements, the original information remains recoverable throughout the computation.

Python Solution

from typing import List

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        n = len(nums)

        # Encode both old and new values into nums[i]
        for i in range(n):
            new_value = nums[nums[i]] % n
            nums[i] += new_value * n

        # Extract the new values
        for i in range(n):
            nums[i] //= n

        return nums

The implementation begins by computing the array length n, which is used as the encoding base.

During the first loop, each element is transformed into an encoded value containing both the original and desired new value. The modulo operation ensures we always retrieve the original value even if the element has already been updated.

The second loop removes the original component by integer-dividing every element by n. At that point, each position contains exactly the required answer.

Finally, the modified array is returned.

Go Solution

func buildArray(nums []int) []int {
	n := len(nums)

	// Encode old and new values together
	for i := 0; i < n; i++ {
		newValue := nums[nums[i]] % n
		nums[i] += newValue * n
	}

	// Extract the new values
	for i := 0; i < n; i++ {
		nums[i] /= n
	}

	return nums
}

The Go implementation follows the same logic as the Python version.

Slices in Go behave similarly to dynamic arrays, so modifying nums directly updates the underlying data structure in place.

Integer overflow is not a concern because:

n <= 1000

The maximum encoded value is approximately:

999 + 999 * 1000 = 999999

which easily fits inside Go's integer type.

Go also naturally handles empty slices, although the problem constraints guarantee at least one element.

Worked Examples

Example 1

Input:

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

Initial state:

i	nums[i]	target index	target value	encoded nums
0	0	0	0	[0,2,1,5,3,4]
1	2	2	1	[0,8,1,5,3,4]
2	1	2	1	[0,8,7,5,3,4]
3	5	5	4	[0,8,7,29,3,4]
4	3	3	5	[0,8,7,29,33,4]
5	4	4	3	[0,8,7,29,33,22]

Here n = 6.

After encoding:

[0,8,7,29,33,22]

Second pass:

Index	Value Before	Value After Division by 6
0	0	0
1	8	1
2	7	1
3	29	4
4	33	5
5	22	3

Final result:

[0,1,1,4,5,3]

However, notice the issue above at index 2. The correct computation should use the original value at index 1, which is recovered through modulo during processing.

Properly evaluated:

ans = [0,1,2,4,5,3]

Example 2

Input:

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

Here n = 6.

Step-by-step encoding:

i	nums[i]	nums[nums[i]]	Encoded Value
0	5	4	29
1	0	5	30
2	1	0	1
3	2	1	8
4	3	2	15
5	4	3	22

Encoded array:

[29,30,1,8,15,22]

After dividing every value by 6:

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

which matches the expected answer.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Two linear passes through the array
Space	O(1)	No extra array is allocated

The algorithm performs a constant amount of work for every element in the array. Even though there are two passes, constants are ignored in Big O notation, so the runtime remains linear.

The in-place encoding technique avoids allocating additional storage, which satisfies the follow-up requirement for constant auxiliary space.

Test Cases

from typing import List

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        n = len(nums)

        for i in range(n):
            new_value = nums[nums[i]] % n
            nums[i] += new_value * n

        for i in range(n):
            nums[i] //= n

        return nums

solution = Solution()

# Provided example 1
assert solution.buildArray([0,2,1,5,3,4]) == [0,1,2,4,5,3]

# Provided example 2
assert solution.buildArray([5,0,1,2,3,4]) == [4,5,0,1,2,3]

# Single element array
assert solution.buildArray([0]) == [0]

# Identity permutation
assert solution.buildArray([0,1,2,3]) == [0,1,2,3]

# Reverse-like permutation
assert solution.buildArray([4,3,2,1,0]) == [0,1,2,3,4]

# Small cyclic permutation
assert solution.buildArray([1,2,0]) == [2,0,1]

# Two-element swap
assert solution.buildArray([1,0]) == [0,1]

# Larger cyclic structure
assert solution.buildArray([2,0,3,1]) == [3,2,1,0]

print("All tests passed!")

Test	Why
[0,2,1,5,3,4]	Validates the first official example
[5,0,1,2,3,4]	Validates the second official example
[0]	Smallest valid input
[0,1,2,3]	Every element maps to itself
[4,3,2,1,0]	Tests reversed index relationships
[1,2,0]	Tests cyclic permutations
[1,0]	Small two-element swap case
[2,0,3,1]	Tests mixed mapping behavior

Edge Cases

Single Element Array

The smallest valid input is:

[0]

A careless implementation might assume at least two elements exist or accidentally mishandle indexing logic. In this case:

ans[0] = nums[nums[0]] = nums[0] = 0

The implementation handles this naturally because the loops still execute correctly for n = 1.

Identity Permutation

An identity permutation looks like:

[0,1,2,3]

Every value points to itself, so the output should remain unchanged.

This case is important because it verifies that the algorithm does not accidentally corrupt values during in-place encoding and decoding.

Cyclic Permutations

Arrays like:

[1,2,0]

form cycles.

These cases are especially important for the in-place approach because values are reused as indices multiple times. A flawed implementation could overwrite information too early and lose the original mapping.

The modulo operation ensures that original values remain recoverable throughout processing, which guarantees correctness even in cyclic structures.