Domain 2MediumCORE

Rotate Image

We are given a square 2D matrix representing an image grid of size $n times n$. The goal is to rotate this entire grid by 90 degrees clockwise in-place.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array

48. Rotate Image

Model: qwen3.5:9b
Topics: Array
FAANG asked: 1
Acceptance rate: 60.5%


Problem Breakdown

We are given a square 2D matrix representing an image grid of size n×nn \times n. The goal is to rotate this entire grid by 90 degrees clockwise in-place.

Key Constraints:

  1. In-Place Modification: We cannot allocate another O(n2)O(n^2) space for the result; we must modify matrix directly. This rules out creating a new matrix and copying data into it.
  2. Square Matrix: The input is guaranteed to be square (n×nn \times n).
  3. Values: Integers (positive, negative) do not affect logic but imply standard integer types.

Implicit Edge Cases:

  • n=1n=1: A single element matrix remains unchanged after rotation.
  • Empty Matrix: Constraints specify matrix.length == n and 1 <= n, so an empty input is technically out of scope based on the problem statement, though the algorithm naturally handles it gracefully if encountered (loops simply do not execute).

Intuition

A brute-force approach would be to calculate the new coordinates for every element (i,j)(i, j) in a 90-degree clockwise rotation. The mapping formula maps an element at row rr, column cc to row cc, column n−1−rn-1-r. While this gives us the correct destination indices, filling it into a pre-existing structure without overwriting data prematurely is tricky if we try to do it in one pass (we’d overwrite source values before reading them).

To solve strictly in-place, we need an algorithm that rearranges elements using swaps. Geometrically, rotating a matrix 90 degrees clockwise can be decomposed into two simpler transformations:

  1. Transpose: Swap rows and columns across the main diagonal (top-left to bottom-right). This turns (i,j)(i, j) into (j,i)(j, i). Visually, this reflects elements across the line y=xy = x.
  2. Reverse Rows: After transposing, each column becomes a row in reverse order relative to where they need to be for rotation. Reversing every individual row completes the transformation.

Why this works:

  • Transpose aligns columns into rows but keeps them “upside down” (or left-right flipped) compared to the target orientation.
  • Flipping each row horizontally corrects that specific alignment, resulting in a 90-degree clockwise rotation. Both steps are O(n2)O(n^2) and use only constant extra space for swapping variables.

Approach

  1. Transpose: Iterate through the upper triangle of the matrix (where column index j > row index i). Swap elements at (matrix[i][j], matrix[j][i]). This ensures we don’t swap twice or process redundant pairs.
  2. Reverse Rows: For each row in the transposed matrix, use two pointers (left, right) to reverse the order of elements within that specific row until they meet.
  3. Combine these steps: The final state matches the rotated image exactly without allocating a new grid structure.

Complexity Analysis

  • Time Complexity: O(n2)O(n^2). We visit every element in the matrix once during transposition and again (or partially) during reversal to swap elements into place. Since there are n×nn \times n total cells, this is linear with respect to the number of pixels/elements.
  • Space Complexity: O(1)O(1) auxiliary space. We only use a few integer variables for loop indices (i, j) and temporary storage during swaps. No new matrix or list structures are allocated beyond standard Python variable overhead.

Solution

def rotate(matrix):
    n = len(matrix)
    
    # Step 1: Transpose the matrix (swap across 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]
            
    # Step 2: Reverse each row individually
    for r in range(n):
        left, right = 0, n - 1
        while left < right:
            matrix[r][left], matrix[r][right] = \
                matrix[r][right], matrix[r][left]
            left += 1
            right -= 1
            
    return matrix

# Example usage (not required for submission but good for verification)
# rotate([[1,2],[3,4]]) -> [[3,1],[4,2]]

Edge Cases Handled

  • Single Element (n=1n=1): The loops range from 0 to 0. Transpose loop range(1) runs once but inner j starts at i+1, so it doesn’t run. Reverse row swaps nothing since pointers meet immediately. Result is unchanged, which is correct for a 1×11 \times 1 matrix rotated by 90 degrees.
  • Negative Values: The logic relies only on indices and swapping references; the integer values themselves do not impact control flow or memory layout in Python (references are swapped), so negative numbers work identically to positive ones.
  • Memory Constraints: By using explicit index-based swaps (matrix[r][left] = ...) rather than slicing assignment, we avoid creating intermediate list objects for rows during the reversal step, adhering strictly to O(1)O(1) space requirements relative to input size.