Thanks. We can further improve by not using loop for reversing of row in optimal instead just use reverse after j loop is finished like this: for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { swap(mat[i][j], mat[j][i]); } reverse(mat[i].begin(), mat[i].end()); }
Great explanation. I tried to come up with my solution prior to watching the video. I used the intuition of concentric squares within the matrix. I traverse one side of each concentric square and perform three swaps for each element . Since only one side of each concentric square is traversed, the number of elements traversed is approximately 1/4(m*n) and since there are 3 swaps for each element the time complexity will be O(3/4 m*n). Using a swap counter, Striver's solution is very close to O(m*n). However, unlike Striver, I do use some extra auxiliary constant space in the form of 4 pairs of co-ordinates which I use to determine the correct placing of the elements during swapping. void rotate(vector& m) { int l = 0; int h = m.size() - 1; pair a, b, c, d;
while (l < h) { a = {l,l}; b = {l,h}; c = {h,h}; d = {h,l}; for (int i = l; i < h; i++) { swap (m[a.first][a.second], m[b.first][b.second]); swap (m[a.first][a.second], m[c.first][c.second]); swap (m[a.first][a.second], m[d.first][d.second]); a.second++; b.first++; c.second--; d.first--; } l++; h--; } }
How you elaborate on the problem and solution is unique to any other free content I have gone through. I'll surely gonna recommend your channel if somebody asks.
I did this optimal solution on my own, then came to see the solution video, this sheet building my confidence and skills little by little. (Rikon was my childhood friend. He worked for you some days back. No wonder why he praised you so much.)
I used the idea of concentric squares to solve the problem. Say, n = 6. Now the square will be of 3X3 size. You can draw a matrix to see how the outer square is of length = 6, inside it there's a square of side = 4 and inside it there's another square of side = 2. Basically each inside square is of 2 units lesser length then its outer square. We traverse from outside to inside and rotate each square one by one. For rotation, we traverse the upper side of the square and use 3 swaps for each grid. Also, the traversal is done till 2nd last grid because if you do the dry run, you'll notice that the last grid is already swapped in the first step, i.e., the corners are common between 2 given sides. The most difficult part is to deduce the co-ordinates for the replacing element. Imagine a square which you're traversing on its top side. Now, the top left element will be replaced by bottom left, bottom left by bottom right, bottom right by top right and top right by top left. It's hard to explain in a comment how I arrived at the co-ordinates but if someone wants to try this out, instead of swapping element by element, first try swapping row by row. I've attached codes for both. Basically, store the upper side of square in a temp array then replace top row with left column, replace left column with bottom row and so on. Once you understand how that's working, the co-ordinates for element by element swap is same but using lesser extra space. If someone needs a video explanation, do reply and I'll try to post a video explaining the same. // Swapping row by row: for (int i = 0; i < n/2; i++) { vector temp; for (int j = i; j < m-i; j++) temp.push_back(mat[i][j]); for (int j = m-i-1; j >= i; j--) mat[i][j] = mat[n-1-j][i]; for (int j = m-i-1; j >= i; j--) mat[n-1-j][i] = mat[n-1-i][m-1-j]; for (int j = m-i-1; j >= i; j--) mat[n-1-i][m-1-j] = mat[j][m-1-i]; for (int j = m-i-1; j >= i; j--) mat[j][m-1-i] = temp[j-i]; } // Swapping element by element int len = mat.size(); for (int i = 0; i < len/2; i++) { for (int j = i; j < (len-i-1); j++) { int temp = mat[i][j]; mat[i][j] = mat[len-1-j][i]; mat[len-1-j][i] = mat[len-1-i][len-1-j]; mat[len-1-i][len-1-j] = mat[j][len-1-i]; mat[j][len-1-i] = temp; } }
#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India.
Thanks a lot bhaiya. This time I must say you are on fire. Your explaining capability is next level, bez I had problems in understanding the matrix(index and all). But Now super clear. OP Striver Guru 🔥🔥🔥🔥
9:54 We do transpose not because we need to convert rows into column. If we have a another matrix to store then we can do it directly instead of two steps. we do it so that we can swap elements. you can't do it directly. so do the extra step
now I understood why bhai chose c++ over java because u have to write so many function in java but in c++ u have stl :( . But bro i understood the question thanku :b
Java Code: ```class Solution { public void rotate(int[][] matrix) { int n = matrix.length;
// Transpose of Matrix for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } }
// Reverse each row for (int i = 0; i < n; i++) { int left = 0, right = n - 1; while (left < right) { int temp = matrix[i][left]; matrix[i][left] = matrix[i][right]; matrix[i][right] = temp; left++; right--; } } } }```
this is how I wrote the transpose code for(int i=0; i< n ; i++){ for(int j=i; j < n; j++){ swap(matrix[i][j], matrix[j][i]); } } which is less confusing
bro this code is not optimal, because it this code u will traverse through all elements, and the code in the video is not traversing the diagonal element which reduce the time complexity
this will not work because after this loop all the element will be in actual place only and the array will be reach to its initial state because u are swapping twice the same element and so after this loop ends and there will be no change...
******* we can do by this approach here i have used the i variable to swap the value instead of iterating i+1 to n-1 class Solution { public: void rotate(vector& matrix) {int n=matrix.size(); int m=matrix[0].size(); for(int i=0;i
an approach i came up with, if you need to rotate clockwise, just swap elements at each layer anticlockwise void rotate(vector& matrix) { int n = matrix.size(); for(int i=0; i
hi, the solution provided in the sheet for java doesn't follow the same explanation, the logic is bit changed in it. Here, is the code following the explanation: class Solution { public void rotate(int[][] matrix) { int n = matrix.length, m = matrix[0].length; //Transpose for(int i =0; i
Hi bro! I came across this problem and the first two operations on my mind were transpose and reverse. As the problem requried it to be solved in O(1) space, I carefully examined if the sequence of these operations made any signifcant changes to the performance. What I did was to reverse the matrix (row-wise) first, then take a transpose. The first operation used n/2 iterations (for optimal reversing). The second operation used n*(n+1)/2 iterations (for optimal transpose). So the total number of iterations with optimization: (n(n + 1) + n)/2 = O(n^2 + n) = O(n^2) With transpose first and then reverse each row: (n(n+1) + n^2)/2 = O(n^2 + n^2) = O(n^2) It doesn't make a difference as our PCs are blazzingly fast, but I found it neat :) Thanks a lot! This series is amazing!♥♥
I thought that too. For the first loop, we still have to go through all of the rows except last one, which would be O(n). Now, for each row you go through, you will go through n - (i + 1) columns, which theoretically means you go through the later half of our matrix. This is why it is calculated as n/2. Then, when we loop through the rows and reverse them, we say we go through n rows and for each row we have to go loop through it to reverse them, which with the algorithm provided by Striver, it takes n/2. So, the answer would be in fact O(n * n/2) + O(n * n/2), which in simpler terms is O(n^2/2).
I think built the most confusing program but works lol: public void rotate(int[][] matrix) { int n = matrix.length; for (int j = 0; j < n / 2; j++) { int size = n-2; if(j != 0){ size = n-2-j; } for (int i = j; i
Tried it in a slightly different way and managed to get rid of the reverse function. Any feedback is welcome! class Solution { public void rotate(int[][] m) { int l = m.length - 1; for (int i = 0; i < Math.ceil(l/2.0); i++) { for (int j = i; j < l - i; j++) { int topLeft = m[i][j]; int topRight = m[j][l-i]; int bottomRight = m[l-i][l-j]; int bottomLeft = m[l-j][i]; m[i][j] = bottomLeft; m[j][l-i] = topLeft; m[l-i][l-j] = topRight; m[l-j][i] = bottomRight; } } } }
Please watch our new video on the same topic: ua-cam.com/video/Z0R2u6gd3GU/v-deo.html
It's a loop same video link
The way you approach the problem.......It gives me the confidence that i can also do it!!!!!💀
Timestamps pleaseee.
Let's march ahead, and create an unmatchable DSA course! ❤
Use the problem links in the description.
notes link is not visible
Love you brother, marching ahead consistently.
Thanks. We can further improve by not using loop for reversing of row in optimal instead just use reverse after j loop is finished like this:
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
swap(mat[i][j], mat[j][i]);
}
reverse(mat[i].begin(), mat[i].end());
}
Great explanation.
I tried to come up with my solution prior to watching the video. I used the intuition of concentric squares within the matrix. I traverse one side of each concentric square and perform three swaps for each element . Since only one side of each concentric square is traversed, the number of elements traversed is approximately 1/4(m*n) and since there are 3 swaps for each element the time complexity will be O(3/4 m*n). Using a swap counter, Striver's solution is very close to O(m*n).
However, unlike Striver, I do use some extra auxiliary constant space in the form of 4 pairs of co-ordinates which I use to determine the correct placing of the elements during swapping.
void rotate(vector& m)
{
int l = 0;
int h = m.size() - 1;
pair a, b, c, d;
while (l < h)
{
a = {l,l}; b = {l,h}; c = {h,h}; d = {h,l};
for (int i = l; i < h; i++)
{
swap (m[a.first][a.second], m[b.first][b.second]);
swap (m[a.first][a.second], m[c.first][c.second]);
swap (m[a.first][a.second], m[d.first][d.second]);
a.second++; b.first++; c.second--; d.first--;
}
l++; h--;
}
}
I had the same idea
TIMESTAMPS
00:49 Problem statement
2:06 Observation
2:24 Brute force approach
6:25 Brute force code
7:49 Optimized approach
14:00 pseudo code for transposition
15:01 Optimized approach code
How you elaborate on the problem and solution is unique to any other free content I have gone through. I'll surely gonna recommend your channel if somebody asks.
we can also transpose as:
for(int i=0;i
I did this optimal solution on my own, then came to see the solution video, this sheet building my confidence and skills little by little.
(Rikon was my childhood friend. He worked for you some days back. No wonder why he praised you so much.)
I used the idea of concentric squares to solve the problem. Say, n = 6. Now the square will be of 3X3 size. You can draw a matrix to see how the outer square is of length = 6, inside it there's a square of side = 4 and inside it there's another square of side = 2. Basically each inside square is of 2 units lesser length then its outer square. We traverse from outside to inside and rotate each square one by one.
For rotation, we traverse the upper side of the square and use 3 swaps for each grid. Also, the traversal is done till 2nd last grid because if you do the dry run, you'll notice that the last grid is already swapped in the first step, i.e., the corners are common between 2 given sides. The most difficult part is to deduce the co-ordinates for the replacing element. Imagine a square which you're traversing on its top side. Now, the top left element will be replaced by bottom left, bottom left by bottom right, bottom right by top right and top right by top left. It's hard to explain in a comment how I arrived at the co-ordinates but if someone wants to try this out, instead of swapping element by element, first try swapping row by row. I've attached codes for both. Basically, store the upper side of square in a temp array then replace top row with left column, replace left column with bottom row and so on. Once you understand how that's working, the co-ordinates for element by element swap is same but using lesser extra space. If someone needs a video explanation, do reply and I'll try to post a video explaining the same.
// Swapping row by row:
for (int i = 0; i < n/2; i++) {
vector temp;
for (int j = i; j < m-i; j++) temp.push_back(mat[i][j]);
for (int j = m-i-1; j >= i; j--) mat[i][j] = mat[n-1-j][i];
for (int j = m-i-1; j >= i; j--) mat[n-1-j][i] = mat[n-1-i][m-1-j];
for (int j = m-i-1; j >= i; j--) mat[n-1-i][m-1-j] = mat[j][m-1-i];
for (int j = m-i-1; j >= i; j--) mat[j][m-1-i] = temp[j-i];
}
// Swapping element by element
int len = mat.size();
for (int i = 0; i < len/2; i++) {
for (int j = i; j < (len-i-1); j++) {
int temp = mat[i][j];
mat[i][j] = mat[len-1-j][i];
mat[len-1-j][i] = mat[len-1-i][len-1-j];
mat[len-1-i][len-1-j] = mat[j][len-1-i];
mat[j][len-1-i] = temp;
}
}
I am watching in sequence, the best explanation frrrr.. SOME ONE REMIND ME TO STUDY BY LIKING THE COMMENT
#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India.
Nice explaination, the best part is that you teach how to build your mind to think in that way.....
Best optimal explaination with in depth time complexity. Great. I do by myself with rotated by anti-clockwise and clockwise both. THankyou
Thanks a lot bhaiya. This time I must say you are on fire. Your explaining capability is next level, bez I had problems in understanding the matrix(index and all). But Now super clear. OP Striver Guru 🔥🔥🔥🔥
We can also find a pattern i.e. i -> j and then j -> n-i-1
Bhaiya, apka har solutions are just too OP and easy to understand 🔥🔥
Understood.
Thank you for this amazing content. I have tried many lectures but the way you approach the problem it seems extremely easy.
best DSA sheet ever you are the god of DSA really
bro I was able to come up with the brute force myself but the optimal solution is just too good and clever 😆
I also came up with the transpose approach very happy 😁😁
very well understood, thank you for the great content ❤
Brother you are awesome. The way you give the solutions of the problems and it very helpful for me to explain whole code(dry and run).🙏🙏
9:54
We do transpose not because we need to convert rows into column.
If we have a another matrix to store then we can do it directly instead of two steps.
we do it so that we can swap elements.
you can't do it directly.
so do the extra step
now I understood why bhai chose c++ over java because u have to write so many function in java but in c++ u have stl :( . But bro i understood the question thanku :b
SDE Sheet Day 2 Problem 1 Done!
so amazing watching your videos and getting to know how one should change there mind to observe the problem.
Java Code:
```class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// Transpose of Matrix
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// Reverse each row
for (int i = 0; i < n; i++) {
int left = 0, right = n - 1;
while (left < right) {
int temp = matrix[i][left];
matrix[i][left] = matrix[i][right];
matrix[i][right] = temp;
left++;
right--;
}
}
}
}```
thanks
God bless you man
We don't need to use another loop for reverse() , we can simply add the reverse() after every inner loop ends but within outer loop.
this is how I wrote the transpose code
for(int i=0; i< n ; i++){
for(int j=i; j < n; j++){
swap(matrix[i][j], matrix[j][i]);
}
}
which is less confusing
bro this code is not optimal, because it this code u will traverse through all elements, and the code in the video is not traversing the diagonal element which reduce the time complexity
@@ast_karan128 thanks for pointing that out bro 🤜
this will not work because after this loop all the element will be in actual place only and the array will be reach to its initial state because u are swapping twice the same element and so after this loop ends and there will be no change...
Samaj aa gaya bhai. Thank you.
******* we can do by this approach here i have used the i variable to swap the value instead of iterating i+1 to n-1
class Solution {
public:
void rotate(vector& matrix)
{int n=matrix.size();
int m=matrix[0].size();
for(int i=0;i
Superb UNderstood
Understood
Thank you for this amazing lecture sir.
Bhaiya ur amazing . How can one explain with soo much perfection man. Live long and keep making videos for us . Hope to meet you soon .
Understood! Amazing explanation as always, thank you very much for your effort!!
I never thought, this question was that simple :(
Understood Striver, Thanks
Understood. Thank you Striver
an approach i came up with, if you need to rotate clockwise, just swap elements at each layer anticlockwise
void rotate(vector& matrix) {
int n = matrix.size();
for(int i=0; i
thankyou so muxh for these videos❤❤... and the problem link added is a different question, but in your dsa sheet its same
Understood!
Amazing explanation!
hi, the solution provided in the sheet for java doesn't follow the same explanation, the logic is bit changed in it.
Here, is the code following the explanation:
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length, m = matrix[0].length;
//Transpose
for(int i =0; i
Sir app bhut accha Padhte hoo.
Hi bro! I came across this problem and the first two operations on my mind were transpose and reverse. As the problem requried it to be solved in O(1) space, I carefully examined if the sequence of these operations made any signifcant changes to the performance.
What I did was to reverse the matrix (row-wise) first, then take a transpose.
The first operation used n/2 iterations (for optimal reversing).
The second operation used n*(n+1)/2 iterations (for optimal transpose).
So the total number of iterations with optimization: (n(n + 1) + n)/2 = O(n^2 + n) = O(n^2)
With transpose first and then reverse each row: (n(n+1) + n^2)/2 = O(n^2 + n^2) = O(n^2)
It doesn't make a difference as our PCs are blazzingly fast, but I found it neat :)
Thanks a lot! This series is amazing!♥♥
I wish , I would have seen this video before makemytrip interview.. Thank you for great content.
they ask to complete the func in interview or just write pseudo code
Wow sir amazing and super easy explanation ❤❤❤😊
Thank you very much brother🙇
Awesome Lecture Sir.................
Thank you for work you do. Really helpful!
thanks you sir, i easily understand how to transpose matrix inplace.
Beautifully explained.
Happy Ram Navami Everyone 🚩
Understood!
understood very well !
Thank you
Hey Striver, the problem link and the video link doesn't match in the SDE sheet, please get it updated...
for left rotate the matrix to 90 degree just reverse the columns instead of rows and done
striver so happy to learn with youuh
understood!!🙇♂
i think swap part of optimal approach take time complexity of O(N * N/2) bcz first loop is running for n times and second N/2 times
great explanation
TC for the first 2 nested for loops would be O(N*N/2) in my point of view?!
trying to pass first year of college : ( thank you : )
your dedication 🙌🙌
understood. thank you so much bro
Thank u Bhaiya Very helpFul video
Understood bhaiya!
Great Explanation❤🙇♂✨🙏
Understood bro. Thank you
understood 🚴♂
UNDERSTOOD SIR
i think the time complexity of the optimal should be O(N) * O(N/2) + O(N) * O(N/2)
How is N/2 brother i don't understand can you explain
I thought that too. For the first loop, we still have to go through all of the rows except last one, which would be O(n). Now, for each row you go through, you will go through n - (i + 1) columns, which theoretically means you go through the later half of our matrix. This is why it is calculated as n/2.
Then, when we loop through the rows and reverse them, we say we go through n rows and for each row we have to go loop through it to reverse them, which with the algorithm provided by Striver, it takes n/2.
So, the answer would be in fact O(n * n/2) + O(n * n/2), which in simpler terms is O(n^2/2).
Understood, thank you.
Optimal Solution:
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length - 1;
int k = 0;
while(k < n){
for(int i = k ; i < n ; i++){
int temp1 = matrix[i][n];
matrix[i][n] = matrix[k][i];
int temp2 = matrix[n][n-i+k];
matrix[n][n-i+k] = temp1;
temp1 = matrix[n-i+k][k];
matrix[n-i+k][k] = temp2;
matrix[k][i] = temp1;
}
k++;
n--;
}
}
}
Understood. Thanks a lot
understood bhaiya
Understood 👍
I think built the most confusing program but works lol:
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int j = 0; j < n / 2; j++) {
int size = n-2;
if(j != 0){
size = n-2-j;
}
for (int i = j; i
Understood! Sir
Thank you sir!..
Try using slicing method
great job bro
Understood, thanks💚
Understood very well
Thank you bhaiya
understood!
understood❤
marvellous
Understood❤
UNDERSTOOD
Understood ❤
understood.
understood!
Understood.
Thank you 🙏
thankyou so much sir
Tried it in a slightly different way and managed to get rid of the reverse function. Any feedback is welcome!
class Solution {
public void rotate(int[][] m) {
int l = m.length - 1;
for (int i = 0; i < Math.ceil(l/2.0); i++) {
for (int j = i; j < l - i; j++) {
int topLeft = m[i][j];
int topRight = m[j][l-i];
int bottomRight = m[l-i][l-j];
int bottomLeft = m[l-j][i];
m[i][j] = bottomLeft;
m[j][l-i] = topLeft;
m[l-i][l-j] = topRight;
m[l-j][i] = bottomRight;
}
}
}
}
Understoooood 🔥😁
understood
please came up with string problems
Understood !!