Build Array from Permutation | Follow Up Qn | Detailed Explanation | Leetcode 1920 |codestorywithMIK

Hi Everyone, this is the 85th video of our Playlist "Leetcode Easy".
Now we will be solving a good but easy Problem - Build Array from Permutation | Follow Up Qn | Detailed Explanation | Leetcode 1920 | codestorywithMIK

I will explain it in full detail so that it becomes easy to understand. We will find the reason behind everything so that we understand why we did what we did.
And we will do a complete dry run.

Problem Name : Build Array from Permutation | Follow Up Qn | Detailed Explanation | Leetcode 1920 | codestorywithMIK
Company Tags : will update later
Code Github(C++ & JAVA) - will update later tonight

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Video Summary :
The problem requires constructing an array such that ans[i] = nums[nums[i]].
Instead of using extra space, the solution encodes both old and new values into each element using the formula:
nums[i] = nums[i] + n * (nums[nums[i]] % n), where % n ensures correct value extraction.
In the second pass, nums[i] is divided by n to retrieve only the newly encoded value, achieving an in-place transformation.
This approach uses mathematical encoding to meet the O(1) space constraint.

✨ Timelines✨
00:00 - Introduction
0:19 - Motivation
0:49 - Problem Explanation
3:53 - Simple Approach
4:41 - Follow Up Qn
8:20 - Detailed with example
21:50 - Story To Code
24:19 - Coding it up

#MIK #mik #Mik
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[harshugamer]

I did this using bits. I played with the constraints — since the values are ≤ 1000, at most the last 11 bits are used. So I stored the new number in the remaining unused bits, and in the second loop, I removed the old part.

class Solution {
public int[] buildArray(int[] nums) {
int n = nums.length;

int mask = 0;

for(int i = 0 ; i < nums.length ; i++){
//get old part
int curr = old(nums[nums[i]]);

//curr h vo nums[i] ka naya part h naye part ko left me rakhte hai
curr = curr << 11;

nums[i] += curr;
}

for(int i = 0 ; i < nums.length ; i++){
//remove old part
nums[i] = nums[i] >> 11;
}

return nums;
}

public int old(int n){
int curr = 0;

for(int i = 0 ; i < 11 ; i++){
if((n & (1 << i)) != 0){
curr += Math.pow(2, i);
}
}

return curr;
    }
}

[deepanshuverma]

Hi Mik, Great explanation as always.

Also for viewers, there is another way using bit manipulation where we hide the new Value & old values in Bit representation.
Binary String of a number : from right to left, first few digits contains oldvalue while remaining contains new value

binary String : here 8(1000) is new Value and 2(0010) is old value.
Also we will be using MSB to know how many bits to shift to make space for both the values
Java code :

public int[] buildArray(int[] nums) {
int n = nums.length;
int msb = (int) ((Math.log(n) / Math.log(2)) + 1);
int mask = (1 << msb) - 1;

// binary String :: new Value....old Value
for (int i = 0; i < n; i++) {
nums[i] |= (nums[nums[i]] & mask) << msb;
}

for (int i = 0; i < n; i++) {
nums[i] >>= msb; // remove old value
}

return nums;
}

[sauravchandra]

The hint that we have to store two numbers in one made the problem easy. Here is the C++ code for the follow-up approach:
class Solution {
public:
vector<int> buildArray(vector<int>& nums) {
for(int i=0; i<nums.size(); i++){
int j = nums[i];
int old = nums[j];

// need to get the old num
if(j < i){
old = nums[j]/1000;
}

nums[i] *= 1000;
nums[i] += old;
}

for(int i=0; i<nums.size(); i++){
nums[i] %= 1000;
}

return nums;
}
};

[piyushgoyal]

sir please bitmasking ke question bhi kraiye...

[coderbanda-ps]

wow. loved this one. good problem follow up

[Vivek-mto]

class Solution {
public:
vector<int> buildArray(vector<int>& nums) {
int n= nums.size();
vector<int>ans;
for(int i=0 ; i<n ; i++){

}
return ans ;
}
}; my appraoch honestliy apne mn se a gya sir ji, thank you sir ji 😅😅

[harshugamer]

Hey Mic!! Currently, I am doing DSA in Java. Now I want to switch, but I am confused between C++ and Python 3. C++ has strong community support and faster execution for competitive programming, whereas Python is less complex, easier to write, and requires less code — so what should I select?

[vibhumathur]

why these O(1) things dont come to my mind instinctively??😑

[tusharnanda]

#solved
In place Approach
class Solution {
public:
vector<int> buildArray(vector<int>& nums) {
int n = nums.size();
for(int i = 0 ; i < n ;i++)
{
int val = nums[nums[i]]%10000;
nums[i] = nums[i] + 10000*val;
}
for(auto &ele:nums)ele = ele/10000;
return nums;
}
};

[Vivek-mto]

can i start system degein with out devlopment sir ji batao na , aapa se nahi puchuga to kisse puchu ☺☺

[aadarshranjan]

my solution class Solution {
public:
vector<int> buildArray(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n);
for (int i = 0; i < n; i++) {
ans[i] = nums[nums[i]];
}
return ans;
}
};

[aizadiqbal]

we can do in the opposite way also right ?

[calisthenics]

Can anyone suggest more questions of this type??

[AryanVats]

Why we can't do old*n+new..instead of old+new*n

[belugabeluga]

mik bhi, I have a question. After running the for loop 2nd time, we are changing nums[i], toh usse toh array badal jayegi na, toh woh galat ans kyun nhi de rhe hai? Please reply

[dhairyachauhan]

Hi sir, i have a system design interview in the next week.
Will your playlist be enough?
I am a 2025 grad so have no idea about system design.
Can you suggest me resources that can help me in the last min prep.
Previously they have asked to design the hld of a load balancer

[bhuppidhamii]

i wasn't able to come up with O1 approach

[Glaring-]

why we not write formula like this ((5*n)+4)/n and for another one %n ?