54 Spiral Matrix

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

Testing

int main() {
    vector<vector<int>> matrix1 = {
        { 1,2,3 },
        { 8,9,4 },
        { 7,6,5 },
    };
    vector<vector<int>> matrix2 = {
        { 1,  2,  3,  4,  5,  6 },
        { 14, 15, 16, 17, 18, 7 },
        { 13, 12, 11, 10, 9,  8 },
    };
    vector<vector<int>> matrix3 = {
        { 3,  },
        { 2 },
    };
    vector<vector<int>> matrix4 = {
        { 2,5 },
        { 8,4 },
        { 0, -1}
    };

    //print(spiralOrder(matrix1));
    //print(spiralOrder(matrix2));
    print(spiralOrder(matrix3));
    print(spiralOrder(matrix4));
}