Square Matrix In-Place Rotation
Algorithm · Core
Step through it: Matrix Traversal pattern
islands = 0
Step 1 of 6
Goal: count the islands of 1s in this grid (0 is water). Treat the grid as a map where each cell touches its neighbours above, below, left and right. Scan the cells one by one.
Step 2 of 6
The first land cell we meet is row 1, column 2. A new island starts here.
Step 3 of 6
Spread out: look at its four neighbours. The cell below, row 2 column 2, is land too.
Step 4 of 6
Keep spreading from each new land cell: row 2 columns 1 and 3 join, then row 3 column 2.
Step 5 of 6
The whole island is found. Mark its cells as visited so the scan never counts them again. Answer: 1 island. Each cell is looked at a few times, so the work is rows × columns. This is matrix traversal.
Step 6 of 6
Your turn.
The Problem
You are given an n x n 2D matrix (representing an image).
Rotate the matrix by 90 degrees (clockwise).
Note
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.
Examples
Example #1
Given input matrix:
[
[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
]Rotate the input matrix in-place such that it becomes:
[
[7, 4, 1],
[8, 5, 2],
[9, 6, 3],
]Example #2
Given input matrix:
[
[5, 1, 9, 11],
[2, 4, 8, 10],
[13, 3, 6, 7],
[15, 14, 12, 16],
]Rotate the input matrix in-place such that it becomes:
[
[15, 13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7, 10, 11],
]Algorithm
We would need to do two reflections of the matrix:
- reflect vertically
- reflect diagonally from bottom-left to top-right
Or we also could Furthermore, you can reflect diagonally top-left/bottom-right and reflect horizontally.
A common question is how do you even figure out what kind of reflections to do? Simply rip a square piece of paper, write a random word on it so you know its rotation. Then, flip the square piece of paper around until you figure out how to come to the solution.
Here is an example of how first line may be rotated using diagonal top-right/bottom-left rotation along with horizontal rotation.
Let's say we have a string at the top of the matrix:
A B C
• • •
• • •
Let's do top-right/bottom-left diagonal reflection:
A B C
/ / •
/ • •
And now let's do horizontal reflection:
A → →
B → →
C → →
The string has been rotated to 90 degree:
• • A
• • B
• • CCode
/**
* @param {*[][]} originalMatrix
* @return {*[][]}
*/
export default function squareMatrixRotation(originalMatrix) {
const matrix = originalMatrix.slice();
// Do top-right/bottom-left diagonal reflection of the matrix.
for (let rowIndex = 0; rowIndex < matrix.length; rowIndex += 1) {
for (let columnIndex = rowIndex + 1; columnIndex < matrix.length; columnIndex += 1) {
// Swap elements.
[
matrix[columnIndex][rowIndex],
matrix[rowIndex][columnIndex],
] = [
matrix[rowIndex][columnIndex],
matrix[columnIndex][rowIndex],
];
}
}
// Do horizontal reflection of the matrix.
for (let rowIndex = 0; rowIndex < matrix.length; rowIndex += 1) {
for (let columnIndex = 0; columnIndex < matrix.length / 2; columnIndex += 1) {
// Swap elements.
[
matrix[rowIndex][matrix.length - columnIndex - 1],
matrix[rowIndex][columnIndex],
] = [
matrix[rowIndex][columnIndex],
matrix[rowIndex][matrix.length - columnIndex - 1],
];
}
}
return matrix;
}References
Practice
Matrix Traversal
- Flood FillEasy
- Island PerimeterEasy
- Transpose MatrixEasy
- Toeplitz MatrixEasy
- Number of IslandsMedium
- Max Area of IslandMedium
- Surrounded RegionsMedium
- Spiral MatrixMedium
- Rotate ImageMedium
- Set Matrix ZeroesMedium
- Game of LifeMedium
- Word SearchMedium
- Number of EnclavesMedium
- Spiral Matrix IIMedium
- Diagonal TraverseMedium
- Search a 2D Matrix IIMedium
- Longest Increasing Path in a MatrixHard
- Word Search IIHard
Spotted a mistake or something unclear? Report it on GitHub.