Rotate Image (Matrix 90 Degree Rotation)

Problem

Rotate an n x n matrix 90 degrees clockwise, in place.

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

Python Solution

def rotate_image(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()
    return matrix

C++ Solution

void rotateImage(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
    for (auto& row : matrix) {
        reverse(row.begin(), row.end());
    }
}

Java Solution

class Solution {
    public void rotateImage(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        for (int[] row : matrix) {
            for (int left = 0, right = row.length - 1; left < right; left++, right--) {
                int temp = row[left]; row[left] = row[right]; row[right] = temp;
            }
        }
    }
}

Complexity

Time: O(n²) — every cell is touched once during the transpose and once during the row reversal. Space: O(1) — the rotation is done in place by transposing then reversing each row, with no second matrix allocated.