Code Implementation

class Solution:
    def buildArray(self, nums):
        # nums[i] is in the range [0, n-1], and nums is a permutation
        # We want ans[i] = nums[nums[i]]
        return [nums[nums[i]] for i in range(len(nums))]
      

class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            ans[i] = nums[nums[i]];
        }
        return ans;
    }
};
      

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;
    }
}
      

var buildArray = function(nums) {
    let n = nums.length;
    let ans = new Array(n);
    for (let i = 0; i < n; i++) {
        ans[i] = nums[nums[i]];
    }
    return ans;
};
      

Problem Description

You are given a zero-indexed array nums of length n, which contains a permutation of the numbers from 0 to n - 1. Your task is to build a new array ans of the same length where ans[i] = nums[nums[i]] for every index i (that is, for each position, look up the value at nums[i] and use it as an index into nums).

• Each element in nums is unique and in the range [0, n-1].
• There is only one valid answer for each input.
• Do not reuse or modify elements in a way that would break the permutation property.

Thought Process

Let's break down what the problem is asking. We have a permutation array, so every number from 0 to n-1 appears exactly once. For each position i, we want to find nums[nums[i]] and put that in the answer array at position i.

The most straightforward approach is to create a new array and, for each index, compute the required value directly. Since the array is a permutation, we know all indices are valid, and we do not need to worry about out-of-bounds errors.

An initial brute-force idea might be to use nested loops, but since each lookup is direct and the permutation property guarantees uniqueness, a single loop suffices. There is no need for further optimization or auxiliary data structures.

Solution Approach

Let's walk through the algorithm step by step:

1. Initialize the Answer Array: Create a new array ans of the same size as nums.
2. Iterate Through Each Index: For each index i from 0 to n-1 (where n is the length of nums):
   • Look up nums[i] to get the index to fetch from nums.
   • Set ans[i] to nums[nums[i]].
3. Return the Result: After the loop, return the ans array.

This approach is efficient because we only process each element once, and each lookup is O(1) due to array indexing. No additional data structures are needed beyond the output array.

Example Walkthrough

Let's use the sample input nums = [5,0,1,2,3,4]. The length n = 6.

1. For i = 0:
   • nums[0] = 5
   • nums[nums[0]] = nums[5] = 4
   • So, ans[0] = 4
2. For i = 1:
   • nums[1] = 0
   • nums[nums[1]] = nums[0] = 5
   • So, ans[1] = 5
3. For i = 2:
   • nums[2] = 1
   • nums[nums[2]] = nums[1] = 0
   • So, ans[2] = 0
4. For i = 3:
   • nums[3] = 2
   • nums[nums[3]] = nums[2] = 1
   • So, ans[3] = 1
5. For i = 4:
   • nums[4] = 3
   • nums[nums[4]] = nums[3] = 2
   • So, ans[4] = 2
6. For i = 5:
   • nums[5] = 4
   • nums[nums[5]] = nums[4] = 3
   • So, ans[5] = 3

The final answer is [4,5,0,1,2,3].

Time and Space Complexity

• Brute-force Approach: If we tried to use nested loops (for each i, search for nums[i]), it would be O(n²), but that's unnecessary here due to direct indexing.
• Optimized Approach: The implemented solution uses a single loop with direct lookups:
  • Time Complexity: O(n), since we process each element exactly once.
  • Space Complexity: O(n), due to the output array ans.

The solution is as efficient as possible for this problem.

Summary

To solve "Build Array from Permutation," we use the fact that permutations allow direct, safe indexing for each element. By iterating once over the array and assigning ans[i] = nums[nums[i]], we get the required result efficiently. The solution is elegant because it leverages the permutation property, requires no auxiliary data structures, and operates in linear time and space.