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!
@@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.
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) {
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!
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!
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
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.
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.
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 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); } }
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!
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! 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
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!
Daymnnn Man you made it so easy !! You have the best solutions for leetcode on youtube
I felt stuck then I watched this video. Feel alive again!!
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
I was stuck on this problem from 3days and solved on my own but this approach is much better
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
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.
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
Hi Nick, can we not do j=i+1 when we do the transpose?
How is this linear time? There is 2 nested loops.
Linear with respect to the dimensions of the matrix.
Hi.. Nice explanation. Thanks for the video!! Could you please tell me how the time complexity is not O(N^2)?
Great explanation, really helped a lot. Love from India.
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.
Really Really Helpful Buddy. Spent A Lot Time On It.
the best solution so far!
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
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.
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
you wanna know this if you have online assessments coming up!!! Matrix diagonals and rotation comes up alot
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.
Best explanation by far to this problem.
Awesome explanation. Thank you so much for all you do!
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
Amazing explanation! Thank you very much
Another great video, Thanks, Nick!
Excellent explanation. Thank you.
this is brilliant and doable. 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
what if we just reverse each row in the second loop
That works too
Thank you so much. This really helped me a lot.
Love it! Such an elegant solution
Amazing explanation, man!! Thank you. Liked and subscribed!
Great Explanation and very clean code !
Thank you Nick!!
Same exact question in Javascript is under the "easy" category on LeetCode ?!
thats sick thanks Nick
excellent explanation and solution Nick! more video pls
What abt an NxM ? .ex 3x5?
You would not be able to rotate a non square matrix in place.
Made this so simple 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).
great vid! the time complexity of this algorithm is O(N^2) not linear tho
linear for the size of matrix.
super easy solution bro. Thanks a ton!
just awesome man just awesome
Great Explanation!!!! As always :)
1:50 code real fine
Great explanation, thanks
you made it easy.....
Thanks
Nice solution!
Thanks!
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!
bro thanks for everything
Thank you
Great video❤
Thanks man
Good question
TNX man!
Oh, man, you are awesome
nice vid!
Thanks bro
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
Thank u
thanks bruh
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);
}
}
I feel less stupid. Thanks
cool trick.
Champ!
Your clapping of hands gave me a headache, kindly avoid that
Thank You