Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].
The Idea: Iterate between moving right, down, left, up respectfully and collect the elements as you get across them. Mark the trail you leave behind with INT_MIN, so when you encounter it, you either move in the next direction or stop entirely.
Complexity: O(n*m) and O(1) _extra _space
vector<int> spiralOrder(vector<vector<int>>& matrix)
{
using v = vector<int>;
using dv = vector<v>;
if (matrix.empty()) return v();
const size_t rows = matrix.size(), cols = matrix[0].size();
int num_times_to_loop = (2 * min(rows, cols)) - 1;
v spiral_order; spiral_order.reserve(num_times_to_loop);
auto right = [&](int &row, int &col) {
while (col < cols &&
matrix[row][col] != INT_MIN) {
spiral_order.push_back(matrix[row][col]);
matrix[row][col++] = INT_MIN;
}
col--; row++;
};
auto down = [&](int &row, int &col) {
while (row < rows &&
matrix[row][col] != INT_MIN) {
spiral_order.push_back(matrix[row][col]);
matrix[row++][col] = INT_MIN;
}
row--; col--;
};
auto left = [&](int &row, int &col) {
while (col >= 0 &&
matrix[row][col] != INT_MIN) {
spiral_order.push_back(matrix[row][col]);
matrix[row][col--] = INT_MIN;
}
col++; row--;
};
auto up = [&](int &row, int &col) {
while (row >= 0 &&
matrix[row][col] != INT_MIN) {
spiral_order.push_back(matrix[row][col]);
matrix[row--][col] = INT_MIN;
}
row++; col++;
};
vector<std::function<void(int &, int &)>> functors = { right, down, left, up };
int row = 0, col = 0;
int function_wrapper = 0;
while (cols >= 0 && rows >= 0 &&
col < cols && row < rows &&
matrix[row][col] != INT_MIN) {
functors.at(function_wrapper % functors.size())(row, col);
function_wrapper++;
}
return spiral_order;
}