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

*and return it. A zero-based permutation*

`0 <= i < nums.length`

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

- In-place
- In a way that allows us to move the value
`(nums[nums[i]])`

in the correct place`(i)`

. - 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

*and*

`b`

*are not multiples of*

`r`

*, and*

`q`

*then we can extract*

`r < q`

*and*

`b`

*with the following.*

`r`

(where*b = a / q*`/`

is integer division) – we know that

when divided by*qb*

will give us*q*

, however, we still would need to get rid of the*b*

. From our requirements though,*r / q*

, so*r < q*

will always be*r**/ q*`0`

, thus*b = (qb/q) + (r/q) = b + 0 = b*

– we know that*r = a % q*

is a multiple of*qb*

, thus is divided by it cleanly and we know that*q*

, so*r < q*

is not a multiple of*r*

, therefore the remainder when dividing*q*

by*a = qb + r*

is just*q**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

*, and you want to divide*

`'q'`

*by*

`'a'`

*using integer division (where you only get the whole number part of the division).*

`'q'`

(integer division):`b = a / q`

- Imagine you have a bag with
apples, and you want to share them into`'a'`

equal-sized groups.`'q'`

represents the number of complete groups you can make out of those`'b'`

apples.`'a'`

- 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,
is the answer you get by counting how many complete groups of`'b'`

apples each you can make out of`'q'`

apples.`'a'`

- Imagine you have a bag with
(remainder of the division):`r = a % q`

- Imagine again that you have
apples and you want to share them into`'a'`

equal-sized groups.`'q'`

represents the remaining apples that don’t fit perfectly into those groups.`'r'`

- For example, if
is 10 and`'a'`

is 3, you can make 3 groups of 3 apples each (totaling 9 apples), and there will be 1 apple left over (the remainder).`'q'`

is the number of apples that are left after you’ve distributed as many complete groups of`'r'`

apples as possible.`'q'`

- Imagine again that you have

Now, putting it together:

- When you divide
by`'a'`

and get`'q'`

, you’re counting the full groups of`'b'`

apples that fit into`'q'`

, ignoring any leftover apples.`'a'`

- When you calculate the remainder
, you’re finding the number of apples that are left over after filling complete groups of`'r'`

apples.`'q'`

So, when you add up the full groups of * 'q'* apples

*and the leftover apples*

`('b')`

*, you get back to the original number of apples*

`('r')`

*. The remainder*

`'a'`

*is the part that couldn’t be evenly divided into complete groups, but it’s still part of the original total*

`'r'`

*.*

`'a'`

**Now come back to the solution of our problem:**

We need to find a way to transform every element of

into the form *nums*

.*a = qb + r*

At every

, *i*

is going to be our *nums[nums[i]]*

and the original value, *b*

is our *nums[i]*

. Now we just need a *r*

that satisfies the *q*

, for all the possible *r < q*

values (all *r*

). Luckily, we have such a *nums[i]*

already, as our array values are *q** 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.

**Follow Me**

If you like my post please follow me to read my latest post on programming and technology.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py