You are given a 2D grid of integers. Write a function to rotate the grid by 90 degrees…
- User
You are given a 2D grid of integers. Write a function to rotate the grid by 90 degrees clockwise. Please write a function that solves this problem, explain your algorithm. A common approach is to first transpose the matrix and then reverse each row, and can you do this in-place.
- Assistant
We are going to solve the problem in two steps:
- Transpose the matrix: swap element at (i, j) with (j, i) for all i < j.
- Reverse each row of the transposed matrix.
However, note that we are asked to do it in-place. So we must do the transpose and reversal without using extra space for another 2D matrix.
Steps for in-place rotation (for square matrix only): Step 1: Transpose the matrix. For i from 0 to rows-1: For j from i+1 to cols-1: swap matrix[i][j] with matrix[j][i]
Step 2: Reverse each row. For each row in the matrix, reverse the row.
But note: the problem does not specify if the matrix is square. The common method of transpose and then reverse each row works for square matrices. However, for non-square matrices, rotating 90 degrees clockwise would result in a matrix of dimensions (n, m) becoming (m, n). So in-place rotation for non-square matrices is not possible without changing the dimensions. Therefore, I assume the grid is square.
But let's read the problem: "You are given a 2D grid of integers." and then "rotate the grid by 90 degrees clockwise". It doesn't specify square. However, the common approach for in-place is for square matrices.
If the matrix is not square, we cannot do it in-place because the dimensions change. So we have two options:
Option 1: Assume the matrix is square and do the in-place method.
Option 2: If the matrix is not square, we would have to create a new matrix of size (n, m) -> (m, n). But the problem says "in-place".
Since the problem says "in-place", I think we can assume the matrix is square.
However, let me clarify: if the matrix is not square, we cannot do it in-place without changing the structure of the matrix (i.e., the number of rows and columns). Therefore, I will write a function that works for square matrices in-place.
But wait, the problem doesn't say the matrix is square. So let's think:
If the matrix is of size m x n, then rotating 90 degrees clockwise gives a matrix of size n x m. In-place means we cannot use extra space for another 2D array. But we can use a temporary variable for swapping, but we cannot store the entire matrix.
For non-square, we would have to change the number of rows and columns, which in most programming languages means we need to create a new structure.
So I think the problem expects the matrix to be square. However, to be safe, I will note:
If the matrix is not square, then we cannot do it in-place without changing the dimensions. Therefore, the function will only work for square matrices.
But the problem statement does not specify. Let me re-read: "Write a function to rotate the grid by 90 degrees clockwise." and then "do this in-place".
I think the intended solution is for square matrices.
Let's write for square matrices.
Steps for square matrix (n x n):
- Transpose: swap matrix[i][j] with matrix[j][i] for i in [0, n) and j in [i+1, n).
- Reverse each row: for each row i, swap matrix[i][j] with matrix[i][n-1-j] for j in [0, n/2).
However, if we are not allowed to assume square, we have to return a new matrix of different dimensions? But the problem says in-place.
Given the ambiguity, I will provide two solutions:
Solution 1 (for square matrices, in-place):
Solution 2 (for any matrix, but not in-place because dimensions change, so we return a new matrix).
Since the problem says "in-place", I think we should assume square.
But wait, the problem says: "A common approach is to first transpose the matrix and then reverse each row, and can you do this in-place."
That approach is for square matrices. So I will assume square.
However, to be thorough, I will write a function that checks if the matrix is square. If not, then we cannot do in-place and we might throw an exception or return the original?
But the problem says "rotate", so for non-square we must change the dimensions. So in-place is impossible.
Therefore, I will write for square only.
Let's code for square matrix in-place.
Steps:
n = len(matrix)
Transpose
for i in range(n): for j in range(i+1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
Reverse each row
for i in range(n): matrix[i].reverse()
But note: the reverse operation in Python for a list is in-place and O(n). However, we are allowed to use that.
Alternatively, we can reverse each row by swapping:
for i in range(n): left, right = 0, n-1 while left < right: matrix[i][left], matrix[i][right] = matrix[i][right], matrix[i][left] left += 1 right -= 1
But using the built-in reverse is simpler and also in-place.
However, the problem says "in-place" and we are using the built-in reverse which is in-place for the row (since rows are lists).
But note: the matrix is a list of lists. When we do matrix[i].reverse(), it reverses the inner list in-place.
So the entire operation is in-place for the square matrix.
Let's write the function accordingly.
However, what if the matrix is empty? We should handle that.
Code:
def rotate(matrix): n = len(matrix) # Check if it's square? We assume it is. But we can check: for row in matrix: if len(row) != n: raise ValueError("Matrix must be square for in-place rotation.")
# Transpose for i in range(n): for j in range(i+1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # Reverse each row for i in range(n): matrix[i].reverse()But note: the above reverse uses the built-in which is O(n) for each row.
Alternatively, we can do the reverse without built-in by swapping as above.
However, the problem does not specify language. We are writing in Python.
Let me write without using the built-in reverse for clarity of the algorithm:
for i in range(n): for j in range(n//2): matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
But note: the inner loop condition: we only need to go up to n//2.
However, using the built-in is acceptable and more readable.
But the problem says "explain your algorithm". So I will write the swapping version for reverse to show the steps.
Final code without using built-in reverse for rows:
def rotate(matrix): n = len(matrix) # Check square if any(len(row) != n for row in matrix): raise ValueError("Matrix must be square.")
# Transpose for i in range(n): for j in range(i+1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # Reverse each row by swapping for i in range(n): left, right = 0, n-1 while left < right: matrix[i][left], matrix[i][right] = matrix[i][right], matrix[i][left] left += 1 right -= 1However, note that the transpose step is O(n^2) and the reverse step is O(n^2) as well.
But wait, what if the matrix is 1x1? Then it works.
Let's test with a 3x3:
Original: 1 2 3 4 5 6 7 8 9
Transpose: 1 4 7 2 5 8 3 6 9
Then reverse each row: 7 4 1 8 5 2 9 6 3
But that is 90 degrees clockwise? Let's check:
Original: 1 2 3 4 5 6 7 8 9
90 degrees clockwise should be: 7 4 1 8 5 2 9 6 3
Yes, that's correct.
So the algorithm is correct.
However, note: the common method is transpose then reverse each row. That gives 90 degrees clockwise.
What if we want 90 degrees counter-clockwise? Then we would reverse each column after transpose? But that's not asked.
But the problem says clockwise.
So we are good.
Now, what about non-square? We cannot do in-place. So if we are given a non-square matrix, we should return a new matrix? But the problem says in-place.
Therefore, I think the problem expects square.
But to be safe, I will write the function for square and if it's not square, we can do:
Option: create a new matrix of size (n, m) -> (m, n) and then fill accordingly. But that's not in-place.
Since the problem says "in-place", I will only handle square and raise an error for non-square.
However, sometimes in an interview, they might ask to handle non-square without using extra space for the entire matrix? That is impossible because the shape changes.
So I think we are safe.
Let me write the function accordingly.
But wait, the problem says: "You are given a 2D grid of integers." and then "rotate the grid by 90 degrees clockwise". It doesn't specify the grid is square. So maybe we are allowed to change the grid's dimensions? But in-place means we cannot allocate a new 2D array.
How about we do:
If the matrix is m x n (m != n), then we cannot do in-place because we need to change the number of rows and columns. So we must return a new matrix. But the problem says in-place.
Therefore, I think the intended input is square.
Let's stick to square.
However, if we are in a language that uses fixed 2D arrays (like C++), then we cannot change the dimensions at all. But in Python, we can change the matrix by reassigning the outer list? But then we are changing the reference?
The problem says "in-place", meaning we should modify the given matrix. But if the matrix is non-square, we cannot because the number of rows and columns change.
So, I will assume the matrix is square.
Code:
def rotate(matrix): n = len(matrix) # Check if it's square for row in matrix: if len(row) != n: # We cannot do in-place for non-square raise ValueError("The matrix must be square to rotate in-place.")
# Transpose the matrix for i in range(n): for j in range(i+1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # Reverse each row for i in range(n): left = 0 right = n - 1 while left < right: matrix[i][left], matrix[i][right] = matrix[i][right], matrix[i][left] left += 1 right -= 1However, note: the above reverse for each row is done by swapping. We can also use:
for i in range(n): matrix[i] = matrix[i][::-1]But that creates a new list for each row and then assigns it to matrix[i]. Is that in-place? In Python, when we do matrix[i] = ..., we are changing the reference of the inner list. But the outer list (matrix) is the same. However, we are creating a new list for each row. So it uses O(n) extra space for each row? Actually, the slicing [::-1] creates a new list. So that would be O(n^2) extra space in total.
So if we want to be strictly in-place (without allocating new lists for rows), we should swap in the same list.
Therefore, the swapping in the while loop is better for in-place.
Alternatively, we can use:
for i in range(n): for j in range(n//2): matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]This is the same as the while loop but with a for loop.
Let me adjust:
for i in range(n): for j in range(n//2): matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]This is also in-place and uses O(1) extra space.
So I'll use that.
Final code:
def rotate(matrix): n = len(matrix) if n == 0: return # Check square for row in matrix: if len(row) != n: raise ValueError("Matrix must be square for in-place rotation.")
# Transpose for i in range(n): for j in range(i+1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # Reverse each row for i in range(n): for j in range(n//2): matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]Let's test with 3x3:
Step 1: transpose of [1,2,3] [4,5,6] [7,8,9] becomes: [1,4,7] [2,5,8] [3,6,9]
Step 2: reverse each row:
[7,4,1] [8,5,2] [9,6,3]Which is correct.
Time complexity: O(n^2) because we have two nested loops for transpose and two nested loops for reverse (each is n^2/2, so still O(n^2)).
Space complexity: O(1) extra space.
However, note that the transpose step also uses two nested loops, so total operations are about 2*(n*(n-1)/2) for transpose and 2*(n*(n//2)) for reverse? But in big O, it's O(n^2).
So that's the solution.
But wait, what if the matrix is 0x0? We check n=0 and return.
Also, if the matrix is 1x1? Then transpose does nothing and reverse does nothing (because n//2=0). So it's fine.
So we are done.
However, the problem says "write a function", so I'll write a function that takes a list of lists and modifies it.
But note: the function does not return anything, it modifies the input.
Let's write the function accordingly.
But wait, the problem might be for non-square? If we are not allowed to assume square, then we have to do:
m = len(matrix) n = len(matrix[0]) if m>0 else 0
Then create a new matrix of size n x m, and then fill:
new_matrix = [[0]*m for _ in range(n)] for i in range(m): for j in range(n): new_matrix[j][m-1-i] = matrix[i][j]Then return new_matrix? But that's not in-place.
Since the problem says in-place, we cannot do that.
So I think we stick to square.
However, if the problem expects non-square and in-place is impossible, then we have to change the structure of the matrix. But in Python, we can reassign the variable
matrixto a new list, but that would not change the original reference in the caller?So I think we are safe with square.
But to cover the non-square case, we can do:
If the matrix is not square, then we cannot do in-place. So we can either:
a) Throw an exception (as above). b) Return a new matrix (but then the function signature would change?).
Since the problem says "in-place", I think we should throw an exception for non-square.
Alternatively, we can check at the beginning and if not square, then we can do:
m, n = len(matrix), len(matrix[0]) if m != n: # We cannot do in-place, so we create a new matrix and then assign the rows? But the caller's matrix variable would still point to the old one. # So we cannot change the caller's variable to point to a new matrix without returning and having the caller assign.
Therefore, we must assume square.
So I'll write the function for square.
Let me write the function with docstring.
However, note: the problem says "A common approach is to first transpose the matrix and then reverse each row, and can you do this in-place."
So they are hinting at the square matrix.
Therefore, I think we are correct.
Code:
def rotate(matrix): """ Rotates the given n x n matrix by 90 degrees clockwise in-place.
Args: matrix: A list of n lists, each of length n, representing an n x n matrix. Raises: ValueError: If the matrix is not square. """ n = len(matrix) if n == 0: return # Check if the matrix is square for row in matrix: if len(row) != n: raise ValueError("The matrix must be square (n x n) for in-place rotation.") # Transpose the matrix for i in range(n): for j in range(i+1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # Reverse each row for i in range(n): for j in range(n//2): matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]That's it.
But note: the reverse step can be done with:
for i in range(n): left, right = 0, n-1 while left < right: matrix[i][left], matrix[i][right] = matrix[i][right], matrix[i][left] left += 1 right -= 1Both are acceptable.
Let's stick to the for loop for reverse.
However, the for loop for reverse uses range(n//2) and then we swap j with n-1-j. That's also clear.
So I'll leave it as the for loop.
Now, what about the case when n is odd? The middle element in each row stays the same. So we don't need to swap it. That's why we use n//2.
Example: n=3, we swap (0,2) and (1,1) stays. That's correct.
So the code is complete. To rotate an
n x nmatrix 90 degrees clockwise in-place, we perform two key steps:- Transpose the matrix: Convert rows into columns by swapping
matrix[i][j]withmatrix[j][i]for alli < j. - Reverse each row: For every row, swap elements symmetrically from the ends toward the center (e.g., swap
matrix[i][j]withmatrix[i][n-1-j]forj < n/2).
This approach works because:
- Transposing turns rows into columns, aligning elements for the final clockwise orientation.
- Reversing each row completes the 90-degree clockwise rotation.
Complexity:
- Time: O(n²) — we visit each element twice (transpose + reverse).
- Space: O(1) — only a constant amount of extra space for temporary swaps.
Implementation
def rotate(matrix): """ Rotates an n x n matrix 90 degrees clockwise in-place. Args: matrix: List[List[int]] - The input square matrix. Raises: ValueError: If the matrix is not square. """ n = len(matrix) if n == 0: return # Validate square matrix for row in matrix: if len(row) != n: raise ValueError("Matrix must be square (n x n) for in-place rotation.") # Step 1: Transpose the matrix (swap across diagonal) for i in range(n): for j in range(i + 1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # Step 2: Reverse each row for i in range(n): left, right = 0, n - 1 while left < right: matrix[i][left], matrix[i][right] = matrix[i][right], matrix[i][left] left += 1 right -= 1Example Walkthrough
Input:
1 2 3 4 5 6 7 8 9After Transpose:
1 4 7 2 5 8 3 6 9After Reversing Rows:
7 4 1 8 5 2 9 6 3Output (90° clockwise rotation):
7 4 1 8 5 2 9 6 3Notes
- This solution only works for square matrices. Non-square matrices (
m x nwherem ≠ n) cannot be rotated in-place because rotation changes dimensions (ton x m), requiring a new matrix. - The algorithm modifies the input matrix directly with O(1) extra space.
- Edge cases (empty matrix, 1x1 matrix) are handled naturally.