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));
}