Problem Statement

Given an n × n 2D matrix representing an image, rotate the image clockwise by 90 degrees. The rotation must be performed in-place without using an auxiliary matrix.

Algorithm Approach

The clockwise rotation can be achieved through two sequential operations:

1. Transpose along the main diagonal — swap rows and columns
2. Mirror each row horizontally — reverse elements within each row

This two-step approach direct yields the desired 90-degree clockwise rotation without requiring additional storage.

Worked Example

Starting matrix:

1 2 3
4 5 6
7 8 9

Step 1: Transpose (diagonal reflection)

1 4 7
2 5 8
3 6 9

Step 2: Horizontal row reversal

7 4 1
8 5 2
9 6 3

Result: The matrix is now rotated 90° clockwise.

Implementation

#include <iostream>
#include <vector>
using namespace std;

class ImageRotator {
public:
    void rotateClockwise(vector<vector<int>>& grid) {
        int dimension = grid.size();
        
        // Step 1: Diagonal transposition
        for (int row = 0; row < dimension; ++row) {
            for (int col = row + 1; col < dimension; ++col) {
                swap(grid[row][col], grid[col][row]);
            }
        }
        
        // Step 2: Reverse each row
        for (int row = 0; row < dimension; ++row) {
            reverse(grid[row].begin(), grid[row].end());
        }
    }
};

int main() {
    vector<vector<int>> grid = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    
    ImageRotator rotator;
    rotator.rotateClockwise(grid);
    
    // Display result
    for (const auto& rowVec : grid) {
        for (int val : rowVec) {
            cout << val << " ";
        }
        cout << endl;
    }
    
    return 0;
}

Implementation Details

Diagonal Transposition

The transpose operation swaps elements across the main diagonal (top-left to bottom-right). Only the upper triangular portion needs processing:

• Condition: col > row (elements strictly above the diagonal)
• Each swap handles two positions simultaneously
• Traversing both triangles would undo previous swaps

Visual representation:

○ ● ●
× ○ ●
× × ○

• ● = upper triangular region (processed)
• × = lower triangular region (skipped)
• ○ = main diagonal (unchanged)

Row Reversal

After transposition, applying reverse() to each row completes the rotation. This horizontal flip converts the transposed matrix into the final rotated state.

Complexity Analysis

Mathematical Verification

For any element at position (i, j) in the original matrix:

• After transpose: moves to (j, i)
• After row reversal: moves to (j, n-1-i)

This transformation maps to the correct clockwise rotation destination for a n×n matrix.