---

1. Problem Summary

You are given an integer array nums of length n, where:

• nums is a zero-based permutation
• meaning it contains all integers from 0 to n-1 exactly once

You must construct a new array ans such that:

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

and return ans.

Example:

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

---

2. Key Insights

Insight 1: Nested indexing is always valid

Since every value in nums is a valid index, accessing nums[nums[i]] is always safe.

Insight 2: No reordering or computation beyond lookup

The problem is directly evaluated per index.

Insight 3: Two solution paths

1. Using a new result array (simple, clean)
2. In-place value encoding (constant space)

Insight 4: In-place trick relies on bounded values

Because values are in [0, n-1], we can temporarily store two values in one slot.

Insight 5: No special cases required

No negative values, duplicates, or out-of-range values to worry about.

---

3. Approach

Standard Approach (recommended)

Steps:

1. Create new array ans with size n
2. Loop through indices: ans[i] = nums[nums[i]]
3. Return ans

In-Place Approach (space optimized)

Steps:

1. Encode both old and new values in nums[i]
2. Extract new values by division

---

4. Time and Space Complexity

Time Complexity

O(N)

Space Complexity

O(N) using ans[]
O(1) using in-place technique

---

5. Java Solution (new array version)

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. Java Solution (in-place constant space)

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]

Evaluation:

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 safe nested lookup
• Index mapping directly matches problem definition
• In-place encoding uses modulo to retain original values
• Works for all valid inputs without branching

---

9. Common Mistakes

1. Thinking nums may contain invalid indices (it cannot)
2. Allocating unnecessary data structures
3. Forgetting modulo when encoding in-place
4. Misinterpreting nums[i] as value rather than index