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

Examples

Example 1:

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

Example 2:

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

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

Thinking Process

There are two main approaches to solve this problem:

  1. Boundary Tracking: Use four boundaries (top, bottom, left, right) and traverse in spiral order
  2. Direction Simulation: Use direction vectors and mark visited cells to simulate spiral movement
Grid traversal BFS/DFS flood from each cell

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Row/column traversal O(nm) O(1) Simulation, spiral
BFS/DFS on grid O(nm) O(nm) Islands, shortest path
Matrix as graph (this problem) O(nm) O(nm) 4/8-directional neighbors
Transpose / rotate O(nm) O(1) In-place rotation tricks

Solution

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> rtn;
        const int rows = matrix.size(), cols = matrix[0].size();
        int up = 0, left = 0, right = cols - 1, down = rows - 1;
        
        while(rtn.size() < rows * cols) {
            // Traverse right along top row
            for(int col = left; col <= right; col++) {
                rtn.push_back(matrix[up][col]);
            }
            
            // Traverse down along right column
            for(int row = up + 1; row <= down; row++) {
                rtn.push_back(matrix[row][right]);
            }
            
            // Traverse left along bottom row (if not same as top)
            if(up != down) {
                for (int col = right - 1; col >= left; col--) {
                    rtn.push_back(matrix[down][col]);
                }
            }
            
            // Traverse up along left column (if not same as right)
            if(left != right) {
                for(int row = down - 1; row > up; row--) {
                    rtn.push_back(matrix[row][left]);
                }
            }
            
            // Move boundaries inward
            left++;
            right--;
            up++;
            down--;
        }
        return rtn;
    }
};

Solution Explanation

Approach: Matrix as graph (this problem)

Key idea: There are two main approaches to solve this problem:

How the code works:

  1. Boundary Tracking: Use four boundaries (top, bottom, left, right) and traverse in spiral order
  2. Direction Simulation: Use direction vectors and mark visited cells to simulate spiral movement

Walkthrough — input matrix = [[1,2,3],[4,5,6],[7,8,9]], expected output [1,2,3,6,9,8,7,4,5]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Common Mistakes

  4. Off-by-one errors in boundary conditions
  5. Not handling single row/column cases properly
  6. Incorrect boundary updates after each spiral
  7. Missing edge cases for 1x1 matrices

References

Key Takeaways

  1. Boundary Management: Track four boundaries and move them inward after each complete spiral
  2. Edge Cases: Handle single row/column matrices with conditional checks
  3. Direction Changes: Use direction vectors to simulate spiral movement
  4. Visited Marking: Mark cells as visited to avoid revisiting them