Rotate Image

Rotate Image is a favorite because the easy answer wastes memory. Anyone can copy the grid into a new grid in rotated order. But the interviewer adds one rule. Do it in place. No second grid. That small rule turns a simple copy into a neat two-step trick. Showing that trick is the whole point.

🎯 The Problem

You get a square matrix and you must turn it in place. Here are the rules.

• The grid is square. The same number of rows and columns.
• Turn it 90 degrees clockwise. The top row swings to the right side.
• Change the grid in place. No second grid the same size.
• The first column read bottom to top becomes the new top row.

Look at this grid. After a clockwise turn, 7 4 1 becomes the new top row.

Input:
1 2 3
4 5 6
7 8 9

Output:
7 4 1
8 5 2
9 6 3

Explanation: turn the grid 90 degrees clockwise, in place.

Here is what one rotation does to a single cell. The value at row 0 col 0 moves to row 0 col 2.

🐢 Approach 1: Copy Into a New Matrix (Brute Force)

The idea in one line: build a fresh grid, place each cell where the turn sends it, then copy it back.

The idea:

• Make a new grid the same size.
• Old cell (i, j) lands at new cell (j, n - 1 - i).
• Fill the new grid, then copy it over the old one.

Why it is weak:

• It needs a second grid as big as the input.
• That extra space is O(n²).
• The interviewer almost always bans the second grid.

Here is the extra-matrix code:

def rotate(matrix):
    n = len(matrix)
    copy = [[0] * n for _ in range(n)]

    for r in range(n):
        for c in range(n):
            copy[c][n - 1 - r] = matrix[r][c]

    for r in range(n):
        matrix[r][:] = copy[r]

⚡ Approach 2: Transpose Then Reverse Each Row (Best)

The idea in one line: a clockwise turn is just a transpose, then a reverse of each row, both inside the same grid.

The idea:

• Transpose means flip the grid across its main diagonal.
• The main diagonal runs from top left to bottom right.
• Transpose swaps cell (i, j) with cell (j, i). Rows become columns.

How it works:

• Transpose first. Rows and columns trade places.
• Each row is now in the wrong left-right order.
• Reverse each row. Swap first with last, second with second-last, and so on.
• Two flips together equal one clockwise turn.

Why it is fast:

• Both flips happen inside the same grid.
• The extra space is O(1).
• The order matters. Transpose first, then reverse rows.

Steps to Solve

1. Transpose the matrix. For every pair (i, j) with j > i, swap matrix[i][j] and matrix[j][i].
2. Reverse each row. For each row, swap the cells from the two ends moving toward the middle.
3. The matrix is now turned 90 degrees clockwise, all in place.

Here is the two-step flow on the example.

#include <stdio.h>

#define N 3

void rotate(int matrix[N][N]) {
    for (int i = 0; i < N; i++)            // transpose
        for (int j = i + 1; j < N; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    for (int i = 0; i < N; i++)            // reverse each row
        for (int j = 0; j < N / 2; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[i][N - 1 - j];
            matrix[i][N - 1 - j] = tmp;
        }
}

int main(void) {
    int matrix[N][N] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    rotate(matrix);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) printf("%d ", matrix[i][j]);
        printf("\n");
    }
    return 0;
}

7 4 1
8 5 2
9 6 3

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

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

int main() {
    vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    rotate(matrix);
    for (auto& row : matrix) {
        for (int v : row) cout << v << " ";
        cout << endl;
    }
    return 0;
}

7 4 1
8 5 2
9 6 3

public class Rotate {
    public static void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++)         // transpose
            for (int j = i + 1; j < n; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        for (int i = 0; i < n; i++)         // reverse each row
            for (int j = 0; j < n / 2; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = tmp;
            }
    }

    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        rotate(matrix);
        for (int[] row : matrix) {
            StringBuilder sb = new StringBuilder();
            for (int v : row) sb.append(v).append(" ");
            System.out.println(sb.toString().trim());
        }
    }
}

7 4 1
8 5 2
9 6 3

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


matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate(matrix)
for row in matrix:
    print(" ".join(str(v) for v in row))

7 4 1
8 5 2
9 6 3

function rotate(matrix) {
  const n = matrix.length;
  for (let i = 0; i < n; i++) {           // transpose
    for (let j = i + 1; j < n; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
  for (const row of matrix) row.reverse(); // reverse each row
}

const matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
rotate(matrix);
for (const row of matrix) console.log(row.join(" "));

7 4 1
8 5 2
9 6 3

Let us read the Python version line by line, because the two steps must happen in this exact order.

n = len(matrix) records the side length. Since the matrix is square, the row count and column count are the same.

The transpose loop is the first key part. The outer loop runs i over every row. The inner loop runs j from i + 1 to the end. Starting j at i + 1 is on purpose. It only touches cells above the main diagonal. So each pair is swapped once, not twice. If j started at 0, we would swap every pair twice and end up back where we started. The line matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] swaps the mirror cells across the diagonal.

After this loop the rows and columns have traded places. But the values inside each row are in the wrong order for a clockwise turn.

The second loop fixes that. for row in matrix: row.reverse() reverses each row end to end. row.reverse() flips the row in place, so it costs no extra grid. After both steps the matrix is turned 90 degrees clockwise.

The order matters. Transpose first, then reverse rows. Swap the order and you get a counter-clockwise turn instead.

⏱️ Time and Space Complexity

Both approaches touch each cell a constant number of times. So the time is O(n²) for an n by n grid. The difference is memory. The copy approach needs a second grid, so its space is O(n²). The transpose-then-reverse approach works inside the same grid, so its extra space is just O(1).

🧩 Key Takeaways

• ✅ A clockwise 90-degree turn equals a transpose followed by reversing each row.
• ✅ Transpose swaps cell (i, j) with cell (j, i), flipping across the main diagonal.
• ✅ Start the inner transpose loop at i + 1 so each pair is swapped only once.
• ✅ Both steps happen in place, so the extra space is O(1).
• ✅ The order matters: transpose first, then reverse rows, or you turn the wrong way.

🚀 What’s Next?

• Spiral Matrix
• Set Matrix Zeroes