Build Array from Permutation
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).
This problem is taken from :-
Solution:-
Understanding the Problem:-
Given Array is :-
nums = [0,2,1,5,3,4]
We have to build an array as = nums[nums[i]].
And the new length of the array will be same as the given array.
And here also this will be zero based. i.e. nums[0] = 0 upto nums.length -1, that is nums[5] = 4 where n is the length of the given array.
The given original array is:-
| 0 | 2 | 1 | 5 | 3 | 4 |
So, at index i=0. for first loop.
Nums[0] = 0,
And nums[0] also will be zero.
So the new array will be
| 0 |
For index value 1,
Nums[1] = 2
And nums[2] = 1.
So the new array will be:-
| 0 | 1 |
And similiary for index 2:-
Nums[2] = 1,
And nums[1] is 2.
So the new array will be:-
| 0 | 1 | 2 |
And thus the final array will be:-
| 0 | 1 | 2 | 4 | 5 | 3 |
Approach:-
Here we have to solve the solution in such a way that, the space complexity should be O(1). For that we need to store two values i.e. nums[i] and nums[nums[i]] in the same spot .
That can be achieved by the below formulation:-
nums[i] = nums[i] + n *(nums[nums[i]] % n);
So, only one array data structure will be formed, which will store the values that will be generated by the above equation.
Because, the output values can beachieved from that single value.
e.g.
input = [0,2,1,5,3,4]
Output: [0,1,2,4,5,3]
here, let i=2,
then nums[2] = 1;
and nums[nums[1]] = 2;
So, at index position i=2, as mentioned above, the expected value should be 2.
This can be achived from the above mentioned equation as mentioned below:-
Now for the new value and store it in the array by using the equation:-
nums[i] = nums[i] + n *(nums[nums[i]] % n); //Equation 1
nums[2] = 1 + 6 *(2 %6);
nums[2] = 13
So, the value that will be genarted as:-
for i = 0 , 0,
for i = 1 , the value is 8.
Thus the new final array that will be generated by the equation in the first loop is :-
[0, 8, 13, 29, 33, 22]
Now in Second loop we Can retrieve nums[nums[i]] by dividing by n,
nums[i] = nums[i] + n *(nums[nums[i]] % n) / n;
nums[i] = 0 + nums[nums[i]];
nums[i]= nums[nums[i];
nums[2]/n = 13/6 =2;
Java Code:-
For the complete java code use the below mentioned link:- java code of 1920