# Build Array From Permutation

Problem Statement: 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).

#### 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]`

#### Solutions:

Disclaimer: Don’t directly jump into the solution, first try it yourself.

Approach 1: Brute Force Approach

This approach is simple, Just create a `new array ans` of similar length and iterate over given array nums in such a way that you get the value of each index `(like nums[i])` and then use that value as an index to get the value of array nums again `(like nums[nums[i]])` and store it one by one in new array ans `(like ans[i] = nums[nums[i]])`.

For example:

for the given array nums = [0,2,1,5,3,4]

we find ans = [0,1,2,4,5,3]

Code:

```class Coderzpy {

int[] buildArray(int[] nums) {

int len = nums.length;
int[] ans = new int[len];

for(int i = 0; i < len; i++){
ans[i] = nums[nums[i]];
}
return ans;
}
public static void main(String args[]) {

int[] nums = {5,0,1,2,3,4};

System.out.println("The new array is: "+
buildArray(nums));
}
}
```

output: The new array is: [0,1,2,4,5,3]

Time Complexity: O(n) for iterating each element in array nums.

Space Complexity: O(n) for storing all elements in new arrays ans.

Approach 2: Optimized Approach

In this approach, we are going to use the constant space to process the original array :

1. In-place
2. In a way that allows us to move the value `(nums[nums[i]])` in the correct place `(i)`.
3. While also keeping the original value `(nums[i])`, in-place, in some way so that we can use it later when needed.

We have to keep the value `nums[i]` preserved, for example, if we need the value at the later position of the array say `j`, `nums[j] = i`, but we have overridden the value of `i (nums[i])` by `(nums[nums[i]])`, then we will not be able to use the Original value.

To achieve this task we are going to use Euclid’s Division Algorithm in which a number can be represented in the form `a = qb + r`, where `b` and `r` are not multiples of `q`, and `r < q` then we can extract `b` and `r` with the following.

• `b = a / q` (where `/` is integer division) – we know that `qb` when divided by `q` will give us `b`, however, we still would need to get rid of the `r / q`. From our requirements though, `r < q`, so `r / q` will always be `0`, thus `b = (qb/q) + (r/q) = b + 0 = b`
• `r = a % q` – we know that `qb` is a multiple of `q`, thus is divided by it cleanly and we know that `r < q`, so `r` is not a multiple of `q`, therefore the remainder when dividing `a = qb + r` by `q` is just `r`

Euclid’s Division Algorithm Explained (if you don’t understand the above points, then read this first and try to understand the above points again) otherwise skip this part:

Let’s say you have two numbers, `'a'` and `'q'`, and you want to divide `'a'` by `'q'` using integer division (where you only get the whole number part of the division).

1. `b = a / q` (integer division):
• Imagine you have a bag with `'a'` apples, and you want to share them into `'q'` equal-sized groups.
• `'b'` represents the number of complete groups you can make out of those `'a'` apples.
• Now, you might worry about any leftover apples that don’t make a complete group. But, because we’re using integer division, we’re only interested in the complete groups, not the leftovers.
• So, `'b'` is the answer you get by counting how many complete groups of `'q'` apples each you can make out of `'a'` apples.
2. `r = a % q` (remainder of the division):
• Imagine again that you have `'a'` apples and you want to share them into `'q'` equal-sized groups.
• `'r'` represents the remaining apples that don’t fit perfectly into those groups.
• For example, if `'a'` is 10 and `'q'` is 3, you can make 3 groups of 3 apples each (totaling 9 apples), and there will be 1 apple left over (the remainder).
• `'r'` is the number of apples that are left after you’ve distributed as many complete groups of `'q'` apples as possible.

Now, putting it together:

• When you divide `'a'` by `'q'` and get `'b'`, you’re counting the full groups of `'q'` apples that fit into `'a'`, ignoring any leftover apples.
• When you calculate the remainder `'r'`, you’re finding the number of apples that are left over after filling complete groups of `'q'` apples.

So, when you add up the full groups of `'q'` apples `('b')` and the leftover apples `('r')`, you get back to the original number of apples `'a'`. The remainder `'r'` is the part that couldn’t be evenly divided into complete groups, but it’s still part of the original total `'a'`.

Now come back to the solution of our problem:

We need to find a way to transform every element of `nums` into the form `a = qb + r`.

At every `i``nums[nums[i]]` is going to be our `b` and the original value, `nums[i]` is our `r`. Now we just need a `q` that satisfies the `r < q`, for all the possible `r` values (all `nums[i]`). Luckily, we have such a `q` already, as our array values are indices in the same array. `q = nums.length` is always guaranteed to be greater than all `nums[i]` because each index is always within the bounds of the array, from `0` to `nums.length`.

Code:

```class Coderzpy {

public int[] buildArray(int[] nums) {

int q = nums.length;

for(int i = 0; i < q; i++) {

int r = nums[i];

int b = nums[nums[i]]%q ;

nums[i] = q*b + r;
}

for(int i = 0; i < q; i++) {

nums[i] = nums[i]/q;
}

return nums;
}

public static void main(String args[]) {

int[] nums = {5,0,1,2,3,4};

System.out.println("The new array is: "+
buildArray(nums));
}
}
```

output: The new array is: [0,1,2,4,5,3]

Time Complexity: O(n) for iterating each element in array nums.

Space Complexity: O(1) because no new array is created to keep new values.