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 . The goal is to rotate this entire grid by 90 degrees clockwise in-place.
Key Constraints:
- In-Place Modification: We cannot allocate another space for the result; we must modify
matrixdirectly. This rules out creating a new matrix and copying data into it. - Square Matrix: The input is guaranteed to be square ().
- Values: Integers (positive, negative) do not affect logic but imply standard integer types.
Implicit Edge Cases:
- : A single element matrix remains unchanged after rotation.
- Empty Matrix: Constraints specify
matrix.length == nand1 <= 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 in a 90-degree clockwise rotation. The mapping formula maps an element at row , column to row , column . 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:
- Transpose: Swap rows and columns across the main diagonal (top-left to bottom-right). This turns into . Visually, this reflects elements across the line .
- 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 and use only constant extra space for swapping variables.
Approach
- Transpose: Iterate through the upper triangle of the matrix (where column index
j> row indexi). Swap elements at(matrix[i][j], matrix[j][i]). This ensures we don’t swap twice or process redundant pairs. - 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. - Combine these steps: The final state matches the rotated image exactly without allocating a new grid structure.
Complexity Analysis
- Time Complexity: . We visit every element in the matrix once during transposition and again (or partially) during reversal to swap elements into place. Since there are total cells, this is linear with respect to the number of pixels/elements.
- Space Complexity: 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 (): The loops range from 0 to 0. Transpose loop
range(1)runs once but innerjstarts ati+1, so it doesn’t run. Reverse row swaps nothing since pointers meet immediately. Result is unchanged, which is correct for a 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 space requirements relative to input size.