Rotate Matrix 90 Degrees
Rotate an n×n matrix 90 degrees clockwise in-place using an elegant two-step process: transpose then reverse each row. This classic array manipulation problem demonstrates how complex transformations can be decomposed into simple operations. The in-place approach requires O(1) extra space, making it optimal for memory-constrained environments. Common in image processing, game development, and graphics programming.
Visualization
Interactive visualization for Rotate Matrix 90 Degrees
Interactive visualization with step-by-step execution
Implementation
1function rotate(matrix: number[][]): void {
2 const n = matrix.length;
3
4 // Transpose
5 for (let i = 0; i < n; i++) {
6 for (let j = i + 1; j < n; j++) {
7 [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
8 }
9 }
10
11 // Reverse each row
12 for (let i = 0; i < n; i++) {
13 matrix[i].reverse();
14 }
15}
16
17// Layer by layer approach
18function rotateLayered(matrix: number[][]): void {
19 const n = matrix.length;
20
21 for (let layer = 0; layer < Math.floor(n / 2); layer++) {
22 const first = layer;
23 const last = n - 1 - layer;
24
25 for (let i = first; i < last; i++) {
26 const offset = i - first;
27 const top = matrix[first][i];
28
29 // left -> top
30 matrix[first][i] = matrix[last - offset][first];
31
32 // bottom -> left
33 matrix[last - offset][first] = matrix[last][last - offset];
34
35 // right -> bottom
36 matrix[last][last - offset] = matrix[i][last];
37
38 // top -> right
39 matrix[i][last] = top;
40 }
41 }
42}Deep Dive
Theoretical Foundation
Rotating a matrix 90° clockwise can be decomposed into two operations: (1) Transpose (swap matrix[i][j] with matrix[j][i] for all i<j), converting rows to columns. (2) Reverse each row left-to-right. Example: [[1,2,3],[4,5,6],[7,8,9]] → transpose → [[1,4,7],[2,5,8],[3,6,9]] → reverse rows → [[7,4,1],[8,5,2],[9,6,3]]. For counter-clockwise: transpose then reverse each column. For 180°: reverse all rows then reverse all columns. Time O(n²) as we touch each element once per operation. Space O(1) in-place.
Complexity
Time
O(n²)
O(n²)
O(n²)
Space
O(1)
Applications
Industry Use
Image rotation in photo editors (Photoshop, GIMP)
Game development (rotating game boards, Tetris pieces)
Computer graphics transformations
QR code orientation correction
Document scanning and OCR preprocessing
Augmented reality marker detection
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.