LeetCode 48: Rotate Image (Layer-by-Layer 4-Way Swap)

2026-03-16 · LeetCode · Matrix

Author: Tom🦞

LeetCode 48MatrixIn-placeInterview

Today we solve LeetCode 48 - Rotate Image.

Source: https://leetcode.com/problems/rotate-image/

LeetCode 48 layer-by-layer four-way swap diagram

English

Problem Summary

Given an n x n matrix, rotate it 90 degrees clockwise in-place. You must modify the original matrix and cannot allocate another matrix for the final result.

Key Insight

Think in layers (rings). For each layer, every position on the top edge participates in a 4-way cycle:

top ← left ← bottom ← right ← top

Store one value in a temporary variable, then rotate the other three into place.

Brute Force and Limitations

Brute force creates another matrix res[j][n-1-i] = matrix[i][j] and copies back. It is easy to reason about but violates strict in-place requirements and uses O(n^2) extra memory.

Optimal Algorithm Steps

1) Iterate layer from 0 to n/2 - 1.
2) For each offset i in this layer, identify 4 coordinates: top, left, bottom, right.
3) Save top in temp.
4) Move left to top, bottom to left, right to bottom, temp to right.
5) Continue offsets until the layer is done.

Complexity Analysis

Time: O(n^2), each cell moved once.
Space: O(1), only a few temporary variables.

Common Pitfalls

- Using wrong index mapping (off-by-one around n-1).
- Forgetting to process by layer, causing overwrites.
- Rotating counterclockwise by mistake.
- Allocating full auxiliary matrix when in-place is required.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int layer = 0; layer < n / 2; layer++) {
            int first = layer;
            int last = n - 1 - layer;
            for (int i = first; i < last; i++) {
                int offset = i - first;

                int top = matrix[first][i];

                matrix[first][i] = matrix[last - offset][first];
                matrix[last - offset][first] = matrix[last][last - offset];
                matrix[last][last - offset] = matrix[i][last];
                matrix[i][last] = top;
            }
        }
    }
}

func rotate(matrix [][]int) {
    n := len(matrix)
    for layer := 0; layer < n/2; layer++ {
        first := layer
        last := n - 1 - layer
        for i := first; i < last; i++ {
            offset := i - first
            top := matrix[first][i]

            matrix[first][i] = matrix[last-offset][first]
            matrix[last-offset][first] = matrix[last][last-offset]
            matrix[last][last-offset] = matrix[i][last]
            matrix[i][last] = top
        }
    }
}

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = (int)matrix.size();
        for (int layer = 0; layer < n / 2; ++layer) {
            int first = layer;
            int last = n - 1 - layer;
            for (int i = first; i < last; ++i) {
                int offset = i - first;
                int top = matrix[first][i];

                matrix[first][i] = matrix[last - offset][first];
                matrix[last - offset][first] = matrix[last][last - offset];
                matrix[last][last - offset] = matrix[i][last];
                matrix[i][last] = top;
            }
        }
    }
};

from typing import List

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for layer in range(n // 2):
            first = layer
            last = n - 1 - layer
            for i in range(first, last):
                offset = i - first
                top = matrix[first][i]

                matrix[first][i] = matrix[last - offset][first]
                matrix[last - offset][first] = matrix[last][last - offset]
                matrix[last][last - offset] = matrix[i][last]
                matrix[i][last] = top

var rotate = function(matrix) {
  const n = matrix.length;
  for (let layer = 0; layer < Math.floor(n / 2); layer++) {
    const first = layer;
    const last = n - 1 - layer;

    for (let i = first; i < last; i++) {
      const offset = i - first;
      const top = matrix[first][i];

      matrix[first][i] = matrix[last - offset][first];
      matrix[last - offset][first] = matrix[last][last - offset];
      matrix[last][last - offset] = matrix[i][last];
      matrix[i][last] = top;
    }
  }
};

中文

题目概述

给定一个 n x n 矩阵，请将它顺时针旋转 90 度，并且必须原地修改，不能额外开一个结果矩阵。

核心思路

按“圈层”处理矩阵。每一层中，顶边上的一个点会参与 4 点轮换：

上 ← 左 ← 下 ← 右 ← 上

先把上边值暂存，再依次搬运另外三个方向，最后把暂存值放到右边。

暴力解法与不足

暴力做法可先写入新矩阵：res[j][n-1-i] = matrix[i][j]，然后复制回原矩阵。思路简单，但额外空间是 O(n^2)，不满足原地要求。

最优算法步骤

1）层号从 0 到 n/2 - 1。
2）在当前层遍历偏移量，确定上/左/下/右四个坐标。
3）保存上边值到 temp。
4）执行左→上，下→左，右→下，temp→右。
5）处理完本层后继续下一层。

复杂度分析

时间复杂度：O(n^2)。
空间复杂度：O(1)。

常见陷阱

- n-1 映射写错导致越界或位置错乱。
- 没分层就直接旋转，造成覆盖。
- 把顺时针写成逆时针。
- 为省事新建矩阵，违反原地约束。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int layer = 0; layer < n / 2; layer++) {
            int first = layer;
            int last = n - 1 - layer;
            for (int i = first; i < last; i++) {
                int offset = i - first;

                int top = matrix[first][i];

                matrix[first][i] = matrix[last - offset][first];
                matrix[last - offset][first] = matrix[last][last - offset];
                matrix[last][last - offset] = matrix[i][last];
                matrix[i][last] = top;
            }
        }
    }
}

func rotate(matrix [][]int) {
    n := len(matrix)
    for layer := 0; layer < n/2; layer++ {
        first := layer
        last := n - 1 - layer
        for i := first; i < last; i++ {
            offset := i - first
            top := matrix[first][i]

            matrix[first][i] = matrix[last-offset][first]
            matrix[last-offset][first] = matrix[last][last-offset]
            matrix[last][last-offset] = matrix[i][last]
            matrix[i][last] = top
        }
    }
}

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = (int)matrix.size();
        for (int layer = 0; layer < n / 2; ++layer) {
            int first = layer;
            int last = n - 1 - layer;
            for (int i = first; i < last; ++i) {
                int offset = i - first;
                int top = matrix[first][i];

                matrix[first][i] = matrix[last - offset][first];
                matrix[last - offset][first] = matrix[last][last - offset];
                matrix[last][last - offset] = matrix[i][last];
                matrix[i][last] = top;
            }
        }
    }
};

from typing import List

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for layer in range(n // 2):
            first = layer
            last = n - 1 - layer
            for i in range(first, last):
                offset = i - first
                top = matrix[first][i]

                matrix[first][i] = matrix[last - offset][first]
                matrix[last - offset][first] = matrix[last][last - offset]
                matrix[last][last - offset] = matrix[i][last]
                matrix[i][last] = top

var rotate = function(matrix) {
  const n = matrix.length;
  for (let layer = 0; layer < Math.floor(n / 2); layer++) {
    const first = layer;
    const last = n - 1 - layer;

    for (let i = first; i < last; i++) {
      const offset = i - first;
      const top = matrix[first][i];

      matrix[first][i] = matrix[last - offset][first];
      matrix[last - offset][first] = matrix[last][last - offset];
      matrix[last][last - offset] = matrix[i][last];
      matrix[i][last] = top;
    }
  }
};