# 54. Spiral Matrix
You are given an n x n 2D matrix representing an image.
Rotate the image 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.
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]
]
# Solution
Approach 1: Layer by layer or step by step.
# Code (Python)
Approach 1:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
# layer by layer
if not matrix or not matrix[0]:
return []
height, width = len(matrix), len(matrix[0])
layer = 0
direction = 0
result = []
while len(result) < height * width:
if direction == 0:
result.extend(matrix[layer][layer:width-layer])
elif direction == 1:
result.extend((matrix[row][width-layer-1] for row in range(layer + 1, height - layer)))
elif direction == 2:
result.extend(matrix[height-layer-1][layer:width-layer-1][::-1])
else:
result.extend([matrix[row][layer] for row in range(layer + 1, height - layer - 1)][::-1])
layer += 1
direction = (direction + 1) % 4
return result
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
# step by step
# this solution edits the matrix to mark them as visited
if not matrix or not matrix[0]:
return []
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
current = (0, 0)
result = []
current_direction = 0
while True: # OR: while len(result) < len(matrix) * len(matrix)[0]
result.append(matrix[current[0]][current[1]])
matrix[current[0]][current[1]] = '-'
next_position = self._generate_next(current, current_direction, directions, matrix)
if next_position:
current = next_position
else:
current_direction = (current_direction + 1) % 4
next_position = self._generate_next(current, current_direction, directions, matrix)
if next_position:
current = next_position
else:
break
return result
def _generate_next(self, coord, direction, directions, matrix):
next_coord = (coord[0] + directions[direction][0], coord[1] + directions[direction][1])
if 0 <= next_coord[0] < len(matrix) and 0 <= next_coord[1] < len(matrix[0]) and matrix[next_coord[0]][next_coord[1]] != '-':
return next_coord
else:
return None
# Code (C++)
Approach 1:
class Solution {
private:
int nextStep[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> spiral;
int m = matrix.size();
if (m == 0) return spiral;
int n = matrix[0].size();
int rowHead = 0;
int rowTail = m - 1;
int colHead = 0;
int colTail = n - 1;
while (rowHead < rowTail && colHead < colTail)
{
/*
// Layer by layer.
// e.g., 1 2 3
// 4 5 6
// 7 8 9
// We do: 1->2, 3->6, 9->8, 7->4.
for (int col = colHead; col < colTail; ++col)
{
spiral.push_back(matrix[rowHead][col]);
}
for (int row = rowHead; row < rowTail; ++row)
{
spiral.push_back(matrix[row][colTail]);
}
for (int col = colTail; col > colHead; --col)
{
spiral.push_back(matrix[rowTail][col]);
}
for (int row = rowTail; row > rowHead; --row)
{
spiral.push_back(matrix[row][colHead]);
}
*/
// Step by step.
int row = rowHead;
int col = colHead;
int stepIdx = 0;
do
{
spiral.push_back(matrix[row][col]);
int nextRow = row + nextStep[stepIdx][0];
int nextCol = col + nextStep[stepIdx][1];
if (nextRow < rowHead || nextRow > rowTail || nextCol < colHead || nextCol > colTail)
{
stepIdx = (stepIdx + 1) % 4;
}
row += nextStep[stepIdx][0];
col += nextStep[stepIdx][1];
}
while (row != rowHead || col != colHead);
rowHead++;
rowTail--;
colHead++;
colTail--;
}
// e.g., 1 2 3 1 1 2 3
// 4 5 6 or 2 or
// 7 8 9 3
if (rowHead == rowTail)
{
for (int col = colHead; col <= colTail; ++col)
{
spiral.push_back(matrix[rowHead][col]);
}
}
else if (colHead == colTail) // need to be "else if".
{
for (int row = rowHead; row <= rowTail; ++row)
{
spiral.push_back(matrix[row][colHead]);
}
}
return spiral;
}
};