Rotate Image - Matrix - Leetcode 48

I hope you realise that you have a gift in explaining difficult concepts

Could you provide a C++ solution? The C++ approach on your website appears to be a direct copy from LeetCode, which differs from the demonstration in this video

Easier solution for nXn matrix! Neetcode solution may be better suited for nXm matrix.

function rotate(matrix: number[][]): void {
const n = matrix.length;

// Transpose the matrix, starting from i = 1
for (let i = 1; i < n; i++) {
for (let j = i; j < n; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}

// Reverse each row
for (let i = 0; i < n; i++) {
matrix[i].reverse();
}
}

Cleanest explanation I have ever seen. Thank you!

hi neetcode, 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.

List2 = []
for x in range(len(matrix[0])):
List1=[]
for y in matrix[::-1]:
list1.append(y[×])
List2.append(list1)
return list2


Why this code is giving wrong output in leetcode but right output in local jupyter notebook

r seems like always n - l, because the matrix is nxn

great

My solution:
def rotate(self, matrix: List[List[int]]) -> None:
N = len(matrix)

for y in range(N // 2):
for x in range(y, N - y - 1):
first = matrix[y][x]
matrix[y][x] = matrix[-x - 1][y]
matrix[-x - 1][y] = matrix[-y - 1][-x - 1]
matrix[-y - 1][-x - 1] = matrix[x][-y - 1]
matrix[x][-y - 1] = first


------- or

class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
N = len(matrix)

for y in range(N // 2):
for x in range(y, N - y - 1):
rot_x, rot_y = x, y

for i in range(3):
matrix[rot_y][rot_x], matrix[-rot_x - 1][rot_y] = (
matrix[-rot_x - 1][rot_y],
matrix[rot_y][rot_x],
)
rot_x, rot_y = rot_y, -rot_x - 1

The best explanation by far of the layer rotation method. Damn it. The best!!

j=0
for i in zip(*matrix):
matrix[j]=reversed(i)
j+=1

my ego has made me attempt this problem almost 3 hours – thank you for this clean explanation!

Since its python you can just do

def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
l, r = 0, n - 1

while l < r:
top, bottom = l, r
for i in range(r - l):
(
matrix[top + i][r],
matrix[top][l + i],
matrix[bottom - i][l],
matrix[bottom][r - i]
) = (
matrix[top][l + i],
matrix[bottom - i][l],
matrix[bottom][r - i],
matrix[top + i][r]
)

r -= 1
l += 1


So theres no need for a temp variable, in that case we also wouldnt have to care about doing it in reverse.

But I think readablitiy suffers a little

To say this is time O(n^2) is subtly misleading/not best way to express the time complexity. While I understand that algebraically "n x n = n^2", when expressing the algo itself in time complexity, O(n^2) could be interpreted as a quadratic runtime. Since the algo only looks at each cell once, the algo is, in fact, linear, so it would be better to express "n x n" as just "M" and therefore O(M).

I cant explain you how much this channel helps me !! Other channels just tell the transpose method which is not so intuitive, you always tell solutions which I can think in future in real interviews and exams. Thanks a lot Neetcode !! Keep up the good work man <3

Cool beans dude!

this code is not working now

The explanation was amazing. I find subtracting i a little confusing. Though dry run help me understand how it works. How do I remember it when I code?

how does leetcode verify solutions to problems where there is no return value but just in place change? thank you!

Your explanation is so good

It's possible to do this without any extra memory at all.
Suppose you have variables x and y. You can swap them like this
y=y+x
x=y-x
y=y-x
This is all you need to transpose a matrix and to swap columns or rows. This rotation is just a transposition followed by inverting the order of the rows.

"top" and "bottom" variables are not necessary, one could replace them by "l" and "r"

Can anyone tell what is wrong with c++ using the same approach??

class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n=matrix.size();
int left = 0, right = n-1;
while(left <= right){
int top = left;
int bottom = right;
for(int i=left; i<right; i++){
//move top-left element in a temp variable
int temp = matrix[top][left+i];

//move bottom-left to top-left
matrix[top][left+i] = matrix[bottom-i][left];

//move bottom-right to bottom left
matrix[bottom-i][left] = matrix[bottom][right-i];

//move top-right to bottom-right
matrix[bottom][right-i] = matrix[top+i][right];

//move top-left (temp) to top-right
matrix[top+i][right] = temp;
}
left++;
right--;
}
}
};

fantastic teacher!

I beat 97% time and 70% memory by making a new list and then updating the original list to be that new list

Beautiful code~

I like the intuitively named variables.

Great explanation, does anyone know why the range has to be range(right- left) instead of range(left,right)? The range(left,right) works on many of the smaller test cases but does not work on many of the harder ones. Help!

Very nice explanation. Thanks NeetCode!

How is the complexity O(n^2) wouldn't it be O(n) since big O notation cares about the size of our data and we were given an n x n data set?

as usual, you made it easy man

what about make one round to 1D array and change the order for them ?

Really good explanation

Hi guys, does anyone know why the for loop (line 9) has to be range(right - left)? I thought range(left, right - 1) would work but I've tried it and it doesn't on the harder test cases. I can't wrap my head around why. Would appreciate any help.

Thanks for the clear explanation. I can understand it while I am in a food coma. lol

This is really a pure math problem. rotating a cell 90 degree, the index/coordinate change is from (x,y) -> (y, n-1-x).

I find the standard rotation technique to be pretty frustrating to think about. Instead ive found its easier to invert the values on the diagonal then reverse the rows.

very intuitive

Dude you are amazing

Your explanation is very clear and I understand how it works. However, when I try it on leetcode it says my time limit is exceeded. Would you have any reason for why that would be the case.

You can transpose the matrix in place and reverse each row to achieve the same result

These videos are great, this one in particular is perfect. I struggled with this a lot until I checked out this video. Awesome stuff!

Thanks for such a clear explanation.

Now this... I like!

simpler method is to transpose it and reverse rows.

Thank You Brother for this amazing video.............🙏🙏🙏🙏🙏🙏

Thank you so much. You're the best.