Rotate Matrix / Image by 90 Degrees Clockwise

Given an $N \times N$ 2D square matrix representing an image, the objective is to rotate the image by 90 degrees clockwise. The rotation must be performed efficiently, progressing from a naive approach utilizing auxiliary space to an optimal in-place algorithm that modifies the input matrix directly without allocating extra space.

1. Problem Definition & Mathematical Model

The problem requires taking an $N \times N$ 2D matrix (a square matrix with equal numbers of rows and columns) and rotating its elements by 90 degrees in the clockwise direction.

Visual Workflow of Matrix Rotation

Core Input/Output Rules

1. Input: An $N \times N$ 2D matrix matrix of size $N$.
2. Output: The matrix rotated by 90 degrees clockwise.
3. Primary Constraint (Optimal Target): Modify the matrix in-place ($O(1)$ auxiliary memory).

2. Conceptual Analogy & Structural Mapping

Real-Life Analogy: Turning a Grid Page

Imagine a physical square grid album page containing photos arranged in rows and columns:

• When you tilt the album page 90 degrees clockwise to the right:
  • The first row of photos now stands vertically along the rightmost edge (last column).
  • The bottom-left photo (13) rises up to become the top-left photo of the new orientation.
  • The top-right photo (4) rotates down to become the bottom-right photo.

3. Naive / Brute Force Approach: Helper Matrix Allocation

In an interview setting, you should always start with the Brute Force Solution to establish baseline logic before moving to optimizations.

Core Idea

Create a secondary $N \times N$ answer matrix (ans). Map every element from the source matrix[i][j] to its corresponding rotated cell in ans.

Positional Observations

By observing row and column indices in a $4 \times 4$ matrix ($N = 4$):

• Elements of Row 0 move to Column 3 ($N - 1 - 0$):

  • (0, 0) $\rightarrow$ (0, 3)
  • (0, 1) $\rightarrow$ (1, 3)
  • (0, 2) $\rightarrow$ (2, 3)
  • (0, 3) $\rightarrow$ (3, 3)

• Elements of Row 1 move to Column 2 ($N - 1 - 1$):

  • (1, 0) $\rightarrow$ (0, 2)
  • (1, 1) $\rightarrow$ (1, 2)
  • (1, 2) $\rightarrow$ (2, 2)
  • (1, 3) $\rightarrow$ (3, 2)

4. Deriving the Index Transformation Formula

To generalize this transformation for any element at row index i and column index j:

Original Cell Index: (i, j)
Destination Row Index  : j
Destination Column Index: N - 1 - i

Formula Derivation Table

Generalized Assignment Standard

5. Brute Force Implementation & Complexity Analysis

C++ Source Code (Brute Force)

#include <vector>
using namespace std;

void rotateBruteForce(vector<vector<int>>& matrix) {
    int n = matrix.size();
    // Step 1: Declare an auxiliary matrix of size N x N
    vector<vector<int>> ans(n, vector<int>(n));

    // Step 2: Map each element to its rotated destination
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans[j][n - 1 - i] = matrix[i][j];
        }
    }

    // Step 3: Copy back to original matrix to fulfill function signature
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            matrix[i][j] = ans[i][j];
        }
    }
}

Complexity Breakdown

• Time Complexity: $O(N^2)$
  • Traversing the original matrix takes $O(N^2)$ time.
  • Copying elements back into the original matrix takes another $O(N^2)$ pass.
  • Total time simplifies to $O(N^2)$.
• Space Complexity: $O(N^2)$
  • Allocating an auxiliary $N \times N$ matrix requires $O(N^2)$ extra memory.

6. Optimization Requirement: Moving In-Place

Interviewers will ask you to optimize the space complexity. The phrase "Solve In-Place" means:

• You cannot allocate an additional $N \times N$ matrix.
• All modifications must occur directly within the original memory buffer of matrix.
• Auxiliary space must be reduced from $O(N^2)$ down to $O(1)$.

7. Mathematical Pattern Discovery: Transpose & Reverse

To achieve an in-place transformation, break down the 90-degree rotation into two basic matrix operations:

Key Observation

Compare the initial transposed state of the matrix against the desired final rotated state.

Two-Step Optimal Strategy

1. Transpose the Matrix: Convert every row into a column (swap matrix[i][j] with matrix[j][i]).
2. Reverse Every Row: Reverse the sequence of elements in each row horizontally.

8. Step-by-Step Evolution: Transposing a Matrix In-Place

Diagonal Invariant Property

During matrix transposition, all elements along the main diagonal (matrix[i][i]) remain in their original positions:

• (0, 0) stays at (0, 0)
• (1, 1) stays at (1, 1)
• (2, 2) stays at (2, 2)
• (3, 3) stays at (3, 3)

Traversing Only the Upper Triangle

Pitfall Warning: If you iterate through the entire matrix ($i$ from $0$ to $N-1$ and $j$ from $0$ to $N-1$) and perform swap(matrix[i][j], matrix[j][i]), every non-diagonal element will be swapped twice—canceling out the transposition and returning the matrix to its original state!

To prevent double-swapping:

• Loop row index i from 0 to N - 2.
• Loop column index j from i + 1 to N - 1 (the upper triangle above the main diagonal).

Upper Triangle Loop Pattern (represented by *):

.  *  *  *    (i=0, j goes from 1 to 3)
.  .  *  *    (i=1, j goes from 2 to 3)
.  .  .  *    (i=2, j goes from 3 to 3)
.  .  .  .    (i=3, no iteration needed)

Transpose Pseudocode

for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
        swap(matrix[i][j], matrix[j][i]);
    }
}

9. Step-by-Step Evolution: Reversing Rows In-Place

Once transposed, each row needs to be reversed horizontally.

Two-Pointer Horizontal Reversal Workflow

For each row i:

• Place pointer left at column 0.
• Place pointer right at column N - 1.
• Swap matrix[i][left] and matrix[i][right], then increment left and decrement right until left >= right.

Row Traversal: [ 1,  5,  9, 13 ]
                 ^          ^
               left       right
                 | swap |
               [ 13, 5,  9, 1 ]
                     ^  ^
                   left right
                     | swap |
Final Row State: [ 13, 9, 5, 1 ]

10. Complete Optimal Code Implementation

C++ Solution

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();

        // Step 1: Transpose the matrix in-place
        // Iterate only over the upper triangular elements
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        // Step 2: Reverse each row
        for (int i = 0; i < n; i++) {
            // Using STL algorithm to reverse row i in-place
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

Java Solution

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // Step 1: Transpose the matrix in-place
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // Step 2: Reverse each row in-place using two pointers
        for (int i = 0; i < n; i++) {
            int left = 0;
            int right = n - 1;
            while (left < right) {
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
                left++;
                right--;
            }
        }
    }
}

Python Solution

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 in-place
        for i in range(n - 1):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        # Step 2: Reverse each row in-place
        for i in range(n):
            matrix[i].reverse()

11. Edge Cases, Pitfalls, and Execution Trace

Common Pitfalls to Avoid

1. Double-Swapping in Transpose: Traversing $j$ from $0$ to $N-1$ swaps elements twice, leaving the matrix unchanged. Always start $j$ from $i + 1$.
2. Confusing Clockwise with Counter-Clockwise:
   • 90° Clockwise: Transpose $\rightarrow$ Reverse each row.
   • 90° Counter-Clockwise: Reverse each row $\rightarrow$ Transpose (or Transpose $\rightarrow$ Reverse each column).

Execution Trace on a $3 \times 3$ Matrix

12. Comparison of Approaches

13. Summary and Key Takeaways

• Problem Goal: Rotate an $N \times N$ matrix 90 degrees clockwise in-place.
• Brute Force Index Mapping: Mapping element matrix[i][j] to ans[j][N - 1 - i] requires $O(N^2)$ time and $O(N^2)$ extra space.
• Optimal Strategy: Combine two standard matrix operations: Transpose Matrix then Reverse Every Row.
• In-Place Transposition: Swap matrix[i][j] with matrix[j][i]. Set loop bounds to $i \in [0, N-2]$ and $j \in [i+1, N-1]$ to process only the upper triangle and avoid double-swapping elements back to their original positions.
• In-Place Row Reversal: Reverse each row horizontally using standard STL functions (std::reverse) or a custom two-pointer swap mechanism.
• Optimal Performance: Time Complexity remains $O(N^2)$ while Space Complexity drops to $O(1)$ auxiliary space.