LeetCode “Rotate Image” (#48) asks you to rotate an n × n square matrix 90° clockwise in-place (i.e., without returning a new matrix).
Example
Input matrix1 2 3 4 5 6 7 8 9
Desired output (90° clockwise)
7 4 1 8 5 2 9 6 3
A real-world analogy is rotating a photo on your phone: each pixel’s new position depends on its current row/column.
Here’s the [Problem Link] to begin with.
Brute Force Solution (Extra Matrix)
Intuition & Approach
The simplest mental model is to copy every element into the place where it should appear after rotation:
- Element
(row =i, col =j)
moves to(row =j, col = n − 1 − i)
. - Because every element’s target is unique, we can safely write into a separate
result
matrix and finally overwrite the original.
This costs extra space but keeps the logic crystal clear.
Code Implementation
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
# dimensions
r = len(matrix)
c = len(matrix[0])
# create an empty r × c matrix
result = [[0 for _ in range(c)] for _ in range(r)]
# place each value in its rotated position
for i in range(r):
for j in range(c):
# new row = old column
# new col = (last row index) - old row
result[j][r - 1 - i] = matrix[i][j]
# copy the rotated picture back to the input matrix
matrix[:] = result
Code Explanation
- Allocate
result
filled with zeros. - Double loop walks every
(i, j)
in the original. - Compute its new coordinates and write to
result
. - Assign
matrix[:] = result
to replace contents while keeping the same reference (important for LeetCode’s “in-place” checker).
Dry Run (3 × 3)
Step | (i, j) | matrix[i][j] | Writes to result | result after write |
---|---|---|---|---|
1 | 0,0 | 1 | (0,2) | 1··<br/>····<br/>··· |
2 | 0,1 | 2 | (1,2) | 1··<br/>2··<br/>··· |
… | … | … | … | … |
9 | 2,2 | 9 | (2,0) | 7 4 1<br/>8 5 2<br/>9 6 3 |
Final copy writes the rotated picture back.
Time & Space Complexity
- Time:
O(n²)
– we visit each of the n² entries once. - Space:
O(n²)
extra – the auxiliary matrix.
Conclusion
The brute-force way is straightforward and great for understanding coordinate mapping, but it doubles memory usage—so we can do better!
Optimal Solution (Transpose + Reverse)
Intuition & Approach
A 90° clockwise rotation can be decomposed into two well-known in-place operations:
- Transpose – swap
matrix[i][j]
withmatrix[j][i]
for alli < j
.
Rows become columns. - Reverse each row – flips elements left ↔ right.
Converts the transposed picture into a rotated one.
Because both steps modify cells in-place and never require extra rows/cols, the total extra space is O(1)
.
Code Implementation
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
# 1️⃣ Transpose the matrix (swap across the main diagonal)
for i in range(n - 1):
for j in range(i + 1, n):
# swap upper-triangle with lower-triangle element
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# 2️⃣ Reverse every row to finish the 90° rotation
for i in range(n):
matrix[i].reverse()
Code Explanation
- Transpose loop:
Only the upper triangle (j > i
) is swapped to avoid undoing previous swaps. - Reverse loop:
Python’slist.reverse()
reverses each row in-place.
Together they replicate the mathematical definition of rotation without touching extra memory.
Dry Run (3 × 3)
Start
1 2 3
4 5 6
7 8 9
After transpose
1 4 7
2 5 8
3 6 9
After row reversals
7 4 1
8 5 2
9 6 3
Matches the desired output 👌.
Time & Space Complexity
- Time:
O(n²)
– same double loop size. - Space:
O(1)
– only a few temporary variables for swapping.
Conclusion
By leveraging matrix properties (transpose + reverse), we hit optimal memory usage while maintaining clear, readable code. This is the go-to technique in interviews when asked to “rotate image in-place.”
Final Thoughts
- Start with the brute-force version to internalize coordinate transformations.
- Then graduate to the elegant transpose-then-reverse pattern for production-ready, space-efficient solutions.
- Remember: both run in
O(n²)
time—but optimal wins on memory.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.