LeetCode 48. Rotate Image (Solution Explained)

Рет қаралды 84,580

4 жыл бұрын

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

Пікірлер: 110

@Xyvier 4 жыл бұрын

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!

@NuschStephany 4 жыл бұрын

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!

@bharatprakashparakh9601 4 жыл бұрын

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.

@luiscortes6563 4 жыл бұрын

This makes much more sense than the CTCI solution explanation!

@AdityaKamble49 4 жыл бұрын

Exactly, Much more intuitive than that layer by layer approach

@faizyt12345 4 жыл бұрын

but im looking for MxN matrix. this will work only for a square matrix right

@ryebr3ad 3 жыл бұрын

@@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.

@faizyt12345 3 жыл бұрын

@@ryebr3ad thanks after 7 months

@Suraj-tu3nw 3 жыл бұрын

I also came after not being able to grasp the concept from CTCI for this particular problem. 😂

@xinyucao5550 4 жыл бұрын

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!

@TheSexGod 4 жыл бұрын

great explanation. I got stuck on this one hard until I saw this video.

@monicawang5024 4 жыл бұрын

I felt stuck then I watched this video. Feel alive again!!

@JustThink2000 3 жыл бұрын

of all the explanations ive seen of this problem, this explanation makes the most since.

@Sergey111111 2 жыл бұрын

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

@angelaferro3044 3 жыл бұрын

Awesome explanation. Thank you so much for all you do!

@baibhabmondal1740 4 жыл бұрын

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

@ashishdukare1313 3 жыл бұрын

Thanks, man! Great Logic. It kind of reminds of Linear Algebra : )

@julietgeorge4858 4 жыл бұрын

Another great video, Thanks, Nick!

@random-0 3 жыл бұрын

I was stuck on this problem from 3days and solved on my own but this approach is much better

@BrajBliss 2 жыл бұрын

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.

@nithyasubramanian231 3 жыл бұрын

Love it! Such an elegant solution

@christopherlee3311 3 жыл бұрын

Amazing explanation, man!! Thank you. Liked and subscribed!

@sidhantsuman4601 4 жыл бұрын

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

@TheIndianChroniclee 3 жыл бұрын

Really Really Helpful Buddy. Spent A Lot Time On It.

@huizhao2050 3 жыл бұрын

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.

@sarthaksrivastav3408 4 жыл бұрын

Excellent explanation. Thank you.

@abhinavkannojia1053 4 жыл бұрын

Best explanation by far to this problem.

@Ben-pb7ct 3 жыл бұрын

Great Explanation and very clean code !

@BadriBlitz 3 жыл бұрын

Good explanation.Finally i understood the approach.

@krishnanigalye1173 4 жыл бұрын

super easy solution bro. Thanks a ton!

@Darkblaze371 4 жыл бұрын

Made this so simple thanks!

@georgechen1124 4 жыл бұрын

excellent explanation and solution Nick! more video pls

@alregith 3 жыл бұрын

Hi Nick, can we not do j=i+1 when we do the transpose?

@adarshsasidharan254 3 жыл бұрын

I'm glad I didn't waste much time thinking about the solution on my own cuz I would have never guessed this

@sithumdilanga650 Жыл бұрын

Thank you so much. This really helped me a lot.

@pradiptahafid Жыл бұрын

this is brilliant and doable. Thanks!

@MP-ny3ep 4 ай бұрын

Amazing explanation! Thank you very much

@sujitha2339 2 жыл бұрын

Hi.. Nice explanation. Thanks for the video!! Could you please tell me how the time complexity is not O(N^2)?

@magicundercover 4 жыл бұрын

Great explanation, thanks

@prassifromdec10 2 жыл бұрын

the best solution so far!

@ForCodingInterview 3 жыл бұрын

Great Explanation!!!! As always :)

@shiprashakya6106 Жыл бұрын

Great explanation, really helped a lot. Love from India.

@cracknlp364 3 жыл бұрын

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

@genghisda236 4 жыл бұрын

dude don't forget to say , leave a like . I almost forgot to give a like.. you are the best.

@asifnawaz3454 4 жыл бұрын

you made it easy..... Thanks

@Asingh42 4 минут бұрын

Daymnnn Man you made it so easy !! You have the best solutions for leetcode on youtube

@shrimatkapoor2200 3 жыл бұрын

I think you can set j to i+1 because you can skip over the same index values

@SHSelect 2 жыл бұрын

thats sick thanks Nick

@Chloe-si2hq 2 жыл бұрын

Thank you Nick!!

@DasBeatz 4 жыл бұрын

Nice solution!

@Carlos-sy7cv 4 жыл бұрын

How would you do this if it was asking for counter-clockwise? Or would you just rotate it clockwise 3 times?

@drukendoggy 4 жыл бұрын

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.

@abdoulbarry8111 2 жыл бұрын

you wanna know this if you have online assessments coming up!!! Matrix diagonals and rotation comes up alot

@user-kh2od5bw3u 4 жыл бұрын

Thanks!

@rohanmaurya4060 4 жыл бұрын

just awesome man just awesome

@joseeduardobarajasperez1838 Жыл бұрын

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

@pretty_in_scarlet 3 жыл бұрын

Same exact question in Javascript is under the "easy" category on LeetCode ?!

@WowPlusWow 4 жыл бұрын

How is this linear time? There is 2 nested loops.

@raymondtan2795 3 жыл бұрын

Linear with respect to the dimensions of the matrix.

@tarunk57 3 жыл бұрын

bro thanks for everything

@sakthim7160 4 жыл бұрын

Great video❤

@niraiarasu131 4 жыл бұрын

what if we just reverse each row in the second loop

@VishnuprakashSelvarajan 4 жыл бұрын

That works too

@vighneshk509 4 жыл бұрын

great explanation only doubt how is this linear time solution if we are using 2 for loops ?? help me out please

@ajaypanthagani5959 4 жыл бұрын

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.

@jl1835 3 жыл бұрын

great vid! the time complexity of this algorithm is O(N^2) not linear tho

@ankursao7 3 жыл бұрын

linear for the size of matrix.

@indranilthakur3605 4 жыл бұрын

Hey.. WHy do we do N/2 in the second for loop for J?

@aximilian15 4 жыл бұрын

Is because when you are switching the elements from the first column to the last column, you stop midway through each row.

@indranilthakur3605 4 жыл бұрын

@@aximilian15 I understood that later. Thanks

@shusenacademy 4 жыл бұрын

Oh, man, you are awesome

@daeshavvn 3 жыл бұрын

Thank you

@qwarlockz8017 4 жыл бұрын

I LOVE sprite rotation with a Matrix!!!!!!

@qwarlockz8017 4 жыл бұрын

Your videos really are some of the clearest and cleanest on these problems that I have seen. THANKS!

@shankhadeepbanerjee4980 4 жыл бұрын

Thanks bro

@sarvarjuraev1376 Ай бұрын

Thanks man

@adilkapadia8237 3 жыл бұрын

nice vid!

@vk1618 4 жыл бұрын

Good question

@andriidanylov9453 Жыл бұрын

Thank You

@rakshith3547 3 жыл бұрын

We can simplify the 2nd loop little better like public void rotate(int[][] matrix) { if (matrix == null || matrix.length

@pinigantikrishnavamsi7779 2 жыл бұрын

yes but its taking a little bit more memory but that's okay it looks more readable and understandable

@rioslj9452 4 жыл бұрын

What abt an NxM ? .ex 3x5?

@yashshrivastava3748 4 жыл бұрын

You would not be able to rotate a non square matrix in place.

@KogutDV 3 жыл бұрын

TNX man!

@himanshudhiman5424 3 жыл бұрын

thanks bruh

@brrrkit 4 жыл бұрын

1:50 code real fine

@imranimmu4714 Жыл бұрын

Thank u

@kervensjasmin1508 3 жыл бұрын

I feel less stupid. Thanks

@jwolfe890 Жыл бұрын

cool trick.

@mytommy 4 жыл бұрын

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

@NickWhite 4 жыл бұрын

mytommy listen more closely I explained it pretty clearly

@NickWhite 4 жыл бұрын

Linear or O(N) where N is the number of elements in the 2d array

@NickWhite 4 жыл бұрын

Some people say O(M*N) or O(rows*columns) which is fine as long as you specify what you’re variables are referencing

@mytommy 4 жыл бұрын

@@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?

@nbavc 4 жыл бұрын

@@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).

@kedikebba6441 4 жыл бұрын

Champ!

@flexer7822 3 жыл бұрын

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

@farhan787 3 жыл бұрын

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); } }