Log inSign up
mediumLeetCodeNot Started

Rotate Image

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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.

Example 1 · 3x3 Square Matrix:

Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
Explanation: Step 1 (Transpose): [[1, 4, 7], [2, 5, 8], [3, 6, 9]] Step 2 (Reverse Rows): [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Example 2 · 4x4 Matrix:

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: Rotated 90 degrees clockwise in-place.

Example 3 · 1x1 Matrix:

Input: matrix = [[1]]
Output: [[1]]
Explanation: Single element remains unchanged.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 2D matrix indexing (matrix[row][col])
  • Matrix transposition fundamentals (main diagonal symmetry)
  • Two-pointer horizontal array reversal

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Deconstruct 2D spatial transformations into elementary matrix operations.
  • Perform in-place 2D coordinate swaps without clobbering symmetric values.
  • Formulate both Transpose + Reverse and Direct 4-way Ring Rotation approaches.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Rotating or reflecting a square 2D matrix.
  • Strict requirement to mutate matrix in-place with O(1) extra space.
  • 90 degree clockwise or counter-clockwise grid rotations.

Algorithmic Decision Tree:

  • When rotating 90 degrees Clockwise: Transpose along the main diagonal, then reverse each row.
  • When rotating 90 degrees Counter-Clockwise: Transpose along the main diagonal, then reverse each column (or reverse rows first, then transpose).

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Auxiliary Matrix Copy (Brute Force)

Intuition

Create an auxiliary matrix res of size n x n. For every row r from 0 to n-1 and column c from 0 to n-1, assign res[c][n - 1 - r] = matrix[r][c]. Finally, copy res back into matrix.

When to apply: Use to understand the mathematical rotation formula before optimizing to in-place.

Auxiliary Matrix Rotation Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current operationSTEP 1 OF 6
Matrix: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
1
↑ Row 0
2
3
r1
4
5
6
r2
7
8
9
Variables at this step
row
0
targetCol
2
Check / comparison
Source: row 0 is [1, 2, 3].
Decision / next transition
Row 0 maps to column 2 (n - 1 - 0 = 2).
Why this step matters

Matrix: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]. Allocate empty 3x3 auxiliary grid res.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public void rotate(int[][] matrix) {
6 int n = matrix.length;
7 int[][] res = new int[n][n];
8 for (int r = 0; r < n; r++) {
9 for (int c = 0; c < n; c++) {
10 res[c][n - 1 - r] = matrix[r][c];
11 }
12 }
13 for (int r = 0; r < n; r++) {
14 for (int c = 0; c < n; c++) {
15 matrix[r][c] = res[r][c];
16 }
17 }
18 }
19 }
20
21 public static void main(String[] args) {
22 Solution sol = new Solution();
23 int[][] matrix = {
24 {1, 2, 3},
25 {4, 5, 6},
26 {7, 8, 9}
27 };
28 sol.rotate(matrix);
29 System.out.println("Rotated matrix: " + Arrays.deepToString(matrix));
30 }
31}

Time & Space Complexity

  • Time complexity: O(n^2) — Visiting all n x n cells takes O(n2) operations.
  • Space complexity: O(n^2) — Requires an auxiliary n x n matrix.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. 4-Cell In-Place Cycle Rotation

Intuition

Rotate outer layers inward. For each layer from i=0 to n/2 - 1, rotate 4 elements cyclically: top, right, bottom, left.

When to apply: Use to achieve in-place rotation with minimal operations per cell.

4-Cell Cyclic Swap Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current operationSTEP 1 OF 6
Layer 0: Rotate corners (0,0)->1, (0,2)->3, (2,2)->9, (2,0)->7
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
7
↑ Corners
2
1
r1
4
5
6
r2
9
8
3
Variables at this step
temp
1
corners
[7,1,9,3]
Check / comparison
Cyclic 4-cell group.
Decision / next transition
Swap corners clockwise.
Why this step matters

Layer 0: Rotate corners (0,0)->1, (0,2)->3, (2,2)->9, (2,0)->7.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public void rotate(int[][] matrix) {
6 int n = matrix.length;
7 for (int i = 0; i < (n + 1) / 2; i++) {
8 for (int j = 0; j < n / 2; j++) {
9 int temp = matrix[n - 1 - j][i];
10 matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1];
11 matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 - i];
12 matrix[j][n - 1 - i] = matrix[i][j];
13 matrix[i][j] = temp;
14 }
15 }
16 }
17 }
18
19 public static void main(String[] args) {
20 Solution sol = new Solution();
21 int[][] matrix = {
22 {1, 2, 3},
23 {4, 5, 6},
24 {7, 8, 9}
25 };
26 sol.rotate(matrix);
27 System.out.println("Rotated matrix: " + Arrays.deepToString(matrix));
28 }
29}

Time & Space Complexity

  • Time complexity: O(n^2) — Each cell is moved exactly once in groups of 4.
  • Space complexity: O(1) — O(1) temporary variable for cycle swaps.

3. Transpose and Reverse Rows (Optimal & Standard)

Intuition

1. Transpose: Swap matrix[i][j] and matrix[j][i] for all i < j. 2. Reverse each row: For each row, reverse elements between col 0 and n - 1. Combining transpose and row reversal produces a 90 degree clockwise rotation.

When to apply: Use as the cleanest, most elegant industry standard for in-place matrix rotation.

Transpose + Row Reversal Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current operationSTEP 1 OF 6
Matrix: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
1
4
↑ Swap 2, 4
3
r1
2
5
6
r2
7
8
9
Variables at this step
transposedPairs
["(0,1)<->(1,0)"]
Check / comparison
Swap (0,1) with (1,0): 2 <-> 4.
Decision / next transition
matrix[0][1] = 4, matrix[1][0] = 2.
Why this step matters

Matrix: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]. Phase 1: Transpose across main diagonal (i < j).

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public void rotate(int[][] matrix) {
6 int n = matrix.length;
7 // Step 1: Transpose matrix
8 for (int i = 0; i < n; i++) {
9 for (int j = i + 1; j < n; j++) {
10 int temp = matrix[i][j];
11 matrix[i][j] = matrix[j][i];
12 matrix[j][i] = temp;
13 }
14 }
15 // Step 2: Reverse each row
16 for (int i = 0; i < n; i++) {
17 int left = 0, right = n - 1;
18 while (left < right) {
19 int temp = matrix[i][left];
20 matrix[i][left] = matrix[i][right];
21 matrix[i][right] = temp;
22 left++;
23 right--;
24 }
25 }
26 }
27 }
28
29 public static void main(String[] args) {
30 Solution sol = new Solution();
31 int[][] matrix = {
32 {1, 2, 3},
33 {4, 5, 6},
34 {7, 8, 9}
35 };
36 sol.rotate(matrix);
37 System.out.println("Rotated matrix: " + Arrays.deepToString(matrix));
38 }
39}

Time & Space Complexity

  • Time complexity: O(n^2) — Transpose performs n*(n-1)/2 swaps; horizontal row reversal performs n*(n/2) swaps.
  • Space complexity: O(1) — All operations occur strictly in-place.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Auxiliary 2D Matrix CloneO(N^2)O(N^2)Allocate an auxiliary N x N matrix and place each cell (r, c) into its rotated position (c, n - 1 - r).Repeated redundant scans over the input.
2.Approach 2: 4-Way Cyclic Ring RotationO(N^2)O(1)Rotate the matrix layer by layer from the outermost ring inward, swapping 4 corresponding elements cyclically.Auxiliary memory allocation or sorting step.
3.Approach 3: Transpose & Reverse Rows (Optimal & Cleanest)OptimalO(N^2)O(1)Rotate the matrix in two elegant linear steps: transpose along the main diagonal, then reverse each row.None. Asymptotically optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • 1x1 Matrix [[1]] — Input: `, Expected: ` —
  • 2x2 Matrix [[1, 2], [3, 4]] — Input: `, Expected: ` —
  • Even vs Odd Matrix Dimensions — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Rotate Image?

2.Why is the brute force approach suboptimal for large inputs in Rotate Image?

3.Which data structure or technique enables the optimal solution for Rotate Image?

Back to DSA Sheet