TIC
The Interns Company

Rotate Image

MediumAcceptance: 64.8%
ArrayMatrixMath

Problem Statement

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Constraints:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

Input Format:

  • An n x n 2D matrix representing an image

Output Format:

  • The same matrix rotated 90 degrees clockwise

Examples:

Example 1:

Input:

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

Output:

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

Explanation:

The input matrix is rotated 90 degrees clockwise.

Example 2:

Input:

matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]

Output:

[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Explanation:

The input matrix is rotated 90 degrees clockwise.

Solutions

Transpose and Reverse

Time: O(n²)
Space: O(1)

First transpose the matrix (swap rows with columns), then reverse each row. This effectively rotates the matrix 90 degrees clockwise.

Rotate Four Cells at a Time

Time: O(n²)
Space: O(1)

Rotate the matrix layer by layer. For each layer, rotate the elements in groups of 4 cells in a circular manner.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Transpose the matrix (swap rows with columns):
  2. Swap (0,1) with (1,0): matrix becomes [[1,4,3],[2,5,6],[7,8,9]]
  3. Swap (0,2) with (2,0): matrix becomes [[1,4,7],[2,5,6],[3,8,9]]
  4. Swap (1,2) with (2,1): matrix becomes [[1,4,7],[2,5,8],[3,6,9]]
  5. Reverse each row:
  6. Reverse row 0: [1,4,7] -> [7,4,1]
  7. Reverse row 1: [2,5,8] -> [8,5,2]
  8. Reverse row 2: [3,6,9] -> [9,6,3]
  9. Final matrix: [[7,4,1],[8,5,2],[9,6,3]]

Hints

Hint 1
Think about rotating the matrix layer by layer.
Hint 2
For each layer, rotate the elements in groups of 4.
Hint 3
Another approach is to first transpose the matrix, then reverse each row.

Video Tutorial

Rotate Image - Step by Step Visualization

YouTube•Learn the Rotate Image solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the matrix transformation step by step, first transposing and then reversing each row, or rotating layer by layer.

Key visualization elements:

  • current cell
  • swapped cells
  • current layer

Similar Questions

Set Matrix Zeroes

Medium

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's. You must do it in place.

Spiral Matrix

Medium

Given an m x n matrix, return all elements of the matrix in spiral order.

Asked By

AmazonMicrosoftAppleGoogleFacebookBloombergAdobe

Implementation Notes

This problem tests understanding of matrix manipulation and in-place operations. The key insight is that a 90-degree clockwise rotation can be achieved by either transposing then reversing rows, or by rotating elements in groups of 4 in a circular manner.