Spiral Matrix

Problem

Given an m x n matrix of integers matrix, return a list of all elements within the matrix in spiral order.

Examples

Example 1:

Input: matrix = [[1,2],[3,4]]

Output: [1,2,4,3]

Example 2:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

Output: [1,2,3,6,9,8,7,4,5]

Example 3:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints

• 1 <= matrix.length, matrix[i].length <= 10
• -100 <= matrix[i][j] <= 100

You should aim for a solution with O(m*n) time and O(1) extra space, where m is the number of rows and n is the number of columns in the given matrix.

Solution

Use an outer loop over how many layers we have to do, then an inner 4 loops over top row, right col (minus top row element), bottom row (minus far right col element), then left col (minus bottom and top element). For an odd number of rows/cols, then the top and right sweeps will cover everything, and doing a bottom/left will duplicate. So we check in the middle.

class Solution {
    constexpr auto ceil_div(int num, int denom) {
        return (num + denom - 1) / denom;
    }
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        const int M = matrix.size();
        const int N = matrix[0].size();
        const int L = std::min(ceil_div(M, 2), ceil_div(N, 2));
 
        std::vector<int> result;
        for (int l = 0; l < L; ++l) {
            int top = l;
            int bottom = M - l - 1;
            int left = l;
            int right = N - l - 1;
 
            // Walk along the top row
            for (int c = left; c <= right; ++c) {
                result.push_back(matrix[top][c]);
            }
 
            // Walk along the right column
            for (int r = top + 1; r <= bottom; ++r) {
                result.push_back(matrix[r][right]);
            }
 
            // If there is no separate bottom row or no separate left column,
            // then bottom/left would duplicate cells we already visited.
            if (!(top < bottom && left < right)) {
                break;
            }
 
            // Walk along the bottom row
            for (int c = right - 1; c >= left; --c) {
                result.push_back(matrix[bottom][c]);
            }
 
            // Walk along the left column
            for (int r = bottom - 1; r >= top + 1; --r) {
                result.push_back(matrix[r][left]);
            }
        }
        return result;
    }
};