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}}};
vector<int> values;
values.reserve(m * n);
for (int i = 0, dir = 0, left = 0, right = n - 1, up = 1, down = m - 1, r = 0, c = 0;
i < m * n;
++i) {
values.push_back(matrix[r][c]);
if (dir == 0 && c == right) {
dir = 1;
--right;
} else if (dir == 1 && r == down) {
dir = 2;
--down;
} else if (dir == 2 && c == left) {
dir = 3;
++left;
} else if (dir == 3 && r == up) {
dir = 0;
++up;
}
r += directions[dir].first;
c += directions[dir].second;
}
return values;
}
};