Problem Description

You are given an n x n 2D matrix that represents an image. Your task is to rotate this image by 90 degrees in the clockwise direction.

The key constraint is that you must perform the rotation in-place, meaning you need to modify the original input matrix directly without creating any additional 2D matrix for the rotation.

For example, if you have a 3x3 matrix:

• The element at position [0][0] (top-left) should move to position [0][2] (top-right)
• The element at position [0][2] (top-right) should move to position [2][2] (bottom-right)
• The element at position [2][2] (bottom-right) should move to position [2][0] (bottom-left)
• The element at position [2][0] (bottom-left) should move to position [0][0] (top-left)

The solution achieves this through a two-step transformation:

1. Flip the matrix horizontally (upside down): Swap rows - the first row becomes the last row, the second row becomes the second-to-last row, and so on. This swaps matrix[i][j] with matrix[n - i - 1][j].

2. Transpose the matrix (flip along the main diagonal): Swap elements across the diagonal - matrix[i][j] becomes matrix[j][i]. This transforms rows into columns.

After these two operations, each element matrix[i][j] ends up at position matrix[j][n - i - 1], which is exactly where it should be after a 90-degree clockwise rotation.

The code uses n >> 1 which is equivalent to n // 2 to iterate through half of the rows for the horizontal flip, and then performs the transpose operation on the entire matrix.

Intuition

To understand how to rotate a matrix 90 degrees clockwise in-place, let's first observe what happens to each element's position during rotation. When we rotate clockwise by 90 degrees, an element at position [i][j] moves to position [j][n - i - 1].

The challenge is: how can we achieve this transformation without using extra space? Direct swapping won't work because we'd overwrite values we still need.

Let's think about this differently. What if we could break down this complex transformation into simpler operations that are easier to perform in-place?

Consider what happens when we:

1. First flip the matrix horizontally (upside down)
2. Then transpose it (swap along the diagonal)

Let's trace through what happens to an element at position [i][j]:

Step 1 - Horizontal Flip:

• Element at [i][j] moves to [n - i - 1][j]
• We're essentially reversing the row order while keeping columns the same

Step 2 - Transpose:

• Element now at [n - i - 1][j] moves to [j][n - i - 1]
• We're swapping row and column indices

Notice that after these two operations, the element originally at [i][j] ends up at [j][n - i - 1] - exactly where it should be after a 90-degree clockwise rotation!

Why does this work? The horizontal flip essentially "pre-positions" elements so that when we transpose (which naturally rotates elements 90 degrees but counterclockwise), the combined effect gives us a clockwise rotation.

This approach is elegant because both operations (horizontal flip and transpose) can be easily done in-place using simple swaps, avoiding the need for extra space while achieving our goal.

Learn more about Math patterns.

Solution Approach

The implementation follows the two-step transformation strategy we identified: horizontal flip followed by transpose.

Step 1: Horizontal Flip (Reverse Rows)

for i in range(n >> 1):
    for j in range(n):
        matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]

• We iterate through the first half of the rows (i from 0 to n//2 - 1)
• For each row i, we swap it with its corresponding row from the bottom: row n - i - 1
• The expression n >> 1 is a bitwise right shift, equivalent to n // 2, which gives us the midpoint
• For each position in the row, we swap matrix[i][j] with matrix[n - i - 1][j]
• This effectively flips the entire matrix upside down

For example, in a 3x3 matrix:

• Row 0 swaps with Row 2
• Row 1 stays in place (it's the middle)

Step 2: Transpose (Swap Along Main Diagonal)

for i in range(n):
    for j in range(i):
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

• We iterate through all rows (i from 0 to n-1)
• For each row, we only iterate through columns before the diagonal (j from 0 to i-1)
• We swap matrix[i][j] with matrix[j][i], effectively reflecting the matrix along its main diagonal
• By only iterating j up to i-1, we ensure each pair is swapped exactly once

The key insight is that j < i ensures we only process elements below the main diagonal, preventing us from swapping elements twice (which would undo the operation).

Time and Space Complexity:

• Time: O(n²) - we visit each element twice (once during flip, once during transpose)
• Space: O(1) - we only use a constant amount of extra space for swapping

This approach elegantly transforms matrix[i][j] → matrix[n - i - 1][j] → matrix[j][n - i - 1], achieving the desired 90-degree clockwise rotation entirely in-place.

Example Walkthrough

Let's walk through rotating a 3x3 matrix step by step to see how the two-operation approach works:

Initial Matrix:

1 2 3
4 5 6
7 8 9

Step 1: Horizontal Flip (Reverse Rows)

We swap rows from top and bottom, working toward the middle:

• Swap row 0 with row 2 (since n=3, we swap row i with row n-i-1)
• Row 1 stays in place (middle row)

Operation: Swap row 0 ↔ row 2
1 2 3     7 8 9
4 5 6  →  4 5 6
7 8 9     1 2 3

Let's trace element positions:

• Element 1 at [0][0] moves to [2][0]
• Element 3 at [0][2] moves to [2][2]
• Element 7 at [2][0] moves to [0][0]
• Element 9 at [2][2] moves to [0][2]

Step 2: Transpose (Swap Along Diagonal)

Now we swap elements across the main diagonal (elements where row index = column index):

• Swap [0][1] with [1][0]: 8 ↔ 4
• Swap [0][2] with [2][0]: 9 ↔ 1
• Swap [1][2] with [2][1]: 6 ↔ 2

7 8 9     7 4 1
4 5 6  →  8 5 2
1 2 3     9 6 3

Final Result:

7 4 1
8 5 2
9 6 3

Verification: Let's verify key elements moved correctly for a 90° clockwise rotation:

• Original 1 at [0][0] → Final position [0][2] ✓ (top-left to top-right)
• Original 3 at [0][2] → Final position [2][2] ✓ (top-right to bottom-right)
• Original 7 at [2][0] → Final position [0][0] ✓ (bottom-left to top-left)
• Original 9 at [2][2] → Final position [2][0] ✓ (bottom-right to bottom-left)
• Original 5 at [1][1] → Final position [1][1] ✓ (center stays at center)

The transformation works because:

1. Horizontal flip moves element from [i][j] to [n-i-1][j]
2. Transpose then moves it from [n-i-1][j] to [j][n-i-1]
3. The final position [j][n-i-1] is exactly where element [i][j] should be after a 90° clockwise rotation!

Solution Implementation

Time and Space Complexity

The time complexity is O(n²), where n is the side length of the matrix. This is because:

• The first nested loop iterates through n/2 rows and n columns, performing (n/2) × n = n²/2 operations
• The second nested loop iterates through the upper triangular portion of the matrix, performing n(n-1)/2 operations (sum of 0 + 1 + 2 + ... + (n-1))
• Total operations: n²/2 + n(n-1)/2 = n²/2 + n²/2 - n/2 ≈ n² - n/2 = O(n²)

The space complexity is O(1) as the algorithm only uses a constant amount of extra space for the swap operations, modifying the matrix in-place without allocating any additional data structures that scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Transpose Loop Bounds

One of the most common mistakes is using incorrect loop bounds during the transpose operation, leading to either swapping elements twice (undoing the operation) or missing some elements.

Incorrect Implementation:

# WRONG: This swaps each pair twice, undoing the transpose
for i in range(n):
    for j in range(n):
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

Why it's wrong: When you visit element (i,j), you swap it with (j,i). Later, when you visit (j,i), you swap it back with (i,j), effectively undoing your first swap.

Correct Implementation:

# Option 1: Only iterate below the diagonal
for i in range(n):
    for j in range(i):  # j < i ensures we're below diagonal
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

# Option 2: Only iterate above the diagonal
for i in range(n):
    for j in range(i + 1, n):  # j > i ensures we're above diagonal
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

2. Confusing Operation Order

Another pitfall is performing the operations in the wrong order. The sequence matters significantly.

Incorrect Order:

# WRONG: Transpose first, then flip horizontally
# This results in a 90-degree COUNTER-clockwise rotation
for i in range(n):
    for j in range(i):
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

for i in range(n // 2):
    for j in range(n):
        matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]

Correct Order for Clockwise Rotation:

1. First: Horizontal flip (reverse rows)
2. Then: Transpose

3. Off-by-One Errors in Row Reversal

When flipping rows, it's easy to make indexing mistakes.

Common Mistakes:

# WRONG: Using n // 2 + 1 includes the middle row unnecessarily
for i in range(n // 2 + 1):  # This is incorrect for even n
    matrix[i], matrix[n - i - 1] = matrix[n - i - 1], matrix[i]

# WRONG: Incorrect mirror index calculation
for i in range(n // 2):
    matrix[i], matrix[n - i] = matrix[n - i], matrix[i]  # n - i is out of bounds

Correct Implementation:

for i in range(n // 2):  # Exactly half the rows
    for j in range(n):
        matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]

4. Alternative Approach Confusion

Some developers try to rotate elements directly in cycles, which is conceptually correct but harder to implement correctly.

Complex Direct Rotation (Error-Prone):

# This approach rotates elements in layers/rings
# Easy to make boundary and index calculation errors
for layer in range(n // 2):
    first, last = layer, n - 1 - layer
    for i in range(first, last):
        offset = i - first
        top = matrix[first][i]
        # 4-way rotation - easy to mix up indices
        matrix[first][i] = matrix[last - offset][first]
        matrix[last - offset][first] = matrix[last][last - offset]
        matrix[last][last - offset] = matrix[i][last]
        matrix[i][last] = top

The two-step approach (flip + transpose) is much cleaner and less error-prone.

5. Testing Edge Cases

Don't forget to test with:

• 1x1 matrix (single element)
• 2x2 matrix (smallest non-trivial case)
• Odd-sized matrices (3x3, 5x5)
• Even-sized matrices (4x4, 6x6)

Each requires careful attention to loop bounds to avoid index errors or incomplete rotations.