Skip to content

Volume ITechnology

4.28.1 — Rotate Image ​

LeetCode 48 · Medium

The problem ​

Rotate an n × n matrix 90 degrees clockwise, in place.

Restating the Problem: You are given a 2D square matrix (like a photo or a checkerboard). You need to rotate it 90 degrees to the right. However, you are not allowed to create a new matrix to hold the answer; you must modify the given matrix directly.

  • Constraints to note: n is up to 20, which is very small, but you must do it in place (using O(1) extra memory).
  • Edge cases: n = 1 is an immediate return. Elements can be negative.
1 2 3        7 4 1
4 5 6   →    8 5 2
7 8 9        9 6 3

The brute force, and where it wastes work ​

The naive approach is to allocate a new n × n matrix, then iterate through the original matrix, copying matrix[i][j] to its new rotated position in the new matrix. After filling the new matrix, you copy all elements back to the original matrix. This requires O(n^2) extra space, which violates the "in place" requirement. We need a way to move elements without a full scratchpad.

The pattern ​

Working out the index arithmetic for a rotation directly is error-prone. There is a much easier route:

Transpose, then reverse each row.

Transpose flips the matrix over its main diagonal — swap matrix[i][j] with matrix[j][i].

1 2 3        1 4 7
4 5 6   →    2 5 8
7 8 9        3 6 9

Reverse each row.

1 4 7        7 4 1
2 5 8   →    8 5 2
3 6 9        9 6 3

Done. Two simple operations, each obviously correct, replacing one formula that is easy to get wrong.

Why it works ​

Transposing turns rows into columns: the top row 1 2 3 becomes the left column. A clockwise rotation should put the top row into the right column instead. Reversing each row flips left to right, moving that column to where it belongs.

Anticlockwise is the mirror: transpose, then reverse each column — or equivalently reverse the rows' order first and then transpose.

Worth deriving both once so you are not guessing under pressure.

The solution ​

python
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)

        # 1. transpose — swap across the main diagonal
        for i in range(n):  # (1)
            for j in range(i + 1, n):                  # (2) j starts at i+1
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]  # (3)

        # 2. reverse each row
        for row in matrix:  # (4)
            row.reverse()
ts
function rotate(matrix: number[][]): void {
  const n = matrix.length;

  for (let i = 0; i < n; i++) {  // (1)
    for (let j = i + 1; j < n; j++) {  // (2)
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];  // (3)
    }
  }

  for (const row of matrix) row.reverse();  // (4)
}

Line by line ​

Turning a square grid a quarter turn clockwise is the same as two simpler moves: flip it across its main diagonal, then reverse each row.

(1) Go through each row i.

(2) Only visit cells to the right of the diagonal, where j > i. Each swap handles a pair of cells, (i, j) and (j, i). If j started at 0, every pair would be swapped twice, which puts everything back where it started.

(3) Swap the cell with its mirror across the diagonal. This is called a transpose: rows become columns. Row 0 becomes column 0, and so on.

(4) Reverse each row. After the transpose, the first column of the original is in the first row, but in the wrong order for a clockwise turn. Reversing every row fixes that. Check it on the top-left corner: it must end up in the top-right corner. The transpose leaves it in place, and the reverse moves it to the end of row 0, the top-right. ✓

Trace ​

Take the 3 × 3 grid [[1, 2, 3], [4, 5, 6], [7, 8, 9]].

AfterGrid
start1 2 3 · 4 5 6 · 7 8 9
transpose1 4 7 · 2 5 8 · 3 6 9
reverse rows7 4 1 · 8 5 2 · 9 6 3

The result is the original turned a quarter turn clockwise.

Code Walkthrough:

  • Step 1 (Transpose): We loop over the rows with index i. For each row i, we loop j from i + 1 to n - 1. We swap matrix[i][j] with matrix[j][i]. This essentially turns rows into columns by reflecting elements across the top-left to bottom-right diagonal.
  • Step 2 (Reverse Rows): We loop over every row in the now-transposed matrix and reverse it. This reflects the matrix horizontally.

j starts at i + 1, not at 0. This is the only thing here that can be wrong. Looping j from 0 would swap every pair twice, undoing the transpose and leaving the matrix unchanged. Starting at i + 1 visits each pair above the diagonal exactly once.

Diagonal elements are never touched, which is correct — they stay where they are under a transpose.

row.reverse() is in-place in both languages, so no extra memory is used.

Edge cases ​

  • A 1 × 1 grid. Nothing changes.
  • A 2 × 2 grid. One swap in the transpose, then each row reversed.

Complexity ​

O(n^2) time — every element is touched a constant number of times. O(1) extra space.

  • Time Complexity: O(n^2). The transpose visits about half the elements (since we only loop j from i+1), and the reverse visits all elements. Both operations are proportional to the number of cells in the grid, which is n^2.
  • Space Complexity: O(1). We do everything by swapping elements in place, requiring no extra memory proportional to n.

O(n^2) is optimal, since every one of the n^2 elements has to move.

The layer-by-layer alternative ​

There is a direct method that rotates four elements at a time, walking inward ring by ring:

python
for layer in range(n // 2):
    first, last = layer, n - 1 - layer
    for i in range(first, last):
        offset = i - first
        top = matrix[first][i]
        matrix[first][i] = matrix[last - offset][first]
        matrix[last - offset][first] = matrix[last][last - offset]
        matrix[last][last - offset] = matrix[i][last]
        matrix[i][last] = top

Same complexity, one pass instead of two — and far harder to get right, because there are four index expressions that must all agree.

Write the transpose-and-reverse version. Mention this one exists if asked whether you can do it in a single pass.

Where this goes next ​

The transpose trick is a small toolkit for matrix problems:

operationrecipe
rotate 90° clockwisetranspose, reverse each row
rotate 90° anticlockwisetranspose, reverse each column
rotate 180°reverse rows and reverse each row
mirror horizontallyreverse each row
mirror verticallyreverse the row order
  • Spiral Matrix — a different traversal of the same grid. 4.28.2.
  • Set Matrix Zeroes — in-place again, using the first row and column as storage. 4.28.3.
  • Real graphics — a rotation is a matrix multiplication, and Volume II Part 4 derives why. Image libraries do exactly this for the 90-degree cases because it needs no arithmetic on the pixel values.

What the interviewer will push on ​

"Why does transpose plus reverse give a rotation?" Transposing sends the top row to the left column; reversing each row moves it to the right column, which is where a clockwise rotation puts it.

"Why does j start at i + 1?" Otherwise every pair is swapped twice and nothing changes. This is the question, and it is easy to check by tracing a 2×2.

"How would you rotate anticlockwise?" Transpose, then reverse the columns.

"Can you do it in one pass?" The four-way layer rotation. Say it is harder to get right.

"What if the matrix were not square?" The rotation changes the dimensions, so it cannot be done in place — you allocate an n × m result.

One thing to volunteer: give the full recipe table. It costs one sentence and covers every variation an interviewer might ask for.

Next: 4.28.2 Spiral Matrix — where the difficulty is entirely in the boundary conditions.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet