59. Spiral Matrix II
1. Description
Given a positive integer n, generate an n x n matrix filled with elements from 1 to $n^2$ in spiral order.
2. Example
Example 1:
Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]
Example 2:
Input: n = 1
Output: [[1]]
3. Constraints
- 1 <= n <= 20
4. Solutions
My Accepted Solution
Time complexity: O($n^2$)
Space complexity: O($n^2$)
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
unordered_map<int, pair<int, int>> dirPositionChanges = {
// 0, 1, 2, 3 means right, down, left, up
// the pair means the row and column's step
{0, {0, 1}}, {1, {1, 0}}, {2, {0, -1}}, {3, {-1, 0}}};
unordered_map<int, int> dirBorders = {{0, n - 1}, {1, n - 1}, {2, 0}, {3, 0}};
vector<vector<int>> matrix(n, vector<int>(n));
for (int i = 1, dir = 0, row = 0, column = 0, size = n * n; i <= size; i++) {
matrix[row][column] = i;
if (dir == 0 && column == dirBorders[dir]) {
++dirBorders[3];
dir = (dir + 1) % 4;
} else if (dir == 1 && row == dirBorders[dir]) {
--dirBorders[0];
dir = (dir + 1) % 4;
} else if (dir == 2 && column == dirBorders[dir]) {
--dirBorders[1];
dir = (dir + 1) % 4;
} else if (dir == 3 && row == dirBorders[dir]) {
++dirBorders[2];
dir = (dir + 1) % 4;
}
row += dirPositionChanges[dir].first; // use map to get step, let the code more neat
column += dirPositionChanges[dir].second;
}
return matrix;
}
};
// more neat. but slower
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
unordered_map<int, pair<int, int>> dirPositionChanges = {
{0, {0, 1}}, {1, {1, 0}}, {2, {0, -1}}, {3, {-1, 0}}};
unordered_map<int, int> dirBorders = {{0, n - 1}, {1, n - 1}, {2, 0}, {3, 0}};
unordered_map<int, pair<int, int>> dirBordersChange = {
{0, {3, 1}}, {1, {0, -1}}, {2, {1, -1}}, {3, {2, 1}}};
vector<vector<int>> matrix(n, vector<int>(n));
for (int i = 1, dir = 0, row = 0, column = 0, size = n * n; i <= size; i++) {
matrix[row][column] = i;
if (dir == 0 && column == dirBorders[dir] || dir == 1 && row == dirBorders[dir] ||
dir == 2 && column == dirBorders[dir] || dir == 3 && row == dirBorders[dir]) {
dirBorders[dirBordersChange[dir].first] += dirBordersChange[dir].second;
dir = (dir + 1) % 4;
}
row += dirPositionChanges[dir].first;
column += dirPositionChanges[dir].second;
}
return matrix;
}
};