Build Array from Permutation.

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.