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.

Rotate Image - LeetCode Solution & Explanation

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.

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

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. This approach leverages the symmetry of the rotation and the fixed positions of elements in each layer.

Optimal Approach

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.

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.

Solution

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

1

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.

2

Perform Four-Way Element Swaps to Rotate Each Layer

6for i in range(r - l):
  top, bottom = l, r
  top_left = matrix[top][l + i]
  matrix[top][l + i] = matrix[bottom - i][l]
  matrix[bottom - i][l] = matrix[bottom][r - i]
  matrix[bottom][r - i] = matrix[top + i][r]
  matrix[top + i][r] = top_left

Objective

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

Key Insight

Each element in the top row of the current layer moves to the right column, the right column element moves to the bottom row, the bottom row element moves to the left column, and the left column element moves to the top row. By storing one element temporarily, the algorithm performs these four assignments in sequence, effectively rotating four elements at once. Iterating over the range `r - l` covers all elements in the current layer except the last, ensuring a complete rotation without overlap.

Interview Quick-Check

Core Logic

Four-way swaps rotate elements in groups of four, moving each to its rotated position without extra space.

Common Pitfalls & Bugs

Incorrect indexing or missing elements in the loop can cause incomplete rotation or overwrite values prematurely.

State & Boundaries

The loop runs from 0 to `r - l - 1` to avoid redundant swaps and to cover all elements in the current layer.

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.

Line 6 Standard

for i in range(r - l):

Iterate over the elements in the current layer to perform swaps.

Looping from 0 to `r - l - 1` covers all elements in the current layer's top row except the last, enabling rotation of each group of four corresponding elements.

Line 7 Standard

top, bottom = l, r

Assign top and bottom indices for the current layer.

Defining `top` and `bottom` as `l` and `r` respectively simplifies indexing and clarifies the layer boundaries for the swaps.

Line 9 Standard

top_left = matrix[top][l + i]

Store the top-left element temporarily before overwriting.

Temporarily saving the top-left element prevents its loss during the sequence of swaps, enabling a correct four-way rotation.

Line 11 Standard

matrix[top][l + i] = matrix[bottom - i][l]

Move the bottom-left element to the top-left position.

This assignment moves the element from the bottom-left corner of the current layer to the top-left position, part of the clockwise rotation.

Line 13 Standard

matrix[bottom - i][l] = matrix[bottom][r - i]

Move the bottom-right element to the bottom-left position.

This step continues the rotation by moving the bottom-right element to the bottom-left position, maintaining the cycle of four elements.

Line 15 Standard

matrix[bottom][r - i] = matrix[top + i][r]

Move the top-right element to the bottom-right position.

This assignment moves the top-right element to the bottom-right position, progressing the rotation cycle.

Line 17 Standard

matrix[top + i][r] = top_left

Assign the temporarily stored top-left element to the top-right position.

Completing the four-way swap, this step places the saved top-left element into the top-right position, finalizing the rotation of this group.

Line 18 Standard

r -= 1

Decrement the right pointer to move inward to the next layer.

Moving the right boundary inward prepares the algorithm to process the next inner layer in the subsequent iteration.

Line 19 Standard

l += 1

Increment the left pointer to move inward to the next layer.

Moving the left boundary inward complements the right pointer adjustment, ensuring the next layer is correctly bounded.

Test Your Understanding

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

Because each four-way swap moves four elements to their correct rotated positions simultaneously, and processing all layers ensures every element is moved exactly once without overlap or omission, achieving a full in-place rotation.

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`

6	`for i in range(r - l):`
7	`top, bottom = l, r`
9	`top_left = matrix[top][l + i]`
11	`matrix[top][l + i] = matrix[bottom - i][l]`
13	`matrix[bottom - i][l] = matrix[bottom][r - i]`
15	`matrix[bottom][r - i] = matrix[top + i][r]`
17	`matrix[top + i][r] = top_left`