LeetCode Problem 48

Difficulty: 🟡 Medium
Topics: Array, Math, Matrix

Solution

Rotate Image

Problem Understanding

The problem gives us an n x n square matrix that represents an image. Each element in the matrix corresponds to a pixel or value in the image. Our task is to rotate the entire image by 90 degrees clockwise.

The important requirement is that the rotation must happen in-place. This means we are not allowed to create another separate n x n matrix to store the rotated result. Instead, we must directly modify the existing matrix.

To understand the transformation more clearly, consider this matrix:

1 2 3
4 5 6
7 8 9

After rotating clockwise by 90 degrees, the result becomes:

7 4 1
8 5 2
9 6 3

Notice the pattern:

• The first column becomes the first row in reverse order.
• The second column becomes the second row in reverse order.
• The last row becomes the last column.

The constraints tell us several important things:

• The matrix is always square, meaning the number of rows equals the number of columns.
• 1 <= n <= 20, so the matrix is relatively small.
• Values may be negative or positive, but the actual numeric range does not affect the algorithm because we only rearrange positions.

Even though the constraints are small enough that a brute-force solution would pass, the problem explicitly requires an in-place solution. That requirement is the real challenge.

Several edge cases are important:

• A 1 x 1 matrix should remain unchanged.
• A 2 x 2 matrix is the smallest non-trivial rotation.
• Odd-sized matrices contain a center element that never moves.
• Even-sized matrices rotate entirely through layered swaps.
• Negative numbers and duplicate values must still rotate correctly because the algorithm depends only on positions.

Approaches

Brute Force Approach

A straightforward solution is to create a second matrix of the same size and place every element into its rotated position.

For a cell at position (row, col) in the original matrix, its rotated position becomes:

(col, n - 1 - row)

Using this mapping, we can fill a new matrix with rotated values and then copy the contents back into the original matrix.

This approach is easy to understand and implement. Every element moves exactly once, so the algorithm is correct.

However, this solution uses an additional n x n matrix, which requires O(n²) extra space. The problem explicitly forbids allocating another 2D matrix, so this approach does not satisfy the in-place requirement.

Optimal In-Place Approach

The key insight is that a clockwise rotation can be decomposed into two simpler operations:

1. Transpose the matrix
2. Reverse every row

A transpose swaps rows and columns:

matrix[row][col] ↔ matrix[col][row]

After transposing, rows become columns.

Then, reversing each row changes the orientation into the desired clockwise rotation.

For example:

Original:

1 2 3
4 5 6
7 8 9

After transpose:

1 4 7
2 5 8
3 6 9

After reversing rows:

7 4 1
8 5 2
9 6 3

This method modifies the matrix directly and uses only constant extra memory.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n²)	Uses an additional matrix to store rotated values
Optimal	O(n²)	O(1)	Performs transpose and row reversal in-place

Algorithm Walkthrough

1. Determine the matrix size n.

Since the matrix is square, the same dimension applies to both rows and columns. 2. Transpose the matrix.

For every pair of indices (row, col) where col > row, swap:

matrix[row][col] ↔ matrix[col][row]

We only process the upper triangle of the matrix because swapping twice would undo the change.

After this step, rows become columns. 3. Reverse each row.

For every row in the matrix, reverse the elements in-place.

This converts the transposed matrix into the final clockwise-rotated matrix. 4. Finish without returning anything.

The matrix itself has been modified directly, which satisfies the in-place requirement.

Why it works

The transpose operation reflects the matrix across its main diagonal, converting row positions into column positions. Reversing each row then reorders elements horizontally, which completes the 90-degree clockwise transformation.

Together, these two operations produce exactly the same result as moving each element from:

(row, col) → (col, n - 1 - row)

Because every swap is performed directly inside the original matrix, the algorithm remains in-place.

Python Solution

from typing import List

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)

        # Step 1: Transpose the matrix
        for row in range(n):
            for col in range(row + 1, n):
                matrix[row][col], matrix[col][row] = (
                    matrix[col][row],
                    matrix[row][col],
                )

        # Step 2: Reverse each row
        for row in matrix:
            row.reverse()

The implementation follows the exact algorithm described earlier.

First, we compute the matrix size n.

The transpose step uses nested loops. The outer loop iterates through rows, while the inner loop starts at row + 1. This ensures we only visit the upper triangular portion of the matrix. Each pair of symmetric elements across the diagonal is swapped.

Next, we reverse every row in-place using Python's built-in reverse() method. This efficiently rearranges each row without allocating another matrix.

The function does not return anything because LeetCode expects the original matrix to be modified directly.

Go Solution

func rotate(matrix [][]int) {
	n := len(matrix)

	// Step 1: Transpose the matrix
	for row := 0; row < n; row++ {
		for col := row + 1; col < n; col++ {
			matrix[row][col], matrix[col][row] =
				matrix[col][row], matrix[row][col]
		}
	}

	// Step 2: Reverse each row
	for row := 0; row < n; row++ {
		left := 0
		right := n - 1

		for left < right {
			matrix[row][left], matrix[row][right] =
				matrix[row][right], matrix[row][left]

			left++
			right--
		}
	}
}

The Go implementation mirrors the Python logic closely.

Go does not provide a built-in row reversal method like Python's reverse(), so we reverse each row manually using a two-pointer approach. One pointer starts at the beginning of the row and the other at the end. We repeatedly swap elements until the pointers meet.

No special handling for integer overflow is required because we only swap existing values. The matrix is represented as a slice of slices, and all modifications happen directly on the input structure.

Worked Examples

Example 1

Input:

[
  [1,2,3],
  [4,5,6],
  [7,8,9]
]

Step 1: Transpose

Swap positions across the diagonal.

Swap	Matrix State
swap (0,1) with (1,0)	[[1,4,3],[2,5,6],[7,8,9]]
swap (0,2) with (2,0)	[[1,4,7],[2,5,6],[3,8,9]]
swap (1,2) with (2,1)	[[1,4,7],[2,5,8],[3,6,9]]

After transpose:

1 4 7
2 5 8
3 6 9

Step 2: Reverse Each Row

Row Before	Row After
[1,4,7]	[7,4,1]
[2,5,8]	[8,5,2]
[3,6,9]	[9,6,3]

Final matrix:

[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Example 2

Input:

[
  [5,1,9,11],
  [2,4,8,10],
  [13,3,6,7],
  [15,14,12,16]
]

Step 1: Transpose

After all transpose swaps:

5   2   13  15
1   4   3   14
9   8   6   12
11  10  7   16

Step 2: Reverse Each Row

Row Before	Row After
[5,2,13,15]	[15,13,2,5]
[1,4,3,14]	[14,3,4,1]
[9,8,6,12]	[12,6,8,9]
[11,10,7,16]	[16,7,10,11]

Final matrix:

[
  [15,13,2,5],
  [14,3,4,1],
  [12,6,8,9],
  [16,7,10,11]
]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Every matrix cell is visited a constant number of times
Space	O(1)	All operations are performed in-place

The transpose operation processes roughly half the matrix, which is still proportional to n². Reversing rows also touches every element once. Combining these operations still results in O(n²) time complexity.

No additional matrix or large auxiliary data structure is allocated, so the extra space usage remains constant.

Test Cases

from typing import List

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

        for row in range(n):
            for col in range(row + 1, n):
                matrix[row][col], matrix[col][row] = (
                    matrix[col][row],
                    matrix[row][col],
                )

        for row in matrix:
            row.reverse()

sol = Solution()

# Example 1
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
sol.rotate(matrix)
assert matrix == [
    [7, 4, 1],
    [8, 5, 2],
    [9, 6, 3]
]  # standard 3x3 rotation

# Example 2
matrix = [
    [5, 1, 9, 11],
    [2, 4, 8, 10],
    [13, 3, 6, 7],
    [15, 14, 12, 16]
]
sol.rotate(matrix)
assert matrix == [
    [15, 13, 2, 5],
    [14, 3, 4, 1],
    [12, 6, 8, 9],
    [16, 7, 10, 11]
]  # standard 4x4 rotation

# Single element matrix
matrix = [[1]]
sol.rotate(matrix)
assert matrix == [[1]]  # 1x1 matrix remains unchanged

# 2x2 matrix
matrix = [
    [1, 2],
    [3, 4]
]
sol.rotate(matrix)
assert matrix == [
    [3, 1],
    [4, 2]
]  # smallest non-trivial case

# Matrix with negative numbers
matrix = [
    [-1, -2],
    [-3, -4]
]
sol.rotate(matrix)
assert matrix == [
    [-3, -1],
    [-4, -2]
]  # handles negative values correctly

# Matrix with duplicate values
matrix = [
    [1, 1],
    [1, 1]
]
sol.rotate(matrix)
assert matrix == [
    [1, 1],
    [1, 1]
]  # duplicates should remain consistent

# Odd-sized matrix
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
sol.rotate(matrix)
assert matrix[1][1] == 5  # center element stays fixed

Test	Why
3x3 standard example	Verifies basic clockwise rotation
4x4 standard example	Verifies larger even-sized matrix
1x1 matrix	Confirms smallest boundary case
2x2 matrix	Tests smallest meaningful rotation
Negative values	Ensures values themselves do not affect logic
Duplicate values	Verifies position-based rotation correctness
Odd-sized matrix	Confirms center element behavior

Edge Cases

A 1 x 1 matrix is the smallest possible input. Since there is only one element, rotating the matrix changes nothing. Some implementations accidentally attempt invalid swaps or reversals when handling very small matrices. This implementation handles the case naturally because both loops execute zero meaningful operations.

Odd-sized matrices contain a center element that should remain fixed after rotation. For example, in a 3 x 3 matrix, the middle value never changes position. Incorrect index calculations can accidentally move or overwrite this value. The transpose-and-reverse strategy preserves the center element automatically because it maps to itself.

Matrices with duplicate values can hide logical bugs. For example, if all values are identical, a broken implementation might still appear correct visually. This implementation relies entirely on index transformations rather than value comparisons, so duplicates are handled correctly without ambiguity.

Even-sized matrices such as 4 x 4 or 6 x 6 have no central pivot element. Every value participates in movement during rotation. Incorrect loop boundaries during transpose operations can cause double-swapping or skipped elements. By iterating only where col > row, the implementation guarantees each pair is swapped exactly once.