Rotate Image (Leetcode 48) | Full solution with examples visuals and animation | Study Algorithms
VloĆŸit
- Äas pĆidĂĄn 23. 07. 2024
- You are given a matrix that represents an image. Each grid element can be considered as a part of a complete image. This image needs to be rotated 90 degree in a clockwise direction in a space efficient method. This video explores several ways to achieve this task along with the thought process. Based on the concept you can additionally think about flipping an image and other applications.
Chapters:
00:00 - Intro
01:13 - Problem Statement and Description
02:44 - Brute Force Method to Rotate Image
05:03 - Concept of swapping
06:42 - Efficient solution
10:10 - Dry-run of Code
13:32 - Final Thoughts
Actual problem on LeetCode: leetcode.com/problems/rotate-...
đ Links to topics I talk about in the video:
Time Complexity: âą What is the Time Compl...
What is Big O?: âą Big O Notation Simplif...
Brute Force Solution: âą Brute Force algorithms...
LeetCode Problems: âą Leetcode Solutions
Data Structures: âą Data Structures
đ A text based explanation is available at: studyalgorithms.com
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
đ Reference Books:
Starting Learn to Code: amzn.to/36pU0JO
Favorite book to understand algorithms: amzn.to/39w3YLS
Favorite book for data structures: amzn.to/3oAVBTk
Get started for interview preparation: amzn.to/39ysbkJ
đ To see more videos like this, you can show your support on: www.buymeacoffee.com/studyalg...
đ„ My Recording Gear:
Recording Light: amzn.to/3pAqh8O
Microphone: amzn.to/2MCX7qU
Recording Camera: amzn.to/3alg9Ky
Tablet to sketch and draw: amzn.to/3pM6Bi4
Surface Pen: amzn.to/3pv6tTs
Laptop to edit videos: amzn.to/2LYpMqn
đ» Get Social đ»
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #programming #rotateImage
I really don't know why youtube is not recommending your videos in the top list...excellenet way of explaining the problem and the solution...starting with brute force method to optimized and then dry-run of the code...best videos ever...keep the videos rolling....don't get bogged down by the view counts...
Thank you so much for the love. I hope youtube starts showing my videos on the top soon đ
I don't usually leave comments. . So far, I haven't seen such a thorough explanation. thank you very much, sir
I was stuck in this problem almost a day to solve without transposing, after watching this I was clear now, Thanks bro, keep uploading videos
Bro you are truly a Gem for the coder community your explanation and teaching of each point are very understandable form.
A very few can explain with real life examples and I am happy to find this channel which are very informativeđ
Thank you! You are the best man!
much appreciated Sir, thanks.
this explanation helped me a lot
in the second loop why you didnt use (n+1)/2 instead of n/2 ?
of immense help
As always very descriptive and neat explanation brođ
Regarding the loop bounds, i think it would be best the inner loop(j) runs for +1 iteration, instead of the outer loop(i).
So conceptually, from your logical explanation, for each ring which is the ith loop, all elements in the ring get rotated as part of the j iterations, then we move to the inner ring etc.
But if we keep i loop for more iteration(N+1/2), for odd matrixes like 3*3 say, the inner ring is just 1 element, so ideally there shouldn't be a second ring to be rotated/fixed (as its only 1 element matrix[1][1]). but we can see here that the last rotation in the outer loop is happening as part of the inner ring (i=1) iteration (which ideally should have got completed as part of i=0 itself). If we keep j range from 0 to (N+1)/2, this will get fixed. Hope that makes sense.
thanks for these âš
glad you found them helpful
Thanks sirđ
You solution is easy and straight forward. One question, why are you running loops (n+1)/2 and n/2? Thanks
that is just because how we have to rotate the image. you need to visualize where the final pixels/integers will actually go. Then design your loop. So we are going one ring at a time. When you complete the first ring, you have already covered the first row and the last row. Hence the "/2".
hope this helps.
This solution is optimal, but it just feels too heavy to list all the indices in a cycle of swappings. So, I provide another solution using only the information that we need to carry each value at index (i, j) to the new index (j, n - 1 - i). It's easy to observe that to do a cycle of swappings, we just need to swap the first element to the second element, then the first element to the third element, ..., and finally the first element to the last element. Then, the code becomes (python3):
int n = len(matrix);
def nextPoint(x, y):
return y, n - 1 - x
for i in range((n + 1) // 2):
for j in range(n // 2):
x, y = nextPoint(i, j)
while x != i or y != j:
matrix[i][j], matrix[x][y] = matrix[x][y], matrix[i][j]
x, y = nextPoint(x, y)
This method works with all types of permutation.
How u define limits as n+1/2 and n/2 respectively explain plsđą
look at the part 7:10, 5 starts from 0 and reaches "n"
If you run the loop to "n" then you will reach 5 again. We do not want that. We want to stop at middle. That is how the 4 way swap is working
Can you please explain how will the elements 9,7,14,2 get swapped when we are running the inner loop only till j < n/2 which in this case would mean that j=0 or j=1. What happens to the elements that are at j=2. How will they get swapped?
Watch the visual demo I have in the problem
Could someone explain why the final elements (9, 7, 14, 2) in outer ring will get swapped, when we moved to inner ring i.e., i=1 but not when we are iterating at outer ring i.e., i=0 ?
please follow the explanation instead of going straight to the code.
you have not explained how you came up with all the indices, however thanks for the final thoughts!
the images where I show how a rotation takes place, defines the indices
100% effect 100% Clarity
i understand why n/2 because in the inner layer we only need to do half, but i dont understand why outer layer is n+1/2 , shouldn't they be the same since column and row are the same dims?
Try to trace the path with the explanation I give. You will get the indices yourself.
I think the time complexity must be O(N) , as each cell is getting read once and written once.
correct, but we know that the edge size is n. So how many elements will you have? That is n^2
Think like this, if the edge size is 5, then the area of square is 5^2 = 25.
Since it is a cube, we have n^2 elements.
hi Nikhil Lohia, 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.
haven't thought about a 45 degree use case. Can you find a sample question?
how to know the position likr bottom left is matrix[n - 1 - j][i]? It's hard to understand that and why above for loop (i < (n+1) / 2) and the second loop (j < n / 2), how do you know the syntax at each posititon top left top right bottom left bottom right, it's hard to understand đą can anybody explain how to know syntax at each posititon, omg so hard đąâčïž
Take it step by step. Did you watch the entire video? I explain the thought process.
Where to start and then where to end.
What part are you facing a problem with?
Brother can you explain for me why you know the syntax concept at each position, I understand thr concept you taugh but don't know how to write it in code âčïžâčïž how to know and write syntax at each position i wanna write đą so hard for me bro đ, what is matrix[n-1-j] and matrix[n-1-i][n-j-1], matrix[j][n-1-i], and mattix[i][j] so hard brother
Can you explain the position of indices , its confusing where to consider n-1-i Or n-j-1 . Please explain
Otherwise best explanation of the question
walk through the explanation step by step. See how you are starting from outside and then going in 1 row/column at a time. Trace out and try printing the elements. That will explain everything.
sir you are doing awesome but your voice of video is very low
i have fixed that in my latest videos. Check them out and please let me know
ok simple
firstly Transpose the given matrix and then reverse it.
-------------------------------------------------------
Runtime
0
ms
Beats
100.00%
of users with Java