54. Spiral Matrix
1. Description
Given an m x n matrix, return all elements of the matrix in spiral order.
2. Example
Example 1
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Example 2
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
3. Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 10
- -100 <= matrix[i][j] <= 100
4. Solutions
Simulation
m = matrix.size(), n = matrix.front().size()
Time complexity: O(mn)
Space complexity: O(1)
class Solution {
public:
vector<int> spiralOrder(const vector<vector<int>> &matrix) {
const int m = matrix.size(), n = matrix.front().size();
const array<pair<int, int>, 4> directions{{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
int top_border = 0, right_border = n - 1, bottom_border = m - 1, left_border = 0;
vector<int> values;
values.reserve(m * n);
for (int i = 0, r = 0, c = 0, dir_index = 0; i < m * n; ++i) {
values.push_back(matrix[r][c]);
if (dir_index == 0 && c == right_border) {
++top_border;
dir_index = 1;
} else if (dir_index == 1 && r == bottom_border) {
--right_border;
dir_index = 2;
} else if (dir_index == 2 && c == left_border) {
--bottom_border;
dir_index = 3;
} else if (dir_index == 3 && r == top_border) {
++left_border;
dir_index = 0;
}
r += directions[dir_index].first;
c += directions[dir_index].second;
}
return values;
}
};