Problem Overview

You are given an m x n matrix.

Your task is to return all elements of the matrix in spiral order, starting from the top-left corner and moving clockwise.

Spiral order means:

• Move right

• Then move down

• Then move left

• Then move up

• Repeat until all elements are visited

This problem is commonly asked by Google because it tests boundary control, careful iteration, and edge-case handling.

Example 1

Input:

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

Traversal:

1 → 2 → 3 → 6 → 9 → 8 → 7 → 4 → 5

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]

Approach 1: Probability / Try-All Directions

Conceptually:

• From each cell, try to move in all directions

• Track visited cells

• Stop when all elements are collected

Disadvantages:

• Requires an additional visited matrix

• Complicated direction management

• Unnecessarily complex for this problem

This approach works but is inefficient and hard to maintain.

Approach 2: Greedy Direction Switching

Greedy idea:

• Keep moving in the current direction

• Change direction when you hit a boundary or visited cell

Why it is not ideal:

• Requires marking visited cells

• Extra space usage

• Direction logic becomes error-prone

This is not the cleanest solution.

Best Approach: Boundary Shrinking Simulation

Core Idea

Instead of tracking visited cells, shrink the matrix boundaries after completing each direction.

Maintain four boundaries:

• top → top row not yet visited

• bottom → bottom row not yet visited

• left → left column not yet visited

• right → right column not yet visited

At each step, traverse one boundary and then move it inward.

Step-by-Step Traversal

1. Traverse from left to right on the top row
   Then increment top

2. Traverse from top to bottom on the right column
   Then decrement right

3. Traverse from right to left on the bottom row
   Then decrement bottom
   Only if top <= bottom

4. Traverse from bottom to top on the left column
   Then increment left
   Only if left <= right

Repeat until all boundaries cross.

Why This Works

• Every element is visited exactly once

• No extra space for visited tracking

• Clean and predictable traversal order

This is the solution interviewers expect.

Time and Space Complexity

• Time: O(m × n)

• Space: O(1) extra space (excluding output array)

Final Code (Boundary Simulation)

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;

        int m = matrix.size();
        int n = matrix[0].size();

        int top = 0, bottom = m - 1;
        int left = 0, right = n - 1;

        while (top <= bottom && left <= right) {

            for (int col = left; col <= right; col++)
                result.push_back(matrix[top][col]);
            top++;

            for (int row = top; row <= bottom; row++)
                result.push_back(matrix[row][right]);
            right--;

            if (top <= bottom) {
                for (int col = right; col >= left; col--)
                    result.push_back(matrix[bottom][col]);
                bottom--;
            }

            if (left <= right) {
                for (int row = bottom; row >= top; row--)
                    result.push_back(matrix[row][left]);
                left++;
            }
        }

        return result;
    }
};