- Published on

# Build Array from Permutation.

- Authors
- Name
- Pankaj Tanwar
- @the2ndfloorguy

**Problem for the day** - Build Array from Permutation

**Tag** - Easy

So, the problem says, we have an zero-based permutation array called `nums`

of some length. All elements are distinct here. We need to return an array of same length where `ans[i] = nums[nums[i]]`

.

for example, we have an array [0,2,1,5,3,4] and our output would be [0,1,2,4,5,3] .

So basically, we are iterating through the array. First element is `0`

means we will replace it with value at `0`

index which is `0`

so no change. Next element is `2`

so we will replace it with value at `2`

index which is `1`

. So first two element will become `0 2 ...`

and so on.

`EASY`

category tag, gave me a confidence and with 1 minute i was ready with my solution. Pretty simple.

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

A very easy approach, initialize an extra array and just iterate over the given array to find out the values for the new array. and finally, just return it.

**Time complexity** - o(n)

**Space Complexity** - o(n)

Perfect! First day, first problem, super quick. But I scrolled down a bit and my happiness didnt't last long. Leetcode says, try to implement this solution in o(1) space.

I started to think of solution. My thought process was, we somehow need to remember the previous value too, if we are updating the array in-place. One approach was use `pair<int,int>`

but it will not work as it will add space.

I looked at the constraints. Max value possible in the `nums`

array is 1000. That was a light bulb moment. Can i make use of it somehow?

Suppose old value is 2 and new value is 1 and max possible value is 1000 so why not store it as `newValue * 1000 + oldValue`

and so by this way, I can find out old value from each value just by modulo by 1000.

```
class Solution {public: vector<int> buildArray(vector<int>& nums) { for(int index=0;index<nums.size();index++) { int val = nums[nums[index]]%1000; nums[index] = val*1000 + nums[index]; }
for(int index=0;index<nums.size();index++) { nums[index] = nums[index] / 1000; } return nums; }};
```

**Time complexity** - o(n)

**Space Complexity** - o(1)

You might like previous editions of my coding diary.