Problem Statement

Given a zero-based permutationnums (0-indexed), build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 ≤ i < nums.length and return it.

A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).

Follow-up: Can you solve it wi

Examples

Example 1:

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

Explanation:
The array ans is built as follows:
ans = [
       nums[nums[0]],
       nums[nums[1]],
       nums[nums[2]],
       nums[nums[3]],
       nums[nums[4]],
       nums[nums[5]]
      ]
     = [
        nums[0],
        nums[2],
        nums[1],
        nums[5],
        nums[3],
        nums[4],
       ]
     = [0, 1, 2, 4, 5, 3]

Example 2:

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

Explanation:
The array ans is built as follows:
ans = [
       nums[nums[0]],
       nums[nums[1]],
       nums[nums[2]],
       nums[nums[3]],
       nums[nums[4]],
       nums[nums[5]]
      ]
    = [
       nums[5],
       nums[0],
       nums[1],
       nums[2],
       nums[3],
       nums[4]
      ]
    = [4,5,0,1,2,3]

Different Approaches

1️⃣ Brute Force Approach

Intuition:

• Create a new array ans of the same size.
• For each index i, just compute ans[i] = nums[nums[i]]

Code:

// Function to build a new array from the given nums array
// where each element at index i is nums[nums[i]]
vector<int> buildArray(vector<int>& nums) {
    int n = nums.size();           // Step 1: Get the size of the input array
    vector<int> ans(n);            // Step 2: Create a new vector 'ans' of the same size

    // Step 3: Populate the 'ans' array
    for (int i = 0; i < n; ++i) {
        ans[i] = nums[nums[i]];    // Set ans[i] to the value at index nums[i] in the original array
    }

    // Step 4: Return the constructed array
    return ans;
}

Complexity Analysis:

• Time Complexity:O(n)
  • As we are iterating over the array once.
• Space Complexity:O(n)
  • As we are using the ans array for storage.

2️⃣ In-Place Trick

Observation:

All values are in range [0, n-1], so you can encode two values into one by:

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

Later, extract the new value:

nums[i] = nums[i] / n

Why it works:

• Storing two values in one cell using mode and division because both values are less than n.

Dry Run:

Example:

nums = [0, 2, 1]

Step 1: Encode

nums[0] = 0 + 3 * (nums[0] % 3) = 0 + 3 * 0 = 0
nums[1] = 2 + 3 * (nums[2] % 3) = 2 + 3 * 1 = 5
nums[2] = 1 + 3 * (nums[1] % 3) = 1 + 3 * 2 = 7

Step 2: Decode

nums[0] = 0 / 3 = 0
nums[1] = 5 / 3 = 1
nums[2] = 7 / 3 = 2

Code:

class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        int n = nums.size();

        // First pass: Encode both original and new values in nums[i]
        for (int i = 0; i < n; i++) {
            // nums[nums[i]] might already be modified, so we take modulo n
            int originalVal = nums[nums[i]] % n;

            // Store both old and new values in nums[i]
            // Old value is preserved as (nums[i] % n)
            // New value is stored as (originalVal * n)
            nums[i] = nums[i] + (n * originalVal);
        }

        // Second pass: Extract the new value from the encoded nums[i]
        for (int i = 0; i < n; i++) {
            // The new value is the higher part (quotient) of nums[i] / n
            nums[i] = nums[i] / n;
        }

        // Return the transformed array
        return nums;
    }
};

Complexity Analysis:

• Time Complexity:O(n + n)
• Space Complexity:O(1)