Given a 2-d array matrix, return elements in spiral order starting from matrix[0][0].
Constraints
n, m ≤ 250 where n and m are the number of rows and columns in matrix
Example 1
Input
matrix = [ [6, 9, 8], [1, 8, 0], [5, 1, 2], [8, 0, 3], [1, 6, 4], [8, 8, 10] ]Output
Simulation Algorithm to Build a Spiral Matrix
The initial direction is right. We simulate walking to it until we are about to go outside the boundary or visit a pixel that has been visited before. Then, it is the time to turn 90 degree. We can store the direction offsets in a vector array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | vector<int> spiralMatrix(vector<vector<int>>& matrix) { int rows = matrix.size(); if (0 == rows) return {}; int cols = matrix[0].size(); if (0 == cols) return {}; vector<int> ans; int r = 0, c = 0, n = rows * cols - 1; bool vis[rows][cols]; memset(vis, false, sizeof vis); vector<vector<int>> dir({{0, 1}, {1, 0}, {0, -1}, {-1, 0}}); int di = 0; for (; n > 0; -- n) { ans.push_back(matrix[r][c]); vis[r][c] = true; for (;;) { auto d = dir[di]; int nr = r + d[0]; int nc = c + d[1]; if ((nr >= 0) && (nc >= 0) && (nr < rows) && (nc < cols) && (!vis[nr][nc])) { // continue same direction r = nr; c = nc; break; } else { // need to turn 90 clockwise di = (di + 1) % 4; } } } ans.push_back(matrix[r][c]); return ans; } |
vector<int> spiralMatrix(vector<vector<int>>& matrix) {
int rows = matrix.size();
if (0 == rows) return {};
int cols = matrix[0].size();
if (0 == cols) return {};
vector<int> ans;
int r = 0, c = 0, n = rows * cols - 1;
bool vis[rows][cols];
memset(vis, false, sizeof vis);
vector<vector<int>> dir({{0, 1}, {1, 0}, {0, -1}, {-1, 0}});
int di = 0;
for (; n > 0; -- n) {
ans.push_back(matrix[r][c]);
vis[r][c] = true;
for (;;) {
auto d = dir[di];
int nr = r + d[0];
int nc = c + d[1];
if ((nr >= 0) && (nc >= 0) && (nr < rows) && (nc < cols) && (!vis[nr][nc])) { // continue same direction
r = nr;
c = nc;
break;
} else { // need to turn 90 clockwise
di = (di + 1) % 4;
}
}
}
ans.push_back(matrix[r][c]);
return ans;
}We use a two dimensional boolean array to mark if a pixel that has been visited. The following uses a single direction vector {0, 1, 0, -1, 0} that index (x, x+1) is the 2D dimension direction offset.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | vector<int> spiralMatrix(vector<vector<int>>& matrix) { int rows = matrix.size(); if (0 == rows) return {}; int cols = matrix[0].size(); if (0 == cols) return {}; vector<int> ans; int r = 0, c = 0, n = rows * cols - 1; bool vis[rows][cols]; memset(vis, false, sizeof vis); vector<int> dir{0, 1, 0, -1, 0}; int di = 0; for (; n > 0; -- n) { ans.push_back(matrix[r][c]); vis[r][c] = true; for (;;) { int nr = r + dir[di]; int nc = c + dir[di + 1]; if ((nr >= 0) && (nc >= 0) && (nr < rows) && (nc < cols) && (!vis[nr][nc])) { r = nr; c = nc; break; } else { di = (di + 1) % 4; } } } ans.push_back(matrix[r][c]); return ans; } |
vector<int> spiralMatrix(vector<vector<int>>& matrix) {
int rows = matrix.size();
if (0 == rows) return {};
int cols = matrix[0].size();
if (0 == cols) return {};
vector<int> ans;
int r = 0, c = 0, n = rows * cols - 1;
bool vis[rows][cols];
memset(vis, false, sizeof vis);
vector<int> dir{0, 1, 0, -1, 0};
int di = 0;
for (; n > 0; -- n) {
ans.push_back(matrix[r][c]);
vis[r][c] = true;
for (;;) {
int nr = r + dir[di];
int nc = c + dir[di + 1];
if ((nr >= 0) && (nc >= 0) && (nr < rows) && (nc < cols) && (!vis[nr][nc])) {
r = nr;
c = nc;
break;
} else {
di = (di + 1) % 4;
}
}
}
ans.push_back(matrix[r][c]);
return ans;
}Both implementations take O(RC) time to finish and O(RC) space complexity – where R and C are the number of the rows, and the number of columns respectively.
See also: Algorithm to Generate the Spiral Matrix in Clock-wise Order
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Longest Palindromic Subsequence using Dynamic Programming Algorithm
Next Post: Teaching Kids Programming - Perfect Number Validation Algorithm
