LearnWithKiriti

Rotate Matrix by 90 Degrees

đź’» Try it yourself first. Write your solution in Java, C++, Python or JavaScript and run it against hidden tests, right here. New: mock interview with Mr. Tock. Explain your approach out loud, he pushes you to improve it, then you code it. You get a scorecard at the end.
Play
On this page
  1. Revision notes
  2. Brute: New Grid
  3. Optimal: Transpose Reverse
  4. Layers: Four Way Swap
  5. Follow-up: Anticlockwise
  6. Follow-up: Rectangle
  7. Follow-up: Rotate 180

Revision notes

Rotate Matrix / Rotate Image (online-test style)

Video: “Rotate Matrix (Rotate Image)” on LearnWithKiriti (Kodee and Mr. Tock). Arrays series, episode 14. LeetCode 48, Medium. Taught as an online coding test: a 5-minute clock per round, thinking time counts, and the optimal grows out of the brute force.

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

1 2 3        7 4 1
4 5 6   ->   8 5 2
7 8 9        9 6 3
Folder Approach Time Extra space
Brute-NewGrid/ Follow one cell: ans[col][size-1-row] = matrix[row][col], then copy ans back row by row O(n^2) O(n^2)
Optimal-TransposeReverse/ Swap across the diagonal (transpose), then reverse each row with two pointers O(n^2) O(1)
FollowUp-Anticlockwise/ Transpose, then reverse each column (top and bottom move inward) O(n^2) O(1)
FollowUp-Rotate180/ Reverse each row, then reverse the order of the rows (swap whole rows) O(n^2) O(1)
FollowUp-Rectangle/ New cols x rows grid: ans[col][rows-1-row] = matrix[row][col] (cannot be in place) O(rows x cols) O(rows x cols)
Layers-FourWaySwap/ Spin each ring (the same rings as Spiral Matrix) with a 4-way swap O(n^2) O(1)

Rebuild it

Follow one cell. Swap across the diagonal. Reverse every row.

  • Cell (row, col) lands at (col, n-1-row): row 0 stands up as the last column, top to bottom.
  • How to spot the trick from a blank mind: put the original and the answer side by side. The answer’s row 0 is 7 4 1, the original’s col 0 read bottom-up. Every row of the answer is a column of the original, read backwards.
    • “Columns become rows” = swap across the diagonal (transpose).
    • “Backwards” = reverse (the same reverse as Left Rotate).
  • Writing that straight into matrix overwrites a value you still need. A swap never loses anything.
  • Split the move: (row, col) -> (col, row) is a swap across the diagonal (that is the transpose; start col at row + 1, or every pair swaps twice and undoes itself). Then (col, row) -> (col, n-1-row) keeps the row and mirrors the column: reverse each row.
  • Why not matrix = ans? It only changes your local name; the caller’s grid stays unrotated. Copy row by row (C++: pass by reference with &).

Follow-ups

  • Anticlockwise: transpose, then reverse each column.
  • 180 degrees: reverse each row, then reverse the order of the rows.
  • Rectangle (m x n): cannot be rotated in place. Build a new n x m grid: ans[col][rows-1-row] = matrix[row][col].

Practise it on learnwithkiriti.com (sheet, notes, code in 4 languages, run your own code), or next to the video in the free Kodee Practice Chrome extension (link in the video description).

See the pseudocode.md in each folder. Every program was compiled, run and tested (3x3, 4x4, 1x1, 2x2, 5x5).

brute

Brute: New Grid

R1 Brute: a new grid

ans = new size x size grid
for each row, col:
    ans[col][size-1-row] = matrix[row][col]
copy every row of ans back into matrix

Derivation: watch row 0 (1 2 3). After the rotation it stands in the LAST column, top to bottom; row 1 stands in the middle column. So row goes to column size-1-row, and the cell in column col goes to row col: (row, col) -> (col, size-1-row). Check: 1 at (0, 0) lands at (0, 2), top right. Why not matrix = ans: that only re-points the local name; the caller still holds the old grid. Copy row by row. Complexity: O(n^2) time, O(n^2) extra space (the second grid). Passes every test, but breaks “in place”.

RotateBrute.java
import java.util.*;

public class RotateBrute {
    static void rotateBrute(int[][] matrix) {
        int size = matrix.length;
        int[][] ans = new int[size][size];
        for (int row = 0; row < size; row++) {
            for (int col = 0; col < size; col++) {
                ans[col][size - 1 - row] = matrix[row][col];
            }
        }
        for (int row = 0; row < size; row++) {
            matrix[row] = ans[row];
        }
    }

    static String show(Object o) {
        if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
        if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
        if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
        if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
        return String.valueOf(o);
    }

    public static void main(String[] args) {
        { int[][] matrix = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; rotateBrute(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{5, 1, 9, 11}, {2, 4, 8, 10}, {13, 3, 6, 7}, {15, 14, 12, 16}}; rotateBrute(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{1}}; rotateBrute(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{1, 2}, {3, 4}}; rotateBrute(matrix); System.out.println(show(matrix)); }
    }
}
optimal

Optimal: Transpose Reverse

R2 Optimal: in place (swap across the diagonal, then reverse each row)

for row = 0 to size-1:
    for col = row+1 to size-1:
        swap matrix[row][col], matrix[col][row]
for each row:
    left = 0;  right = size-1
    while left < right: swap, left++, right--

Derivation: writing (row, col) -> (col, size-1-row) straight into matrix overwrites a value we still need (1 lands on the 3). Swaps never lose a value, so split the move:

  • Move A: (row, col) -> (col, row). Row and column trade places: a swap across the diagonal. col starts at row + 1 (from 0, every pair swaps twice and undoes itself; the diagonal has no partner). This is the transpose.
  • Move B: (col, row) -> (col, size-1-row). The row stays, the column mirrors: reverse each row with two pointers (the middle of an odd row stays). Proof on 3x3: after Move A: 1 4 7 / 2 5 8 / 3 6 9. Reverse each row: 7 4 1 / 8 5 2 / 9 6 3. Correct. Complexity: O(n^2) time (linear in the number of cells), O(1) extra space.
Rotate.java
import java.util.*;

public class Rotate {
    static void rotate(int[][] matrix) {
        int size = matrix.length;
        for (int row = 0; row < size; row++) {
            for (int col = row + 1; col < size; col++) {
                int temp = matrix[row][col];
                matrix[row][col] = matrix[col][row];
                matrix[col][row] = temp;
            }
        }
        for (int row = 0; row < size; row++) {
            int left = 0;
            int right = size - 1;
            while (left < right) {
                int temp = matrix[row][left];
                matrix[row][left] = matrix[row][right];
                matrix[row][right] = temp;
                left++;
                right--;
            }
        }
    }

    static String show(Object o) {
        if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
        if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
        if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
        if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
        return String.valueOf(o);
    }

    public static void main(String[] args) {
        { int[][] matrix = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; rotate(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{5, 1, 9, 11}, {2, 4, 8, 10}, {13, 3, 6, 7}, {15, 14, 12, 16}}; rotate(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{1}}; rotate(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{1, 2}, {3, 4}}; rotate(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20}, {21, 22, 23, 24, 25}}; rotate(matrix); System.out.println(show(matrix)); }
    }
}
other

Layers: Four Way Swap

Layer by layer: a 4-way swap per ring (GitHub only)

for layer = 0 to size/2 - 1:
    first = layer;  last = size-1-layer
    for step = 0 to last-first-1:
        top = matrix[first][first+step]
        top    <- left    matrix[first][first+step]  = matrix[last-step][first]
        left   <- bottom  matrix[last-step][first]   = matrix[last][last-step]
        bottom <- right   matrix[last][last-step]    = matrix[first+step][last]
        right  <- top     matrix[first+step][last]   = top

The rings are the same rings you peeled in the Spiral Matrix episode. Each step moves 4 cells one quarter turn using one temp. Same rule: (row, col) -> (col, n-1-row); e.g. the left cell (last-step, first) lands on the top cell (first, first+step). Complexity: O(n^2) time, O(1) extra space. Same speed as transpose + reverse, more index math.

RotateLayers.java
import java.util.*;

public class RotateLayers {
    static void rotateLayers(int[][] matrix) {
        int size = matrix.length;
        for (int layer = 0; layer < size / 2; layer++) {
            int first = layer;
            int last = size - 1 - layer;
            for (int step = 0; step < last - first; step++) {
                int top = matrix[first][first + step];
                matrix[first][first + step] = matrix[last - step][first];
                matrix[last - step][first] = matrix[last][last - step];
                matrix[last][last - step] = matrix[first + step][last];
                matrix[first + step][last] = top;
            }
        }
    }

    static String show(Object o) {
        if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
        if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
        if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
        if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
        return String.valueOf(o);
    }

    public static void main(String[] args) {
        { int[][] matrix = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; rotateLayers(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{5, 1, 9, 11}, {2, 4, 8, 10}, {13, 3, 6, 7}, {15, 14, 12, 16}}; rotateLayers(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{1}}; rotateLayers(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20}, {21, 22, 23, 24, 25}}; rotateLayers(matrix); System.out.println(show(matrix)); }
    }
}
follow-up

Follow-up: Anticlockwise

Follow-up: rotate 90 degrees anticlockwise, in place

for row = 0 to size-1:
    for col = row+1 to size-1:
        swap matrix[row][col], matrix[col][row]
for each col:
    top = 0;  bottom = size-1
    while top < bottom: swap matrix[top][col], matrix[bottom][col]; top++, bottom--

Side by side: the anticlockwise answer’s row 0 is 3 6 9, the start’s last column read top-down. Columns become rows (transpose), then the rows come out in reverse order: reverse each column. Proof on 3x3: after the transpose: 1 4 7 / 2 5 8 / 3 6 9. Reverse each column: 3 6 9 / 2 5 8 / 1 4 7. Correct. Complexity: O(n^2) time, O(1) extra space.

RotateAnti.java
import java.util.*;

public class RotateAnti {
    static void rotateAnti(int[][] matrix) {
        int size = matrix.length;
        for (int row = 0; row < size; row++) {
            for (int col = row + 1; col < size; col++) {
                int temp = matrix[row][col];
                matrix[row][col] = matrix[col][row];
                matrix[col][row] = temp;
            }
        }
        for (int col = 0; col < size; col++) {
            int top = 0;
            int bottom = size - 1;
            while (top < bottom) {
                int temp = matrix[top][col];
                matrix[top][col] = matrix[bottom][col];
                matrix[bottom][col] = temp;
                top++;
                bottom--;
            }
        }
    }

    static String show(Object o) {
        if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
        if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
        if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
        if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
        return String.valueOf(o);
    }

    public static void main(String[] args) {
        { int[][] matrix = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; rotateAnti(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}}; rotateAnti(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{1}}; rotateAnti(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{1, 2}, {3, 4}}; rotateAnti(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20}, {21, 22, 23, 24, 25}}; rotateAnti(matrix); System.out.println(show(matrix)); }
    }
}
follow-up

Follow-up: Rectangle

Follow-up: rotate a rows x cols rectangle 90 degrees clockwise

ans = new cols x rows grid
for each row, col:
    ans[col][rows-1-row] = matrix[row][col]
return ans

A rectangle’s shape changes (2 x 3 becomes 3 x 2), so it cannot be rotated in place: build a new grid. Same one-cell rule as the square, with rows in place of size. Proof on 2x3: [[1,2,3],[4,5,6]] becomes [[4,1],[5,2],[6,3]]. Correct. Complexity: O(rows x cols) time and extra space.

RotateRect.java
import java.util.*;

public class RotateRect {
    static int[][] rotateRect(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] ans = new int[cols][rows];
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                ans[col][rows - 1 - row] = matrix[row][col];
            }
        }
        return ans;
    }

    static String show(Object o) {
        if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
        if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
        if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
        if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
        return String.valueOf(o);
    }

    public static void main(String[] args) {
        System.out.println(show(rotateRect(new int[][]{{1, 2, 3}, {4, 5, 6}})));
        System.out.println(show(rotateRect(new int[][]{{1}, {2}, {3}})));
        System.out.println(show(rotateRect(new int[][]{{1, 2, 3, 4}})));
        System.out.println(show(rotateRect(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}})));
    }
}
follow-up

Follow-up: Rotate 180

Follow-up: rotate 180 degrees, in place

for each row:
    left = 0;  right = size-1
    while left < right: swap, left++, right--
top = 0;  bottom = size-1
while top < bottom: swap whole rows matrix[top], matrix[bottom]; top++, bottom--

Cell (row, col) lands at (size-1-row, size-1-col): both indices mirror, so reverse each row (col mirrors), then reverse the order of the rows (row mirrors). No transpose needed. Proof on 3x3: reverse each row: 3 2 1 / 6 5 4 / 9 8 7. Reverse the row order: 9 8 7 / 6 5 4 / 3 2 1. Correct. Complexity: O(n^2) time, O(1) extra space (swapping whole rows swaps references in Java, Python and JS; in C++ swapping two vectors is O(1)).

Rotate180.java
import java.util.*;

public class Rotate180 {
    static void rotate180(int[][] matrix) {
        int size = matrix.length;
        for (int row = 0; row < size; row++) {
            int left = 0;
            int right = size - 1;
            while (left < right) {
                int temp = matrix[row][left];
                matrix[row][left] = matrix[row][right];
                matrix[row][right] = temp;
                left++;
                right--;
            }
        }
        int top = 0;
        int bottom = size - 1;
        while (top < bottom) {
            int[] temp = matrix[top];
            matrix[top] = matrix[bottom];
            matrix[bottom] = temp;
            top++;
            bottom--;
        }
    }

    static String show(Object o) {
        if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
        if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
        if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
        if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
        return String.valueOf(o);
    }

    public static void main(String[] args) {
        { int[][] matrix = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; rotate180(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}}; rotate180(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{1}}; rotate180(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{1, 2}, {3, 4}}; rotate180(matrix); System.out.println(show(matrix)); }
        { int[][] matrix = new int[][]{{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20}, {21, 22, 23, 24, 25}}; rotate180(matrix); System.out.println(show(matrix)); }
    }
}