💬 Discord
Sign In
NeetCode #901LC-48MediumMath & GeometryBlind 75NC 150NC 250
← Back to All Problems

#901 · #48 · Rotate Image(旋转图像)

📌 Problem Statement & Constraints

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees clockwise, in place (do not allocate another matrix). Constraints: 1 <= n <= 20, -1000 <= matrix[i][j] <= 1000.

💡 Core Algorithmic Approaches

  1. A 90-degree clockwise rotation is equivalent to transposing the matrix and then reversing every row.
  2. The transpose swaps matrix[i][j] with matrix[j][i] for j > i, so each pair is exchanged exactly once.
  3. Reversing each row afterwards moves every element to its final position without any extra storage.
  4. An alternative is the 4-way cyclic swap of the corners of each concentric ring, which is also O(1) extra space but has fiddlier index arithmetic.

💻 Benchmark Python3 Implementation

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        # 1) transpose: swap across the main diagonal
        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        # 2) reverse each row
        for i in range(n):
            matrix[i].reverse()

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): every element is visited a constant number of times.
💾 Space Complexity
O(1): the rotation is performed entirely in place.

⚠️ Interview Pitfalls & Follow-ups

  • Iterating j from 0 instead of i + 1: that swaps each off-diagonal pair twice and cancels the transpose.
  • Reversing the columns instead of the rows: transpose plus row reversal is clockwise; reversing columns would produce a counter-clockwise rotation.
  • Allocating a second matrix: correct but O(n^2) space, which the in-place requirement forbids.
  • Returning the matrix: the method must modify in place and returns None.