Build Array from Permutation

1. Problem Summary

You are given an integer array nums where:

It is a zero-based permutation
Meaning, it contains all integers from 0 to nums.length - 1 exactly once

Your task is to construct a new array ans such that:

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

Then return ans.

Example:

Input:  nums = [0,2,1,5,3,4]
Output: [0,1,2,4,5,3]
Because:
ans[0] = nums[nums[0]] = nums[0] = 0
ans[1] = nums[nums[2]] = nums[2] = 1
...

2. Key Insights

Insight 1: Direct indexing solves it

Since nums is a permutation, every index lookup is valid.

Insight 2: No need for additional logic

No sorting, mapping, or validation needed.

Insight 3: Can be done in two ways

Using extra array (simple and safe)
In-place encoding using math trick (space optimized)

Insight 4: In-place trick relies on value range

Because values are within range [0, n-1], we can encode two values into one integer:

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

Then decode later.

Insight 5: For most use-cases, extra-array solution preferred

Readable, clean, fast enough.

3. Approach

Method A: Build result using new array

Steps:

Create array ans with size equal to nums.length
Loop through each index i
Set: ans[i] = nums[nums[i]]
Return ans

4. Time and Space Complexity

Time Complexity:

O(N)

Single loop through array.

Space Complexity:

O(N)

Because we allocate result array.

5. Java Solution (Simple and Recommended)

class Solution {
    public int[] buildArray(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];

        for (int i = 0; i < n; i++) {
            ans[i] = nums[nums[i]];
        }

        return ans;
    }
}

6. In-Place Java Solution (Space O(1))

class Solution {
    public int[] buildArray(int[] nums) {
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            nums[i] = nums[i] + n * (nums[nums[i]] % n);
        }

        for (int i = 0; i < n; i++) {
            nums[i] = nums[i] / n;
        }

        return nums;
    }
}

7. Dry Run Examples

Example 1

Input:

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

Computation:

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

Output:

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

Example 2

Input:

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

Output:

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

Example 3

Input:

[1,0]

Output:

[0,1]

Example 4

Input:

[2,1,0]

Output:

[0,1,2]

Example 5

Input:

[3,4,2,0,1]

Output:

[0,1,2,3,4]

8. Why This Solution Works

Permutation guarantees valid nested indexing
No duplicates ensure deterministic output
Index substitution matches problem definition exactly
In-place variation mathematically encodes and extracts values safely

9. Common Mistakes

Assuming nums contains arbitrary numbers (it does not)
Trying to sort before processing
Using temporary values without modulo encoding (breaks correctness)
Confusing nums[i] with index instead of indirect lookup
Forgetting zero-based assumption