# Build Array from Permutation
**Difficulty:** EASY
[External](https://leetcode.com/problems/build-array-from-permutation)
Canonical: https://scaleengineer.com/dsa/problems/build-array-from-permutation
**Data structures:** Array
---
## Problem
Given a **zero-based permutation** `nums` (**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**).

**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]

**Constraints:**

* `1 <= nums.length <= 1000`
* `0 <= nums[i] < nums.length`
* The elements in `nums` are **distinct**.

**Follow-up:** Can you solve it without using an extra space (i.e., `O(1)` memory)?

# Approaches
## Using an Extra Array
This is a straightforward approach where we create a new array to store the results. We iterate through the input array `nums`, and for each index `i`, we calculate `nums[nums[i]]` and place it into the corresponding index of the new array.
**Time:** O(n), where n is the length of the `nums` array. We iterate through the array once to build the `ans` array. · **Space:** O(n), as we use an extra array `ans` of the same size as the input array to store the results.
**Pros:** Very simple and easy to understand.; The logic directly translates the problem statement into code.
**Cons:** Uses extra space, which might not be desirable for large inputs or strict memory constraints.; Does not satisfy the follow-up requirement of an O(1) space solution.
### Explanation
The problem asks us to build an array `ans` where `ans[i] = nums[nums[i]]`. The most direct way to achieve this is to allocate a new array, say `ans`, with the same length as `nums`.

We then loop from `i = 0` to `nums.length - 1`. In each iteration, we compute the value `nums[nums[i]]`. Note that since we are reading from the original, unmodified `nums` array and writing to the new `ans` array, we don't have to worry about overwriting values that are needed for later calculations.

The computed value is then assigned to `ans[i]`. After the loop finishes, the `ans` array will contain all the required values, and we can return it.

```java
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;
    }
}
```
### Algorithm
1. Get the length of `nums`, let's call it `n`.
2. Create a new integer array `ans` of size `n`.
3. Iterate with an index `i` from `0` to `n-1`.
4. Inside the loop, calculate `nums[nums[i]]`.
5. Assign this result to `ans[i]`.
6. After the loop, return the `ans` array.

## In-place Modification with Encoding (O(1) Space)
This approach solves the problem without using any extra space, fulfilling the follow-up requirement. The key idea is to store two values (the original and the new value) at each array index simultaneously. This is achieved by using a mathematical encoding/decoding scheme. We iterate through the array twice: once to encode the new values and a second time to decode them into the final result.
**Time:** O(n), where n is the length of the array. We perform two separate passes over the array, which results in O(n) + O(n) = O(2n), which simplifies to O(n). · **Space:** O(1), as we modify the array in-place and do not use any additional data structures that scale with the input size.
**Pros:** Highly space-efficient, meeting the O(1) space complexity requirement.; An elegant solution that demonstrates a useful encoding trick.
**Cons:** The logic is more complex and less intuitive than the extra-space approach.; It modifies the input array, which might not be permissible in all contexts.
### Explanation
To solve the problem in O(1) space, we must modify the input array `nums` in-place. A naive in-place update like `nums[i] = nums[nums[i]]` would fail because it might overwrite an original value that is needed for a later calculation.

The trick is to store both the original value and the new value at each index `i`. Since all numbers in `nums` are in the range `[0, n-1]`, we can use the formula `a + n * b` to store two numbers `a` and `b` (both less than `n`) in a single integer. Here, `a` can be retrieved by `(a + n*b) % n`, and `b` can be retrieved by `(a + n*b) / n`.

The algorithm proceeds in two passes as described above. After the second pass, `nums` will be transformed into the desired output array.

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

        // Encode the result in each number
        // nums[i] = old_val + n * new_val
        for (int i = 0; i < n; i++) {
            // new_val is the original value at nums[nums[i]]
            // which can be retrieved by nums[nums[i]] % n
            nums[i] = nums[i] + n * (nums[nums[i]] % n);
        }

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

        return nums;
    }
}
```
### Algorithm
1. **Encoding Pass:** Iterate through `nums` from `i = 0` to `n-1`.
   - For each index `i`, the original value is `a = nums[i]`. The new value we want to store is `b = nums[nums[i]]`.
   - However, the value at `nums[nums[i]]` might have already been encoded from a previous step. To get its *original* value, we compute `nums[nums[i]] % n`.
   - So, the new value for index `i` is `b = nums[nums[i]] % n`.
   - We update `nums[i]` to store both its original value and this new value: `nums[i] = nums[i] + n * b`.
2. **Decoding Pass:** Iterate through `nums` again from `i = 0` to `n-1`.
   - Each `nums[i]` now holds an encoded value `original_value + n * new_value`.
   - To get the final result, we just need the `new_value`, which can be extracted by integer division: `nums[i] = nums[i] / n`.

# Solutions
### Java

```java
class Solution {
public
  int[] buildArray(int[] nums) {
    int[] ans = new int[nums.length];
    for (int i = 0; i < nums.length; ++i) {
      ans[i] = nums[nums[i]];
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number[]} */ var buildArray = function (
  nums,
) {
  let ans = [];
  for (let i = 0; i < nums.length; ++i) {
    ans[i] = nums[nums[i]];
  }
  return ans;
};

```

### CPP

```cpp
class Solution {
public:
  vector<int> buildArray(vector<int> &nums) {
    vector<int> ans;
    for (int &num : nums) {
      ans.push_back(nums[num]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def buildArray(
        self, nums: List[int]) -> List[int]: return [nums[num] for num in nums]

```