☕ DSA Java Articles

Topics › Arrays › Medium

Rotate matrix by 90 degrees

Medium TUF ID 35 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an n × n square matrix. Rotate it by 90 degrees clockwise. The follow-up, and the version on the sheets, asks you to do it in place without allocating a second matrix.

Rotating clockwise means the first row becomes the last column, the second row becomes the second-to-last column, and so on. In coordinates: the element at (i, j) moves to (j, n - 1 - i).

Constraints: 0 ≤ n ≤ 20 on LeetCode; the code works for any n. Values fit in a 32-bit signed integer.

Example 1

matrix = [[1, 2, 3],
          [4, 5, 6],
          [7, 8, 9]]
answer = [[7, 4, 1],
          [8, 5, 2],
          [9, 6, 3]]       // row 0 (1 2 3) is now column 2, read top to bottom

Example 2

matrix = [[1, 2],
          [3, 4]]
answer = [[3, 1],
          [4, 2]]

Approach 1: Brute force, copy into a new matrix

Intuition. The mapping (i, j) -> (j, n - 1 - i) says exactly where each element goes, so the most direct solution allocates a fresh matrix and writes every element to its destination. Check the formula on a corner: the top-left (0, 0) goes to (0, n - 1), the top-right; the top-right (0, n - 1) goes to (n - 1, n - 1), the bottom-right. That is a clockwise quarter turn.

Algorithm.

  1. Allocate rotated[n][n].
  2. For every (i, j): rotated[j][n - 1 - i] = matrix[i][j].
  3. Return rotated.
static int[][] bruteForce(int[][] matrix) {
    int n = matrix.length;
    int[][] rotated = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            rotated[j][n - 1 - i] = matrix[i][j];   // row i of the input becomes column n-1-i of the output
        }
    }
    return rotated;
}

Complexity. Time O(n^2): each cell is copied once. Space O(n^2) for the new matrix, which is the thing the follow-up wants to eliminate.

Approach 2: Optimal, transpose then reverse each row

Intuition. A clockwise rotation can be decomposed into two simpler in-place operations. Transposing (swapping (i, j) with (j, i), i.e. reflecting across the main diagonal) turns rows into columns, but in the wrong left-to-right order: row 0 becomes column 0, whereas we need it to become column n - 1. Reversing every row of the transposed matrix fixes that. Check with the formula: transpose sends (i, j) to (j, i); reversing row j sends column i to column n - 1 - i; composed, (i, j) -> (j, n - 1 - i), exactly the rotation.

Both steps are in place. The transpose swaps each pair across the diagonal exactly once by only visiting j > i; visiting all pairs would swap everything twice and leave the matrix unchanged.

Algorithm.

  1. For every i and every j > i: swap matrix[i][j] and matrix[j][i].
  2. For every row: reverse it with two pointers.
static int[][] optimal(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n; i++) {                   // transpose: swap across the main diagonal
        for (int j = i + 1; j < n; j++) {
            int t = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = t;
        }
    }
    for (int[] row : matrix) {                      // reverse each row
        for (int lo = 0, hi = n - 1; lo < hi; lo++, hi--) {
            int t = row[lo];
            row[lo] = row[hi];
            row[hi] = t;
        }
    }
    return matrix;
}

Dry run on example 1:

Step Matrix
start [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
after transpose [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
after reversing rows [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Complexity. Time O(n^2): the transpose touches n(n-1)/2 pairs and the reversal touches every cell once. Space O(1): a single temporary per swap.

Two useful variations fall out of the same idea. For a counter-clockwise rotation, transpose and then reverse each column (or reverse rows first, then transpose). For a 180 degree rotation, reverse every row and then reverse the order of the rows.

Approach 3: Optimal, rotate four cells at a time

Intuition. Another way to see the rotation: every cell belongs to a cycle of four positions (top, right, bottom, left) that rotate among themselves. Peel the matrix into concentric rings. On the outer ring, the k-th element of the top row moves to the k-th element of the right column, which moves to the k-th element (counted from the right) of the bottom row, which moves to the k-th element (counted from the bottom) of the left column, which moves back to the top. Save one value, shift the other three along the cycle, then drop the saved value in. Each ring has n - 1 - 2·layer such cycles, and the rings shrink inward until the centre.

This version is more error-prone than transpose-and-reverse, but it is worth knowing because the same “cycle of positions” view appears in other in-place permutation problems.

Algorithm.

  1. For layer from 0 to n/2 - 1: let first = layer, last = n - 1 - layer.
  2. For k from first to last - 1, with offset = k - first:
    • save top = matrix[first][k],
    • left to top: matrix[first][k] = matrix[last - offset][first],
    • bottom to left: matrix[last - offset][first] = matrix[last][last - offset],
    • right to bottom: matrix[last][last - offset] = matrix[k][last],
    • top to right: matrix[k][last] = top.
static int[][] optimalCycles(int[][] matrix) {
    int n = matrix.length;
    for (int layer = 0; layer < n / 2; layer++) {
        int first = layer, last = n - 1 - layer;
        for (int k = first; k < last; k++) {
            int offset = k - first;
            int top = matrix[first][k];                                 // save top
            matrix[first][k] = matrix[last - offset][first];            // left   -> top
            matrix[last - offset][first] = matrix[last][last - offset]; // bottom -> left
            matrix[last][last - offset] = matrix[k][last];              // right  -> bottom
            matrix[k][last] = top;                                      // top    -> right
        }
    }
    return matrix;
}

Complexity. Time O(n^2): each cell is moved exactly once. Space O(1).

Edge cases and pitfalls