LeetCode 48. Rotate Image (Solution Explained)
Вставка
- Опубліковано 5 жов 2024
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.d...
AlgoCademy - algocademy.com...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/...
Follow Me on X/Twitter - x.com/nickwhit...
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/nick....
Become A Member - / @nickwhite
#coding #programming #softwareengineering
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. 😂
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.
I felt stuck then I watched this video. Feel alive again!!
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
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!
of all the explanations ive seen of this problem, this explanation makes the most since.
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. I got stuck on this one hard until I saw this video.
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
I was stuck on this problem from 3days and solved on my own but this approach is much better
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
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
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.
Daymnnn Man you made it so easy !! You have the best solutions for leetcode on youtube
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.
Thanks, man! Great Logic. It kind of reminds of Linear Algebra : )
Good explanation.Finally i understood the approach.
you wanna know this if you have online assessments coming up!!! Matrix diagonals and rotation comes up alot
Great explanation, really helped a lot. Love from India.
I think you can set j to i+1 because you can skip over the same index values
Awesome explanation. Thank you so much for all you do!
Really Really Helpful Buddy. Spent A Lot Time On It.
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
Amazing explanation! Thank you very much
Best explanation by far to this problem.
Excellent explanation. Thank you.
Another great video, Thanks, Nick!
Thank you so much. This really helped me a lot.
Love it! Such an elegant solution
this is brilliant and doable. Thanks!
great vid! the time complexity of this algorithm is O(N^2) not linear tho
linear for the size of matrix.
the best solution so far!
Hi.. Nice explanation. Thanks for the video!! Could you please tell me how the time complexity is not O(N^2)?
How is this linear time? There is 2 nested loops.
Linear with respect to the dimensions of the matrix.
Same exact question in Javascript is under the "easy" category on LeetCode ?!
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
Amazing explanation, man!! Thank you. Liked and subscribed!
Great Explanation and very clean code !
excellent explanation and solution Nick! more video pls
what if we just reverse each row in the second loop
That works too
Made this so simple thanks!
dude don't forget to say , leave a like . I almost forgot to give a like.. you are the best.
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
super easy solution bro. Thanks a ton!
Hi Nick, can we not do j=i+1 when we do the transpose?
Thank you Nick!!
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.
thats sick thanks Nick
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.
just awesome man just awesome
Great explanation, thanks
you made it easy.....
Thanks
Great Explanation!!!! As always :)
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!
Nice solution!
bro thanks for everything
Thanks!
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
Thank You
Thanks man
Good question
What abt an NxM ? .ex 3x5?
You would not be able to rotate a non square matrix in place.
TNX man!
Thanks bro
Thank u
1:50 code real fine
thanks bruh
Great video❤
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).
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);
}
}
Oh, man, you are awesome
I feel less stupid. Thanks
cool trick.
nice vid!
Champ!
Your clapping of hands gave me a headache, kindly avoid that
Thank you