LeetCode 48. Rotate Image (Solution Explained)
Vložit
- čas přidán 22. 09. 2019
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow My Twitter - / nicholaswwhite
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering - Věda a technologie
You are the kind of tech youtuber that I didn't know I needed.
Thank you for doing videos like these. I have been consuming them alot lately.
Highly informational!
Wow! I read some articles and tried following some examples but only after your explanation, I was able to fully understand the concept and the tricks! Thank you so so much!
Brother, Superb explanation ! Earlier I thought of the same approach but got stuck in the code and your video helped me in a perfect way.
Great explanation! I had a variant of this problem yesterday in an OA, and I didn't figure out how to rotate the square matrix. wish I had watched your video earlier lol! Keep the good videos coming!
This makes much more sense than the CTCI solution explanation!
Exactly, Much more intuitive than that layer by layer approach
but im looking for MxN matrix. this will work only for a square matrix right
@@faizyt12345 Correct -- it's possible to do on an NxM, though it cannot be done in place as the dimensions of the matrix will shift to MxN. The transpose code is similar, except it populates a new array instead of swaping. As an effect, it also needs to hit every element of the original matrix in order to do the transposition
int rows = matrix.length;
int cols = matrix[0].length;
int rotated[][] = new int[cols][rows];
for (int i = 0; i < cols; i++) {
for (int j = 0; j < rows; j++) {
rotated[i][j] = matrix[j][i];
}
}
I know this reply is 7 months late; still, I hope it helped.
@@ryebr3ad thanks after 7 months
I also came after not being able to grasp the concept from CTCI for this particular problem. 😂
great explanation. I got stuck on this one hard until I saw this video.
of all the explanations ive seen of this problem, this explanation makes the most since.
I felt stuck then I watched this video. Feel alive again!!
Thanks a lot! I watched the different solution with actual rotating, but your aproach looks more sophisticated. I think the description force you to do like this showing several matrixes with swapped rows and columns
Great! I was stuck until I found a pattern and solved it recursively. But this (your method) is way simpler.
I'll put my solution in case someone looking for a pattern.
class Solution {
public:
void rotate(vector& matrix) {
helper(matrix, matrix.size(), 0 );
}
void helper(vector& mat, int size, int start) {
if(size
I was stuck on this problem from 3days and solved on my own but this approach is much better
Awesome explanation. Thank you so much for all you do!
Oh god thanks for this solution. The two available on LeetCode solutions page and in some other videos are either complex or not explained properly. Finally got this into my head.
Another great video, Thanks, Nick!
I think that in the transpose part, you can add one condition if(i != j) because the diagonal elements don't need to be transposed.
Love it! Such an elegant solution
Thanks, man! Great Logic. It kind of reminds of Linear Algebra : )
Really Really Helpful Buddy. Spent A Lot Time On It.
Best explanation by far to this problem.
Thank you so much. This really helped me a lot.
Amazing explanation! Thank you very much
bro you are crazy man this solution is hilarious I was stuck at this for more than 4 hrs ur soln is gr8 Love from India
Excellent explanation. Thank you.
this is brilliant and doable. Thanks!
Amazing explanation, man!! Thank you. Liked and subscribed!
I'm glad I didn't waste much time thinking about the solution on my own cuz I would have never guessed this
Great Explanation and very clean code !
Made this so simple thanks!
Good explanation.Finally i understood the approach.
super easy solution bro. Thanks a ton!
Hi Nick, can we not do j=i+1 when we do the transpose?
the best solution so far!
excellent explanation and solution Nick! more video pls
Hi.. Nice explanation. Thanks for the video!! Could you please tell me how the time complexity is not O(N^2)?
thats sick thanks Nick
You can also create a matrix and multiply to get the desired result
i -row,j-column
for position i=i, j=0 - multiply i-th column with [0 0 1]
for position i=i, j=1 - multiply i-th column with [0 1 0]
for position i=i, j=2 - multiply i-th column with [1 0 0]
we can also think parameterizing the multiplication matrix as well. Size of the multiplication matrix is dependent on the size of the original matrix
Great explanation, really helped a lot. Love from India.
Great explanation, thanks
Great Explanation!!!! As always :)
Thank you Nick!!
you made it easy.....
Thanks
Nice solution!
Hi Nick, thank you so much for your videos :D Why did you set j=i if technically could be j=0 but it did not work that way :c
just awesome man just awesome
you wanna know this if you have online assessments coming up!!! Matrix diagonals and rotation comes up alot
How would you do this if it was asking for counter-clockwise? Or would you just rotate it clockwise 3 times?
Try to transpose and do a flip on a different symmetry. See if you can figure it out, it's very similar. The same idea applies to 180 flip as well.
Thanks!
dude don't forget to say , leave a like . I almost forgot to give a like.. you are the best.
I think you can set j to i+1 because you can skip over the same index values
bro thanks for everything
Thanks man
Great video❤
Thank You
Oh, man, you are awesome
great explanation only doubt how is this linear time solution if we are using 2 for loops ?? help me out please
actually he meant linear in-terms of size of entire matrix. for example if it is 3 x 3 matrix, size of matrix is 9. Here N is 9. so it takes linear time in terms of entire matrix size. think of it as a single array.
Thank you
TNX man!
Hey.. WHy do we do N/2 in the second for loop for J?
Is because when you are switching the elements from the first column to the last column, you stop midway through each row.
@@aximilian15 I understood that later. Thanks
How is this linear time? There is 2 nested loops.
Linear with respect to the dimensions of the matrix.
I LOVE sprite rotation with a Matrix!!!!!!
Your videos really are some of the clearest and cleanest on these problems that I have seen. THANKS!
Thanks bro
great vid! the time complexity of this algorithm is O(N^2) not linear tho
linear for the size of matrix.
nice vid!
thanks bruh
what if we just reverse each row in the second loop
That works too
Thank u
Good question
Same exact question in Javascript is under the "easy" category on LeetCode ?!
We can simplify the 2nd loop little better like
public void rotate(int[][] matrix) {
if (matrix == null || matrix.length
yes but its taking a little bit more memory but that's okay it looks more readable and understandable
1:50 code real fine
cool trick.
Champ!
What abt an NxM ? .ex 3x5?
You would not be able to rotate a non square matrix in place.
I feel less stupid. Thanks
The time complexity for the first nested loop is O(n^2) or more accurately O(row*col), isn't it? I'm confused why you mentioned the solution is linear time complexity. Also, whats the time complexity for the second nested loop
mytommy listen more closely I explained it pretty clearly
Linear or O(N) where N is the number of elements in the 2d array
Some people say O(M*N) or O(rows*columns) which is fine as long as you specify what you’re variables are referencing
@@NickWhite I know, I watched the video more than once. You mentioned the solution doesn't use data structure and the loops are separate. Still, how does that make the solution linear time complexity?
@@mytommy Yes it is O(n^2). Outer loop is O(n) inner loop is basically n-1, n-2... which is a known series and the product of the inner and outer loop run times gets you o(n^2).
This is not a real life experience, when you open an image you get a ruster of bytes you don't a get a matrix
C++ Code to do it,
void swapRowValues(vector& matrix, int row) {
const int n = matrix.size();
int left = 0;
int right = n - 1;
while (left < right) {
swap(matrix[row][left++], matrix[row][right--]);
}
}
void transpose(vector& matrix) {
const int n = matrix.size();
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
}
void rotate(vector& matrix) {
const int n = matrix.size();
transpose(matrix);
// Swap each row's values, e.g., col 0 with col n - 1, col 1 with col n - 2, and so on....
for (int i = 0; i < n; i++) {
swapRowValues(matrix, i);
}
}
Your clapping of hands gave me a headache, kindly avoid that