Rotate Image - Matrix - Leetcode 48
Ғылым және технология
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/rotate-m...
0:00 - Read the problem
3:25 - Drawing explanation
9:55 - Coding explanation
leetcode 48
This question was identified as a microsoft interview question from here: github.com/xizhengszhang/Leet...
#microsoft #matrix #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.
Пікірлер: 284
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
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!
@sidkapoor9085
2 жыл бұрын
I found it way easier, almost trivial when I stopped looking at the "2D matrix" and just at the input and output lists.
@caniaccombo123
2 жыл бұрын
@@sidkapoor9085 mind blown
@markomekjavic
2 жыл бұрын
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!
@huansir1922
Жыл бұрын
@@markomekjavic yes,coming up with the double pointer approach , it seems hard
@princeanthony8525
Жыл бұрын
Same here.
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.
@almasmirzakhmetov8590
2 жыл бұрын
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
@Rahul-pr1zr
2 жыл бұрын
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.
@333jjjjjj
2 жыл бұрын
@@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.
@peterpace3379
2 жыл бұрын
@@333jjjjjj for me it was a whole year ago lmao
@przemysawpobrotyn1195
2 жыл бұрын
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 ;)
Just got an offer at amazon. Your videos rock and helped me out so much!
@NeetCode
2 жыл бұрын
Congratulations 🎉
This is the best explanation for this problem. Crystal clear visualization, elegant code. Great job. Thank you so much for posting!
@NeetCode
2 жыл бұрын
Happy it was helpful! :)
Bro what an structured approach . Really loved your way of teaching man! You made it look so easy.
@NeetCode
2 жыл бұрын
Thanks!
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 ) ...
@suraj8092
2 жыл бұрын
Good luck!
This is the best explanation of this problem so I've found. Thank you so much for the content! Keep up the good work 👏
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!
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!
I really like the way u handled minimizing the temp variable swap. very well explained. Thank you so much.
Best explanation one could ever give for a problem!!!. Thank you for the effort and time you are putting into making all these videos.
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.
These videos are great, this one in particular is perfect. I struggled with this a lot until I checked out this video. Awesome stuff!
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.
@jim5621
Жыл бұрын
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!
@brainmaxxing1
10 ай бұрын
@@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!
This is a beautiful way to write the code for this tricky problem. Kudos!!
thanks a lot, great explanation! i stopped my leetcode subscription , now i am just watching your videos and solving question.
Thanks for the details and it is really easier to understand the concept with your good variable naming convention.
This is a freaking amazing explanation. Thank you so much for sharing!
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.
Thank you so much for the straightforward and clear answer!
wow this explanation was so clear and the code was so clean!!
This is a very intuitive explanation. Thanks so much!!
Beautiful solution, great explanation. Thank you so much.
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.
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!
Good work with comments and simplicity!
This is super useful, thanks for the great work!
Awesome Explanation. Just loved it. Keep up the good work :)
Cleanest explanation I have ever seen. Thank you!
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
Excellent article. Keep'em coming!
I thought this was a very though problem but you made it so easy for me. Thank you!
The best explanation by far of the layer rotation method. Damn it. The best!!
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
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.
Thanks for posting, this is great!
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]
made it look like so simple, great explanation
Very nice explanation. Thanks NeetCode!
Wow what an amazing explanation. Thank you !
Perfect explanation! Thank you!
Your code was really elegant. Well done
Very clearly explained, thank you
my ego has made me attempt this problem almost 3 hours - thank you for this clean explanation!
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 😁😊
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 :)
@user-xg2wj4dy5f
Жыл бұрын
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
Thank you so much. You're the best.
This is the best explanation!!
Knew the O(2*n^2) solution using transpose followed by inversion, thanks for this great one pass solution.
Good, explanation, improoving steps ... really golden pedagogical
Another great explanation my dude !
Thanks for such a clear explanation.
"This is still a square if you tilt your head enough" - that got me laughing harder than it should have
love it. thank you!
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 { 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 { 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--; } }
Your explanation is so good
Nice, explanation. I thought the same thing but got thrown off on how to get the indexes
Thanks for this explanation. Really liked it.
@NeetCode
2 жыл бұрын
Thank you so much!! Glad it was helpful!
I really wish I had such clear approach
Mans went into god mode swapping the elements in reverse
WOW, really neat!!
You really are the Bob Ross of LeetCode XD
Great explanation
Great explanation!!!
Best of the best solution!
Nice, thanks for that
thank you. this problem has been bugging me, i figured out how to rotate the image but couldn't implement it properly.
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?
Hey. Thank you for the explanation. Query: In your drawing, you portray the bottom pointer moving up and the top pointer moving down, so it's kinda confusing for me because in your code you write 'bottom - i' and 'top + i'. Mind explaining this distinction?
Thank You Brother for this amazing video.............🙏🙏🙏🙏🙏🙏
Beautiful code~
very intuitive
Your explanation is very clear and I understand how it works. However, when I try it on leetcode it says my time limit is exceeded. Would you have any reason for why that would be the case.
fantastic teacher!
awesome explanation.. thanks (Y)
You are so genius!!
Awesome !!!!
This is really a pure math problem. rotating a cell 90 degree, the index/coordinate change is from (x,y) -> (y, n-1-x).
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 for (let j = i; j [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]; } } // Reverse each row for (let i = 0; i matrix[i].reverse(); } }
Cool beans dude!
Thanks for the clear explanation. I can understand it while I am in a food coma. lol
amazing !
Could you provide a C++ solution? The C++ approach on your website appears to be a direct copy from LeetCode, which differs from the demonstration in this video
video is so helpful.
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
Dude you are amazing
@NeetCode
Жыл бұрын
Thank you 🙏
beautiful code
as usual, you made it easy man
I hope you realise that you have a gift in explaining difficult concepts
Thanks!
This video is so so so (X100) much better than the leetcode's solutions on this problem.
you are awesome!
small correction, in the for loop, at the range function it should be range(r) not range(r-1) for python3
@rohatgiy
2 жыл бұрын
bro it’s an L
hi neetcode, i have a question, how to rotate matrix 45 degrees so the matrix size will increase, i trying to make the solution and now i want to give up (i have tried straight 5 hours btw). Can you make this solution a video pls.
genius solution!
After playing around with matrices, this question was a cake walk.
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