This is a clear explanation, but definitely still not the simplest. For me, the most straightforward method is to transpose the matrix and reverse each row. The code is simple and short. #transpose for row in range(len(matrix)): for col in range(row,len(matrix)): temp = matrix[row][col] matrix[row][col] = matrix[col][row] matrix[col][row] = temp #reverse for row in matrix: row.reverse() Accepted by leetcode.
excellent solution. By the way your solution is based on rotation matrix, right? For 90 degree, we have (x,y) -> (y,x) en.wikipedia.org/wiki/Rotation_matrix
I have another solution in similar vein. I came up with it by eyeballing the leetcode provided input/output samples and noticing that the firs element of the last row of the input is the first element of the first row of the output, the second element of the last row of the input is the first element of the second row of the output etc. thus n = len(matrix) for row in matrix[::-1]: for i in range(n): element = row.pop(0) matrix[i].append(element) also does the job ;)
This has been one of the toughest problems for me. Very hard to visualize and always used to make mistakes even after multiple attempts. The way that you explained the approach is THE BEST. You made it so crystal clear in visualizing the solution. Thank you so much!
I honestly think this is a Hard problem when it comes to implementation.. you can see the idea but coming up with the double pointer approach and a loop, thats a different story!
Thanks a lot for the content mate! No offence to others but I really like your clear accent and structured material which is easy to follow. Hope you keep up posting!
Although this is a good way to do it, I found my way to be a bit simpler once you understand matrix manipulation. Rotating a matrix by 90⁰ is equivalent to flipping the matrix diagonally and then flipping it vertically. First try it out with paper, and once u get it, it's really easy. It doesn't save runtime or anything, but I find it easier in terms of code than to move 4 things at a time layer by layer.
Brilliant idea. But this solution takes 2x time since you need to loop through the matrix twice. But the time complexity is still O(n) though. Good thinking!
@@jim5621 "This solution takes 2x time" isn't actually true. Because of things like cache locality, where the elements that are in the same row will be closer to operate on for the CPU, it's not possible to say that the element-wise method is faster. The profiling method actually worked about 25% faster from tests on my computer!
I gotta say your videos are amazing. I've been grinding LC for the past 3 weeks, I went from struggling to solve even 1 question on the weekly leetcode contest to solving 2 - 3 questions each week. Thank you so much. I've also and will always share your videos and excel sheet on reddit whenever people ask for leetcode tips. Oh and its abit late but congrats on the Google offer! I hope to one day get into google as well or any other company tbh ( my current tech job kinda blows ) ...
Have been struggling with coming up with an notion of using boundaries and using that i variable. Neet explanations for the neet code to write. Thanks for adding this.
I cant explain you how much this channel helps me !! Other channels just tell the transpose method which is not so intuitive, you always tell solutions which I can think in future in real interviews and exams. Thanks a lot Neetcode !! Keep up the good work man
Amazing solution and explanaition! I spent about 2 hours trying to understand leetcode "Rotate group of 4" solution - but no luck. Here 15 minutes - and it's clear.
Great approach! Here you can see if you are confused with variable naming I have used some easy to understand names.Approach is still the same. void rotate(vector &matrix) { int size = matrix.size(); int startRow = 0; int startColumn = 0; int endRow = matrix.size() - 1; int endColumn = matrix.size() - 1; while (startRow < endRow && startColumn < endColumn) { int current_column_for_start_row = startColumn; int current_row_for_end_Column = startRow; int current_column_for_end_row = endColumn; int current_row_for_start_column = endRow; int current_size = endColumn - startColumn; for (int i = 0; i < current_size; i++) { int temp = matrix[startRow][current_column_for_start_row]; matrix[startRow][current_column_for_start_row] = matrix[current_row_for_start_column][startColumn]; matrix[current_row_for_start_column][startColumn] = matrix[endRow][current_column_for_end_row]; matrix[endRow][current_column_for_end_row] = matrix[current_row_for_end_Column][endColumn]; matrix[current_row_for_end_Column][endColumn] = temp; current_column_for_start_row++; current_row_for_end_Column++; current_column_for_end_row--; current_row_for_start_column--; }
Your videos are excellent. You do a great job of being super clear! I often come here to Neetcode to see if you have the solution as it is better than the official explanation. Keep up the great work!
No doubt I love your simple algos but this one can be done in a much simpler way which is to reverse the matrix row wise and then swapping the elements like we do for a transpose. Kudos to the great work you do :)
But to do that you will have to create another matrix which is the copy of the Matrix which is to be transposed and that is against the constraints of the question you have to work in the same Matrix
Great explanation, however if you recalled from Linear Algebra, this is basically transpose the matrix so (row,col) becomes (col,row). So here's a shorter solution in Python rows = len(matrix) matrix.reverse() #Reverse the matrix for r in range(rows): for c in range(r,rows): matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c] #Transpose
Great content Bro :) Solution in Java: class Solution { public void rotate(int[][] matrix) { int n = matrix.length; int right=n-1, left=0; //neetcode solution video while(left
@theraplounge because as you enter in the inner loops the offset, or the amout that you have to add/subtract for the rotation decreases. in the video for the outer matrix the offset can be as much as 2, but in the inner matrix that offset is 0.
While the LeetCode problem doesn't want the cheat solution, I tried it anyway and do the following code. def rotate(self, matrix: List[List[int]]) -> None: mat = list(zip(*matrix[::-1])) for j in range(len(matrix)): for i in range(len(matrix[0])): matrix[j][i] = mat[j][i] This code performs almost as fast as the solution with a caveat that it uses more memory.
Easier solution for nXn matrix! Neetcode solution may be better suited for nXm matrix. function rotate(matrix: number[][]): void { const n = matrix.length; // Transpose the matrix, starting from i = 1 for (let i = 1; i < n; i++) { for (let j = i; j < n; j++) { [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]; } } // Reverse each row for (let i = 0; i < n; i++) { matrix[i].reverse(); } }
Perfect Solution. When I first read the solution in the Cracking the coding interview book, I spent quite a lot of time and still could not understand it. You really simplified the logic which is so much easier to follow! Great Job, man
There a very easy way to do this. First transpose the matrix, which is just flipping along a diagonal in-place. Then reflect vertically, which is another simple in-place swap.
I am thinking about the same. But the problem is we don't know if this is allowed, at least for the purpose of what this question is examining. If this is allowed then you can also use the 2D rotation matrix too.
You know you can just swap instead of using a temporary. Walk through it: Swap TL with TR Swap TL with BR Swap TL with BL Shazam, the corners are rotated and aux space is O(0).
@@trongthuong9581 There are two common methods and one other method that is CPU dependent: A) XOR swap: x ^= y y ^= x x ^= y B) Mathematical swap: x += y y = x - y x -= y C) x86 and x64 CPUs have the XCHG instruction, but it's likely to have the same performance as the other methods. Theoretically it would be faster since it can target a memory value directly, but doing so causes the CPU to lock all cores for synchronization, which is a massive performance hit. Operating just on registers, it has about 3 cycles of latency, which is similar to the XOR and mathematical methods.
It's possible to do this without any extra memory at all. Suppose you have variables x and y. You can swap them like this y=y+x x=y-x y=y-x This is all you need to transpose a matrix and to swap columns or rows. This rotation is just a transposition followed by inverting the order of the rows.
You don't need 'top', 'bottom', 'left' and 'right' mambo jumbo! Simplified transformation for clockwise rotation of [ X, Y ] is: [ X, Y ] => [ Y, abs(X - len(matrix) - 1) ] ...and for counterclockwise: [ X, Y ] => [ abs(Y - len(matrix) - 1), X ] i.e. (switch coordinates and replace one with the absolute value of itself minus the length of the matrix minus 1) Do all transformations from [ 0, 0 ] using TEMP variable, then walk diagonally toward the center... [ 1, 1 ], [ 2, 2 ], ...
Just to point out: whenever you see a 2D, 3D or nD rotation or translation challenge, you know there is ONE rule that works for all the nodes. There are no special cases in rotation nor in translation. Always try to find the rule instead of breaking the matrix into small pieces -> i.e. more challenges.
The guys talking about transpose mean this: Geometrically, rotation of the plane by 90 degrees is equivalent to flipping about the diagonal line y=-x and then flipping about the y-axis. That's why this works.
Apparently you can rotate by transposing the matrix and then flipping each row. I've seen that solution be better than the way you illustrated here I'm assuming because it's more cache friendly in the flip phase.
Since its python you can just do def rotate(self, matrix: List[List[int]]) -> None: n = len(matrix) l, r = 0, n - 1 while l < r: top, bottom = l, r for i in range(r - l): ( matrix[top + i][r], matrix[top][l + i], matrix[bottom - i][l], matrix[bottom][r - i] ) = ( matrix[top][l + i], matrix[bottom - i][l], matrix[bottom][r - i], matrix[top + i][r] ) r -= 1 l += 1 So theres no need for a temp variable, in that case we also wouldnt have to care about doing it in reverse. But I think readablitiy suffers a little
An even better solution to consider: n = len(matrix) # Transpose Matrix for i in range(n): for j in range(i, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
@@brainmaxxing1 Sure, but the TC of that solution is obviously much worse. For that solution theres no need for the second for loop either: n = len(matrix) for row in range(n): for col in range(row + 1, n): matrix[col][row], matrix[row][col] = matrix[row][col], matrix[col][row] matrix[row].reverse()
The time complexity of both solutions is the same, O(n^2). You do more 'operations' but the performance is actually better in my testing (somehow because of how the computer handles the more common operations of reversing a row and transposing a matrix) My notebook testing all 3 colab.research.google.com/drive/1laaMa1XLalAsShcoqENbbD5peb-PdCHo#scrollTo=QSThsieXZiCO Also nice on removing the second loop, that does speed it up.
literally my go to channel..well was it really asked by microsoft?...I solved it by taking its transpose and then reversing it which is in place but needs two traversal
@@markvaldez526 range(l, r) doesn't work because we are iterating r - l times, not from l to r. For example, if l = 5, and r = 10, we need to run our for loop 5 times starting index from 0, 1, 2, 3, and 4 NOT from 5, 6, 7, 8, 9 which would be the case if we do range(5, 10).
Very well explained, but i spotted one line which could be shifted up. Line 10 can be put before the for loop isnt it ? no need to initialize it on every loop
Great video. Just one question - why are the elements replaced in a counterclockwise manner? What benefit does it have over the more intuitive way of just replacing it clockwise?
The explanation was awesome and helpful to understand the problem effectively. I was waiting to see the final input output but nevertheless the code is correct so i guess i will write and check myself 😁😊
Great explanation, does anyone know why the range has to be range(right- left) instead of range(left,right)? The range(left,right) works on many of the smaller test cases but does not work on many of the harder ones. Help!
Chances are , you will not be able to think of a solution such as the second one (the one that stores only 1 variable). It's better to practise for the solution for the first one (the one that stores 4 different variables).
I find the standard rotation technique to be pretty frustrating to think about. Instead ive found its easier to invert the values on the diagonal then reverse the rows.
I found more two approaches to this, First one is to reverse the image and then transpose the resulting matrix (Easier). Other approach is to do this matrix[:] = zip(*matrix[::-1]) I don't really understand what's happening here so if someone understands, please do tell :) Thanks!
This shows me how many people in the comments don't even try the solution themselves. I tried the solution in this video on leetcode and it doesn't pass the test cases.
Here is a js solution const rotate = (matrix) => { let left = 0; // number of columns - 1, // also think, actual position of right let right = matrix.length - 1;
while (left < right) { for (let i = 0; i < right - left; i++) { let top = left; let bottom = right;
} left++; right--; } }; yes I know, py and JS are about as close to languages as you can get but for anyone new or may not understand the small differences between py and JS, here is your answer. NeetCode, thank you, your explanation was thorough and also less than 15 minutes which is great.
The explanation was amazing. I find subtracting i a little confusing. Though dry run help me understand how it works. How do I remember it when I code?
I was clicked and closed this question several times and today I finished watching it so it's WOW that now I understand it and it's easy for me 🤣Thanks!
class Solution(object): def rotate(self, matrix): """ :type matrix: List[List[int]] :rtype: None Do not return anything, modify matrix in-place instead. """ n = len(matrix[0]) for i in range(n): for j in range(i,n): tmp = matrix[i][j] matrix[i][j] = matrix[j][i] matrix[j][i] = tmp for i in range(n): matrix[i].reverse()
I took a temp array, copied all columns into the rows of the temp array but in reverse order, finally, I iterated the temp array and replaced matrix[row] = temp_array[row]
It will flip but not rotate it. Also, it doesn't follow the rule not allowing a copy of the grid. I'm confident that's right by l but I didn't run the code
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
This is a clear explanation, but definitely still not the simplest. For me, the most straightforward method is to transpose the matrix and reverse each row.
The code is simple and short.
#transpose
for row in range(len(matrix)):
for col in range(row,len(matrix)):
temp = matrix[row][col]
matrix[row][col] = matrix[col][row]
matrix[col][row] = temp
#reverse
for row in matrix:
row.reverse()
Accepted by leetcode.
excellent solution. By the way your solution is based on rotation matrix, right?
For 90 degree, we have (x,y) -> (y,x)
en.wikipedia.org/wiki/Rotation_matrix
How do you even get the idea to transpose and then reverse? I agree that implementation is easier but the idea doesn't seem that simple.
@@Rahul-pr1zr You need to recall it from your linear algebra class. Good luck if that was more than a few months ago or never.
@@333jjjjjj for me it was a whole year ago lmao
I have another solution in similar vein. I came up with it by eyeballing the leetcode provided input/output samples and noticing that the firs element of the last row of the input is the first element of the first row of the output, the second element of the last row of the input is the first element of the second row of the output etc. thus
n = len(matrix)
for row in matrix[::-1]:
for i in range(n):
element = row.pop(0)
matrix[i].append(element)
also does the job ;)
This has been one of the toughest problems for me. Very hard to visualize and always used to make mistakes even after multiple attempts. The way that you explained the approach is THE BEST. You made it so crystal clear in visualizing the solution. Thank you so much!
I found it way easier, almost trivial when I stopped looking at the "2D matrix" and just at the input and output lists.
@@sidkapoor9085 mind blown
I honestly think this is a Hard problem when it comes to implementation.. you can see the idea but coming up with the double pointer approach and a loop, thats a different story!
@@markomekjavic yes,coming up with the double pointer approach , it seems hard
Same here.
Just got an offer at amazon. Your videos rock and helped me out so much!
Congratulations 🎉
Hi hope you are doing good
Can you please guide me how's your preparation looks like
Thanks a lot for the content mate! No offence to others but I really like your clear accent and structured material which is easy to follow. Hope you keep up posting!
Bro what an structured approach . Really loved your way of teaching man! You made it look so easy.
Thanks!
This is the best explanation for this problem. Crystal clear visualization, elegant code. Great job. Thank you so much for posting!
Happy it was helpful! :)
Although this is a good way to do it, I found my way to be a bit simpler once you understand matrix manipulation. Rotating a matrix by 90⁰ is equivalent to flipping the matrix diagonally and then flipping it vertically. First try it out with paper, and once u get it, it's really easy. It doesn't save runtime or anything, but I find it easier in terms of code than to move 4 things at a time layer by layer.
Brilliant idea. But this solution takes 2x time since you need to loop through the matrix twice.
But the time complexity is still O(n) though. Good thinking!
@@jim5621 "This solution takes 2x time" isn't actually true. Because of things like cache locality, where the elements that are in the same row will be closer to operate on for the CPU, it's not possible to say that the element-wise method is faster.
The profiling method actually worked about 25% faster from tests on my computer!
I gotta say your videos are amazing. I've been grinding LC for the past 3 weeks, I went from struggling to solve even 1 question on the weekly leetcode contest to solving 2 - 3 questions each week. Thank you so much. I've also and will always share your videos and excel sheet on reddit whenever people ask for leetcode tips. Oh and its abit late but congrats on the Google offer!
I hope to one day get into google as well or any other company tbh ( my current tech job kinda blows ) ...
Good luck!
Thank you. Best explanation without having to deal with 2 for loops with i, j or recursion and all other BS to be worried about.
This is so elegant. Have solved multiple of 2d array problems but never thought of accessing the rows literally by [bottom[[R] and [top][L]
Best explanation one could ever give for a problem!!!. Thank you for the effort and time you are putting into making all these videos.
Have been struggling with coming up with an notion of using boundaries and using that i variable. Neet explanations for the neet code to write. Thanks for adding this.
I cant explain you how much this channel helps me !! Other channels just tell the transpose method which is not so intuitive, you always tell solutions which I can think in future in real interviews and exams. Thanks a lot Neetcode !! Keep up the good work man
This code makes the problem look way easier than it is! Love the code and explanation.
This is really a pure math problem. rotating a cell 90 degree, the index/coordinate change is from (x,y) -> (y, n-1-x).
This is the best explanation of this problem so I've found. Thank you so much for the content! Keep up the good work 👏
I really like the way u handled minimizing the temp variable swap. very well explained. Thank you so much.
thanks a lot, great explanation!
i stopped my leetcode subscription , now i am just watching your videos and solving question.
Amazing solution and explanaition! I spent about 2 hours trying to understand leetcode "Rotate group of 4" solution - but no luck. Here 15 minutes - and it's clear.
Great approach! Here you can see if you are confused with variable naming I have used some easy to understand names.Approach is still the same.
void rotate(vector &matrix)
{
int size = matrix.size();
int startRow = 0;
int startColumn = 0;
int endRow = matrix.size() - 1;
int endColumn = matrix.size() - 1;
while (startRow < endRow && startColumn < endColumn)
{
int current_column_for_start_row = startColumn;
int current_row_for_end_Column = startRow;
int current_column_for_end_row = endColumn;
int current_row_for_start_column = endRow;
int current_size = endColumn - startColumn;
for (int i = 0; i < current_size; i++)
{
int temp = matrix[startRow][current_column_for_start_row];
matrix[startRow][current_column_for_start_row] = matrix[current_row_for_start_column][startColumn];
matrix[current_row_for_start_column][startColumn] = matrix[endRow][current_column_for_end_row];
matrix[endRow][current_column_for_end_row] = matrix[current_row_for_end_Column][endColumn];
matrix[current_row_for_end_Column][endColumn] = temp;
current_column_for_start_row++;
current_row_for_end_Column++;
current_column_for_end_row--;
current_row_for_start_column--;
}
startRow++;
startColumn++;
endRow--;
endColumn--;
}
}
This is a beautiful way to write the code for this tricky problem. Kudos!!
I must've have tried to understand this problem atleast 10 times and always failing to remember it. I now know I will never forget it! Thanks!
Mans went into god mode swapping the elements in reverse
Your videos are excellent. You do a great job of being super clear! I often come here to Neetcode to see if you have the solution as it is better than the official explanation. Keep up the great work!
wow this explanation was so clear and the code was so clean!!
This is a freaking amazing explanation. Thank you so much for sharing!
No doubt I love your simple algos but this one can be done in a much simpler way which is to reverse the matrix row wise and then swapping the elements like we do for a transpose.
Kudos to the great work you do :)
But to do that you will have to create another matrix which is the copy of the Matrix which is to be transposed and that is against the constraints of the question you have to work in the same Matrix
Great explanation, however if you recalled from Linear Algebra, this is basically transpose the matrix so (row,col) becomes (col,row). So here's a shorter solution in Python
rows = len(matrix)
matrix.reverse() #Reverse the matrix
for r in range(rows):
for c in range(r,rows):
matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c] #Transpose
small correction, in the for loop, at the range function it should be range(r) not range(r-1) for python3
bro it’s an L
I did this in one line 😎 which beats 97%
matrix[:] = list(zip(*matrix[::-1]))
These videos are great, this one in particular is perfect. I struggled with this a lot until I checked out this video. Awesome stuff!
I thought this was a very though problem but you made it so easy for me. Thank you!
Great content Bro :)
Solution in Java:
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
int right=n-1, left=0;
//neetcode solution video
while(left
@theraplounge because as you enter in the inner loops the offset, or the amout that you have to add/subtract for the rotation decreases. in the video for the outer matrix the offset can be as much as 2, but in the inner matrix that offset is 0.
Thanks. I was looking for it.
Thanks for the details and it is really easier to understand the concept with your good variable naming convention.
Cleanest explanation I have ever seen. Thank you!
While the LeetCode problem doesn't want the cheat solution, I tried it anyway and do the following code.
def rotate(self, matrix: List[List[int]]) -> None:
mat = list(zip(*matrix[::-1]))
for j in range(len(matrix)):
for i in range(len(matrix[0])):
matrix[j][i] = mat[j][i]
This code performs almost as fast as the solution with a caveat that it uses more memory.
The best explanation by far of the layer rotation method. Damn it. The best!!
my ego has made me attempt this problem almost 3 hours - thank you for this clean explanation!
"This is still a square if you tilt your head enough" - that got me laughing harder than it should have
Easier solution for nXn matrix! Neetcode solution may be better suited for nXm matrix.
function rotate(matrix: number[][]): void {
const n = matrix.length;
// Transpose the matrix, starting from i = 1
for (let i = 1; i < n; i++) {
for (let j = i; j < n; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
// Reverse each row
for (let i = 0; i < n; i++) {
matrix[i].reverse();
}
}
This is a very intuitive explanation. Thanks so much!!
Thank you so much for the straightforward and clear answer!
Good, explanation, improoving steps ... really golden pedagogical
Perfect Solution. When I first read the solution in the Cracking the coding interview book, I spent quite a lot of time and still could not understand it. You really simplified the logic which is so much easier to follow! Great Job, man
Knew the O(2*n^2) solution using transpose followed by inversion, thanks for this great one pass solution.
There a very easy way to do this. First transpose the matrix, which is just flipping along a diagonal in-place. Then reflect vertically, which is another simple in-place swap.
I am thinking about the same. But the problem is we don't know if this is allowed, at least for the purpose of what this question is examining. If this is allowed then you can also use the 2D rotation matrix too.
Just saw other comments. This is allowed. I am happy now.
@@Qxismylife using a 2D rotation matrix may not be inplace as you need extra space for the matrix. Transpose and flip can both be done inplace
You know you can just swap instead of using a temporary.
Walk through it:
Swap TL with TR
Swap TL with BR
Swap TL with BL
Shazam, the corners are rotated and aux space is O(0).
How can u perform swap without temp variable xD
@@trongthuong9581 There are two common methods and one other method that is CPU dependent:
A) XOR swap:
x ^= y
y ^= x
x ^= y
B) Mathematical swap:
x += y
y = x - y
x -= y
C) x86 and x64 CPUs have the XCHG instruction, but it's likely to have the same performance as the other methods. Theoretically it would be faster since it can target a memory value directly, but doing so causes the CPU to lock all cores for synchronization, which is a massive performance hit. Operating just on registers, it has about 3 cycles of latency, which is similar to the XOR and mathematical methods.
It's possible to do this without any extra memory at all.
Suppose you have variables x and y. You can swap them like this
y=y+x
x=y-x
y=y-x
This is all you need to transpose a matrix and to swap columns or rows. This rotation is just a transposition followed by inverting the order of the rows.
Good work with comments and simplicity!
Beautiful solution, great explanation. Thank you so much.
You don't need 'top', 'bottom', 'left' and 'right' mambo jumbo!
Simplified transformation for clockwise rotation of [ X, Y ] is:
[ X, Y ] => [ Y, abs(X - len(matrix) - 1) ]
...and for counterclockwise:
[ X, Y ] => [ abs(Y - len(matrix) - 1), X ]
i.e. (switch coordinates and replace one with the absolute value of itself minus the length of the matrix minus 1)
Do all transformations from [ 0, 0 ] using TEMP variable, then walk diagonally toward the center... [ 1, 1 ], [ 2, 2 ], ...
Just to point out:
whenever you see a 2D, 3D or nD rotation or translation challenge, you know there is ONE rule that works for all the nodes. There are no special cases in rotation nor in translation. Always try to find the rule instead of breaking the matrix into small pieces -> i.e. more challenges.
The guys talking about transpose mean this: Geometrically, rotation of the plane by 90 degrees is equivalent to flipping about the diagonal line y=-x and then flipping about the y-axis. That's why this works.
Apparently you can rotate by transposing the matrix and then flipping each row. I've seen that solution be better than the way you illustrated here I'm assuming because it's more cache friendly in the flip phase.
Amazing approach - very structured! and of course backed by great visualization!! You've got a subscriber, just based on this!! :)
please continue to make more videos, this channel is pure gold
Like the approach. But it's tedious to really remember and do it. I like the transposing and reversing using a 2 ptr approach to do this.
Perfect explanation! Thank you!
Nice, explanation. I thought the same thing but got thrown off on how to get the indexes
Since its python you can just do
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
l, r = 0, n - 1
while l < r:
top, bottom = l, r
for i in range(r - l):
(
matrix[top + i][r],
matrix[top][l + i],
matrix[bottom - i][l],
matrix[bottom][r - i]
) = (
matrix[top][l + i],
matrix[bottom - i][l],
matrix[bottom][r - i],
matrix[top + i][r]
)
r -= 1
l += 1
So theres no need for a temp variable, in that case we also wouldnt have to care about doing it in reverse.
But I think readablitiy suffers a little
An even better solution to consider:
n = len(matrix)
# Transpose Matrix
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Reverse Matrix
for row in matrix:
row.reverse()
@@brainmaxxing1 Sure, but the TC of that solution is obviously much worse.
For that solution theres no need for the second for loop either:
n = len(matrix)
for row in range(n):
for col in range(row + 1, n):
matrix[col][row], matrix[row][col] = matrix[row][col], matrix[col][row]
matrix[row].reverse()
The time complexity of both solutions is the same, O(n^2). You do more 'operations' but the performance is actually better in my testing (somehow because of how the computer handles the more common operations of reversing a row and transposing a matrix)
My notebook testing all 3 colab.research.google.com/drive/1laaMa1XLalAsShcoqENbbD5peb-PdCHo#scrollTo=QSThsieXZiCO
Also nice on removing the second loop, that does speed it up.
literally my go to channel..well was it really asked by microsoft?...I solved it by taking its transpose and then reversing it which is in place but needs two traversal
Great explanation! For some weird reason, for loop with range(l, r) does not pass all test cases!
My code isn't passing either...
@@markvaldez526 range(l, r) doesn't work because we are iterating r - l times, not from l to r. For example, if l = 5, and r = 10, we need to run our for loop 5 times starting index from 0, 1, 2, 3, and 4 NOT from 5, 6, 7, 8, 9 which would be the case if we do range(5, 10).
@@shivaacharya7247 thanks for explaining. Cleared it up for me!
Very nice explanation. Thanks NeetCode!
After playing around with matrices, this question was a cake walk.
I hope you realise that you have a gift in explaining difficult concepts
Your code was really elegant. Well done
There is no way I could have figured this out myself. Not even if they give me a million years time.
1) Invert the order of the rows
2) Transpose
Your explanation is so good
Very well explained, but i spotted one line which could be shifted up.
Line 10 can be put before the for loop isnt it ? no need to initialize it on every loop
made it look like so simple, great explanation
Wow what an amazing explanation. Thank you !
I really wish I had such clear approach
Great video. Just one question - why are the elements replaced in a counterclockwise manner? What benefit does it have over the more intuitive way of just replacing it clockwise?
Awesome Explanation. Just loved it. Keep up the good work :)
The explanation was awesome and helpful to understand the problem effectively. I was waiting to see the final input output but nevertheless the code is correct so i guess i will write and check myself 😁😊
Great explanation, does anyone know why the range has to be range(right- left) instead of range(left,right)? The range(left,right) works on many of the smaller test cases but does not work on many of the harder ones. Help!
that's because we always want to start the i with 0.
let's take (2, 4) as an example
range(2,4) return 2,3
but range(4-2) return 0, 1
Chances are , you will not be able to think of a solution such as the second one (the one that stores only 1 variable). It's better to practise for the solution for the first one (the one that stores 4 different variables).
I find the standard rotation technique to be pretty frustrating to think about. Instead ive found its easier to invert the values on the diagonal then reverse the rows.
Thanks for such a clear explanation.
I found more two approaches to this, First one is to reverse the image and then transpose the resulting matrix (Easier). Other approach is to do this matrix[:] = zip(*matrix[::-1]) I don't really understand what's happening here so if someone understands, please do tell :) Thanks!
This video is so so so (X100) much better than the leetcode's solutions on this problem.
This shows me how many people in the comments don't even try the solution themselves.
I tried the solution in this video on leetcode and it doesn't pass the test cases.
I tried it, it passes.
Thanks for the clear explanation. I can understand it while I am in a food coma. lol
thank you. this problem has been bugging me, i figured out how to rotate the image but couldn't implement it properly.
Here is a js solution
const rotate = (matrix) => {
let left = 0;
// number of columns - 1,
// also think, actual position of right
let right = matrix.length - 1;
while (left < right) {
for (let i = 0; i < right - left; i++) {
let top = left;
let bottom = right;
let topLeft = matrix[top][left + i];
matrix[top][left + i] = matrix[bottom - i][left];
matrix[bottom - i][left] = matrix[bottom][right - i];
matrix[bottom][right - i] = matrix[top + i][right];
matrix[top + i][right] = topLeft;
}
left++;
right--;
}
};
yes I know, py and JS are about as close to languages as you can get but for anyone new or may not understand the small differences between py and JS, here is your answer. NeetCode, thank you, your explanation was thorough and also less than 15 minutes which is great.
C# solution:
public void Rotate(int[][] matrix)
{
int n = matrix.Length;
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
Array.Reverse(matrix[i]);
}
}
Cheers!
You can transpose the matrix in place and reverse each row to achieve the same result
Thanks for this explanation. Really liked it.
Thank you so much!! Glad it was helpful!
Thanks for posting, this is great!
Thank you so much. You're the best.
The explanation was amazing. I find subtracting i a little confusing. Though dry run help me understand how it works. How do I remember it when I code?
pen and paper
I was clicked and closed this question several times and today I finished watching it so it's WOW that now I understand it and it's easy for me 🤣Thanks!
This is super useful, thanks for the great work!
Thank You Brother for this amazing video.............🙏🙏🙏🙏🙏🙏
"top" and "bottom" variables are not necessary, one could replace them by "l" and "r"
Sure, but why sacrifice readability? The difference is very small in terms of memory usage
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
n = len(matrix[0])
for i in range(n):
for j in range(i,n):
tmp = matrix[i][j]
matrix[i][j] = matrix[j][i]
matrix[j][i] = tmp
for i in range(n):
matrix[i].reverse()
I like the intuitively named variables.
I took a temp array, copied all columns into the rows of the temp array but in reverse order, finally, I iterated the temp array and replaced matrix[row] = temp_array[row]
Would this work?
for(int i = 0; i < height; i++)
for(int j = 0; j < width; j++)
rotatedImage[ j ][ width - i ] = image[ i ][ j ]
It will flip but not rotate it. Also, it doesn't follow the rule not allowing a copy of the grid. I'm confident that's right by l but I didn't run the code