leetcode 1260 | Shift 2D Grid | 2d to 1d mapping | Leetcode potd

[00:00:00]So hello and good morning to everyone.

[00:00:02]So our today's lead code is 1 1260 that is shift 2D grid. So basically in this question we are given a 2D grid whose size is m cross n and with that we are also given an integer k. Now what we have to do do is we have to shift this grid k*s right we have to shift the grid k times and in one shift operation we have to perform these three things. The first thing is that the element element present at index i, j will move to i, j + 1. So basically it will move to the next column in the same row. Right?

[00:00:42]Then element at grid element at index i, n minus one. That means the elements in the last column will move to the will move to the first column but of the next row. Right? So here see the row is row is changing and the element is moving from the last column to the first column and the element which is present in the in the uh what we call bottom rightmost corner will move to the starting that is 0. So in one operation these three things are do are being done. Now what we have to do is we have to perform the operation K * and then whatever matrix that we have after performing K * that is our answer. So we have to return that matrix. So let's see the example. So here uh this is our initial matrix and we are given K is equal to 1. So we have to perform the operation one time. So basically it is given that all the elements present at I J will move to I J + 1. All the element at i n - 1 will move to i + 1 comma 0 and all the element at n - 1 n -1 will move to 0.

[00:02:08]Right? So first operation I j2. So see this element I comma j it will move to the next this will also move to the next part. Now this this element this element will follow this property that it is in the last column. So it will move to the starting of the first row. So it will move to the starting of the first row.

[00:02:28]So it will move here. Then this element will move here. Again this element will move here and this element will move here. Now this element will move here.

[00:02:37]This element will move here and this will follow this property that is - 1.

[00:02:42]It will move to 0a 0. So it will go to [clears throat] 0a 0. So if you see we get the this matrix 9 1 2 3 4 5 6 7 8 right so that's our output right so let's see the constraints so m which is the number of rows n which is the number of columns both m and n is less than or equal to 50 and each element in the grid is from minus 1,000 to,000 right and k value is less than or equal to 100. Right? So if you'll see the brute force idea. So what is the brute brute force idea? That we'll simulate whatever given to us and each time we'll perform one operation go to the next matrix perform one operation go to the next matrix because in one operation how many elements we are changing? We are changing m cross n elements and total how many operations we have to do? We have to do k operations. So the total time complexity is m cross n cross k right which is 50 into 50 into 100 right that is uh 25 into 10^ 4 or we can say 2.5 into 10^ 5 right so that's our brute force idea but the question is can we do better than brute force idea or not or brute force approach or not so let's see so if you notice here we have discuss this example right. So after performing one operation this matrix has been converted to this matrix. So now if we convert this 2D matrix to 1D array if you convert this 2D matrix to 1D array row wise then we get 1 2 3 4 5 6 7 8 9 right we get this 1D array. Similarly, if we convert this 2D array to 1D array, we'll get this matrix uh this 1D array, right? That is 9 1 2 3 4 5 6 7 8. Right?

[00:04:46]So, do you notice something between these two 1D arrays, right? So if we if we write rotate if we write rotate this this 1D array one times we basically get this 1D array right that means that our 1D array has been rotated to the right by one position and then we are getting our answer right. So now if you notice that thing then instead of uh solving the instead of now thinking about the 2D grid what we can do is we can convert the 2D grid to a 1D grid and then rotate that 1D grid k*s right then we get our answer and then we'll refill we'll refill that answer back to 2D matrix right we can do that right so Let's see with the one more example. So we have taken the same example but now we this time we have taken K is equal to 2. So when [clears throat] we performed one time we get this matrix. Then again we perform the shiftings one time we'll get this matrix. Right? [snorts] Now let's see if we convert this 2D matrix to 1D array we'll get this array. And as we know now our K is equal to 2. So what we'll do is we'll right rotate we'll rotate this array two times in the right direction. So if you rotate two times in the right direction first time 9 will come over here then next time 8 will come over here. So we'll get 8 9 1 2 and so on up to 7. So that means we'll get this we'll get this 1D matrix after rotating two times. Now when we put these elements back to 2D array back to 2D array we get 8 91 8 91 2 3 4 5 6 7.

[00:06:49]So let's check whether this 2D array whether this 2D array is same as this 2D array or not. Yes, both the arrays are same. That means now instead of performing instead of performing the operation K times what we can do is we basically convert a 2D array to 1D array and then rotate that 1D array K times in the right direction and then store the answer back to 2D array. Right? So we can do that. But still one more question. Is there any need to convert the 2D array to 1D array and then rotate? Is there any need of this? So the answer is no. So now what we'll do is now instead of physically rotating instead of physically rotating the array what we'll do we'll basically calculate where each element will go. Now let's say in suppose we have an element at index i, j in the 2D array. So now when we convert the 2D array to 1D array, what will be the index of that element in the 1D array? Right? So suppose let's say we take this element. So that element is 1, 1. So what is the index of that element in the 1D array? So that index is four because before that element how many element before that before this element how many how many elements are there? n elements over here how many row so this is the first row so how many rows are there before this so suppose let's say here we have i rows so then i rows before this element and then how many elements are there in each row in each row we have n elements and then in its row in its row at what position it is there so that position is basically the column that is j so to find the 1D WD index to find the WD index we have taken how many rows are there before that element and how many elements are there in one row plus what is the position of that element in its row in the row of that element. So we get the 1D index which is I into N + J right now now the we have to rotate the 1D array K times we have to rotate the 1D array K times. So suppose in the 1D array the index is let's say I and D is the index.

[00:09:27]Now when we rotate it K times let's say we'll shift it by K to the right side.

[00:09:32]So index plus K. Now it may be possible that it goes out of bound. So so to handle the circular movement we'll we'll take modulo by total elements. And in this 1D array what are the total elements? Total elements is M cross N.

[00:09:48]Right? So what we do is the new index new index after rotating k*s will be current index in the 1d array plus plus k how many times you have to rotate modulo m cross n. So we are doing this modulo operation to handle the circular movement. So that suppose if we have to rotate this array one time then 9 will go to here but this is out of bound. So we have to bring it back to this position. That's why when we take modulo it will come to the initial position.

[00:10:21]Now now we calculated now up to here we have calculated the index the index after rotating in 1D array. Now what we have to do is we have to convert that index to 2D array because at the end we have to return the answer in the 2D array. So suppose we [clears throat] get the index as new index in the 1D array.

[00:10:44]Now when we refill when we refill the elements in the 2D array we'll refill the elements row wise row wise so to find the row number in each row we'll fill n elements in each row we'll fill n elements so whatever index we have we'll if we'll divide that by n then we get the row of the new row right and then to find the column to find the column we'll take modulo of that particular new index Right? Suppose if our new index is five and total elements is 9. So what is a row number? Row number is sorry n is not 9. N is three. That is the number of columns. So 5x3 5x3 is 1. That means it will come in the first row. Now to find the column 5 modulo 3 5 modulo 3 that is that is 2.

[00:11:41]Right? So it will come at it will come at 1,2 that is here right. So this way we'll find the new index in the 2D array also right. So let's see dry run to understand the whole approach. So what we have done is suppose our element is at I comm J then we'll convert it to 1D that is I cross N where N is the number of columns plus J so this is the index in 1D now when we rotate it when we rotate it so after rotating we'll get the index as let's say this index call as in D then we get the new index after rotation so new index is basically I and D plus value of K then modulo total elements which is M cross N right so we get the new index in the 1D array after rotating then we will convert this new index this new index to again back to 2D so for that row new row is basically this new index new index by n and column is equal to new index by new index modulo n right so this way we'll get the uh new row and new column in the 2D array so let's see now currently we have element one so its position is 0 so what will be the index uh 1D index that is uh 0 into 3 + 0 which is 0 right. So what will be the new index? So here k value is 2, k is 2. So 0 + 2 modulo total elements. So new index will be two. Now you will convert this to back to 2D array. So row is 2x 3 which is 0 and column is 2 modulo 3 which is 2.

[00:13:50]So we have to put the element 1 at 0, 2 in the final answer array. Right? So we have put the answer. So now our next element is five. Next element is five which is present at 1, 1. So 1D index 1 index which is I. I is 1 into N is 3 + J which is four. So new index is four. Now after rotating after rotating we'll get the index as 4 + 2 modulo 9 that is 6.

[00:14:23]We get the new index as 4 + 2 modulo 9 that is six. Now we convert this index to the two to 2D array. So 6ide by 3 we get two. Row number is 2 column number is 0. So the element at 1a 1 will be will be moved to at 2 0. Right? So we put it this is 2 0. So now we'll follow the same steps for every element. So this way we'll get our final answer. So let's see the code part. So in the code part we have taken the number of rows, number of columns and then we have taken the total elements in the uh 2D array and then as we know we are shifting or we are rotating the array k times. So it may be possible that the k value is greater than the total number of elements. Right? So reduce so to reduce the k less than or equal to total we'll take model of k with the total then we have taken the 2D matrix answer and then in that what we'll do is we are taking the older index we are taking the uh current value of the cell then convert that value to the 1D index and then after converting the cell value I comma j to 1d index What we'll do is we'll rotate we'll simulate the rotation. So we'll get the new index after rotation and then we'll convert that new index from 1D to back to 2D and then we'll store the current answer to the new position and this will repeat for all the elements and at the end we'll get our final uh rotated or shifted array. Right? So I hope I'm able to explain you the solution properly. So if you like the video, please make sure to like, share and subscribe the channel. Thank you.