# 59 Spiral Matrix II

Given an integern, generate a square matrix filled with elements from 1 ton2in spiral order.
For example, Givenn=`3`,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
Complexity: O(n) time and space The Idea: Had fun with this one. Basically I've defined 4 functions that do one thing - iterate left, right, up and down. Then I wrap these up in a vector and invoke them over and over again over a wrapping modulus with the right parameterizations. I thought it was pretty elegant.
vector<vector<int>> generateMatrix(int n)
{
using dv = vector<vector<int>>;
if (!n) return dv();
dv spiral_m(n, vector<int>(n));
int incr = 1;
auto right = [&](int &row, int &col, dv &spiral_m, int n, int &incr) {
while (col < n &&
spiral_m[row][col] == 0) {
spiral_m[row][col] = incr++;
col++;
}
// finished - so backtrack once and move down 1
col--; row++;
};
auto down = [&](int &row, int &col, dv &spiral_m, int n, int &incr) {
while (row < n &&
spiral_m[row][col] == 0) {
spiral_m[row][col] = incr++;
row++;
}
// finished - so backtrack once and left 1
row--; col--;
};
auto left = [&](int &row, int &col, dv &spiral_m, int n, int &incr) {
while (col >= 0 &&
spiral_m[row][col] == 0) {
spiral_m[row][col] = incr++;
col--;
}
// finished - so backtrack once and move up 1
col++; row--;
};
auto up = [&](int &row, int &col, dv &spiral_m, int n, int &incr) {
while (row >= 0 &&
spiral_m[row][col] == 0) {
spiral_m[row][col] = incr++;
row--;
}
// finished - so backtrack once and move right 1
row++; col++;
};
vector<std::function<void(int &, int &, dv &, int, int &)>> functors = {right, down, left, up};
int row = 0, col = 0;
int function_wrapper = 0;
// the number of time to loop in a spiral grows at n+n-1;
// consider the pattern for size n:
//
// n | loop
// 1 | 1
// 2 | 3
// 3 | 5
// 5 | 7
int num_times_to_loop = (2 * n) - 1;
while (num_times_to_loop) {
functors.at(function_wrapper % functors.size())(row, col, spiral_m, n, incr);
function_wrapper++;
num_times_to_loop--;
}
return spiral_m;
}
// some testing
int main(int argc, char **argv)
{
for (int i : {0,1,2,3,4,5,6,7,8,9})
print2d(generateMatrix(i));
}