Problem
Given an m×n matrix, return all elements in spiral order (right, down, left, up, repeat).
Example
Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]Solution
Track four boundaries (top, bottom, left, right) and shrink them after each direction.
def spiral_order(matrix):
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for j in range(left, right + 1): result.append(matrix[top][j])
top += 1
for i in range(top, bottom + 1): result.append(matrix[i][right])
right -= 1
if top <= bottom:
for j in range(right, left - 1, -1): result.append(matrix[bottom][j])
bottom -= 1
if left <= right:
for i in range(bottom, top - 1, -1): result.append(matrix[i][left])
left += 1
return resultfunction spiralOrder(matrix) {
const result = [];
let top = 0, bottom = matrix.length - 1;
let left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (let j = left; j <= right; j++) result.push(matrix[top][j]);
top++;
for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
right--;
if (top <= bottom) {
for (let j = right; j >= left; j--) result.push(matrix[bottom][j]);
bottom--;
}
if (left <= right) {
for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
left++;
}
}
return result;
}vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> result;
int top = 0, bottom = matrix.size() - 1;
int left = 0, right = matrix[0].size() - 1;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) result.push_back(matrix[top][j]);
top++;
for (int i = top; i <= bottom; i++) result.push_back(matrix[i][right]);
right--;
if (top <= bottom) {
for (int j = right; j >= left; j--) result.push_back(matrix[bottom][j]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) result.push_back(matrix[i][left]);
left++;
}
}
return result;
}public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) result.add(matrix[top][j]);
top++;
for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
right--;
if (top <= bottom) {
for (int j = right; j >= left; j--) result.add(matrix[bottom][j]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
left++;
}
}
return result;
}Complexity
- Time: O(m * n)
- Space: O(1) extra
Explanation
After traversing each side, shrink the boundary inward. The two extra checks prevent re-visiting the middle row/column when the matrix is rectangular.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?