Link to Question

MEDIUM

Spiral Matrix

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

Example

Input:

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

Output:

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

Explanation:
The matrix is traversed in spiral order.

---

Constraints

• 1 ≤ m, n ≤ 10
• -100 ≤ matrix[i][j] ≤ 100

---

Solution: Simulation

• Time Complexity: O(m * n)
• Space Complexity: O(1) (excluding the output)

C++

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int top = 0, bottom = m - 1, left = 0, right = n - 1;
        vector<int> res;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; ++j) res.push_back(matrix[top][j]);
            ++top;
            for (int i = top; i <= bottom; ++i) res.push_back(matrix[i][right]);
            --right;
            if (top <= bottom) {
                for (int j = right; j >= left; --j) res.push_back(matrix[bottom][j]);
                --bottom;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; --i) res.push_back(matrix[i][left]);
                ++left;
            }
        }
        return res;
    }
};