How do you solve Rotate Image?

Use two pointers, `l` and `r`, to represent the current layer's left and right boundaries. While `l < r`, iterate over the elements in the current layer and perform four-way swaps to rotate the elements clockwise. After processing a layer, move inward by incrementing `l` and decrementing `r`. This achieves an in-place rotation with O(1) auxiliary space and O(n²) time complexity.

Rotate Image

Q: What is the time complexity of Rotate Image?

O(n^2). Each element in the matrix is visited and moved exactly once during the layer-by-layer traversal, resulting in O(n²) operations for an n x n matrix.

Q: What pattern does Rotate Image use?

The Pattern: Matrix Traversal (Layer-by-Layer In-Place Transformation) The Heuristic: When rotating or transforming a matrix in-place, decompose the problem into layers and perform coordinated swaps of elements in groups (e.g., four-way swaps) to avoid extra space and maintain correctness.

Medium Matrix Traversal

Problem

Given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise) in-place.

matrix.length == n
matrix[i].length == n
1 ≤ n ≤ 20
−1000 ≤ matrix[i][j] ≤ 1000

Example

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

Output: [[7,4,1],[8,5,2],[9,6,3]]

The brute-force approach would create a new matrix and copy elements to their rotated positions, requiring O(n²) extra space. The optimal in-place approach rotates the matrix layer by layer, swapping four elements at a time. For the outer layer, the element at top-left moves to top-right, top-right to bottom-right, bottom-right to bottom-left, and bottom-left to top-left. This process repeats for each element in the layer and then proceeds inward to inner layers. The critical insight is that each rotation can be done by swapping four elements in place, eliminating the need for extra memory.

Approach

Straightforward Solution

A straightforward solution creates a new matrix and copies each element from the original matrix to its rotated position, which requires O(n²) extra space and is not in-place.

Core Observation

Rotating a matrix 90 degrees clockwise can be decomposed into rotating each layer of the matrix independently, swapping four corresponding elements at a time. Each element in the top row of a layer moves to the right column, the right column moves to the bottom row, the bottom row moves to the left column, and the left column moves to the top row.

Path to Optimal

Preview

The key insight is to perform the rotation in-place by processing the matrix layer by layer, from the outermost layer to the innermost. For each layer, iterate over the elements and perform a four-way swap to rotate the elements without extra space…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers, `l` and `r`, to represent the current layer's left and right boundaries. While `l < r`, iterate over the elements in the current layer and perform four-way swaps to rotate the elements clockwise…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n^2)

Each element in the matrix is visited and moved exactly once during the layer-by-layer traversal, resulting in O(n²) operations for an n x n matrix.

Space

O(1)

The rotation is performed in-place using only a fixed number of temporary variables for swapping, requiring constant auxiliary space regardless of input size.

Pattern Spotlight

Matrix Traversal (Layer-by-Layer In-Place Transformation)

When rotating or transforming a matrix in-place, decompose the problem into layers and perform coordinated swaps of elements in groups (e.g., four-way swaps) to avoid extra space and maintain correctness.

Solution

Python

1class Solution:
  def rotate(self, matrix: list[list[int]]) -> None:
      l, r = 0, len(matrix) - 1
4
      while l < r:
          for i in range(r - l):
              top, bottom = l, r
8
              top_left = matrix[top][l + i]
              
              matrix[top][l + i] = matrix[bottom - i][l]
12
              matrix[bottom - i][l] = matrix[bottom][r - i]
              
              matrix[bottom][r - i] = matrix[top + i][r]
              
              matrix[top + i][r] = top_left
          r -= 1
          l += 1

Step-by-Step Solution

Traverse Layers Using Two Pointers to Define Boundaries

3l, r = 0, len(matrix) - 1
5while l < r:
18    r -= 1
19    l += 1

Objective

To define the current layer boundaries and control the iteration over layers from outermost to innermost.

Key Insight

Using two pointers, `l` and `r`, to represent the left and right boundaries of the current layer allows systematic traversal from the outer layer inward. The condition `l < r` ensures that the traversal stops when all layers have been processed. This approach cleanly partitions the matrix into concentric square layers, each of which can be rotated independently.

Interview Quick-Check

Core Logic

Two pointers `l` and `r` mark the current layer's boundaries, enabling layer-by-layer traversal from outside in.

State & Boundaries

The loop continues while `l < r` because when `l == r`, the layer is a single center element that does not need rotation.

Perform Four-Way Element Swaps to Rotate Each Layer

To rotate the elements in the current layer by swapping four corresponding elements in place.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 3 Critical

l, r = 0, len(matrix) - 1

Initialize left and right pointers to mark the outermost layer boundaries.

Setting `l` to 0 and `r` to `len(matrix) - 1` defines the initial layer as the entire matrix, enabling systematic inward traversal of layers.

Line 5 Critical

while l < r:

Loop while the left pointer is less than the right pointer to process each layer.

The condition `l < r` ensures that the algorithm processes all layers from outermost to innermost, stopping when the pointers meet or cross, which means all layers are rotated.

Full line-by-line criticality + rationale for all 11 lines available on Pro.

Test Your Understanding

Why does rotating the matrix layer by layer with four-way swaps guarantee a correct in-place 90-degree rotation?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Rotate Image from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Rotate Image drill

or drill a free problem

1	`class Solution:`
2	`def rotate(self, matrix: list[list[int]]) -> None:`
3	`l, r = 0, len(matrix) - 1`
4
5	`while l < r:`
6	`for i in range(r - l):`
7	`top, bottom = l, r`
8
9	`top_left = matrix[top][l + i]`
10
11	`matrix[top][l + i] = matrix[bottom - i][l]`
12
13	`matrix[bottom - i][l] = matrix[bottom][r - i]`
14
15	`matrix[bottom][r - i] = matrix[top + i][r]`
16
17	`matrix[top + i][r] = top_left`
18	`r -= 1`
19	`l += 1`

3	`l, r = 0, len(matrix) - 1`
5	`while l < r:`
18	`r -= 1`
19	`l += 1`