Rotate Image 90 Degrees — Transpose + Flip O(n²) [Meta, Google]

Problem Statement

Rotate an n×n matrix 90 degrees clockwise in-place.

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

Intuition
C++ Solution
Java Solution
Python Solution
Complexity: O(n²) time, O(1) space

Intuition

Step 1: Transpose — swap matrix[i][j] with matrix[j][i] Step 2: Reverse each row — [1,4,7] → [7,4,1]

Together these achieve 90° clockwise rotation.

C++ Solution

class Solution {
public:
    void rotate(vector<vector<int>>& m) {
        int n=m.size();
        // Transpose
        for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) swap(m[i][j],m[j][i]);
        // Reverse rows
        for(int i=0;i<n;i++) reverse(m[i].begin(),m[i].end());
    }
};

Java Solution

class Solution {
    public void rotate(int[][] m) {
        int n=m.length;
        for(int i=0;i<n;i++) for(int j=i+1;j<n;j++){int t=m[i][j];m[i][j]=m[j][i];m[j][i]=t;}
        for(int i=0;i<n;i++){int l=0,r=n-1;while(l<r){int t=m[i][l];m[i][l++]=m[i][r];m[i][r--]=t;}}
    }
}

Python Solution

def rotate(matrix):
    n = len(matrix)
    # Transpose
    for i in range(n):
        for j in range(i+1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row
    for row in matrix:
        row.reverse()

Complexity: O(n²) time, O(1) space

Anti-clockwise: Transpose then reverse each column (or reverse rows then transpose).