Spiral Matrix

How it works

We want to read the matrix in spiral order: right → down → left → up, repeating.

Instead of keeping four boundaries (top, bottom, left, right), this approach tracks:

• the current direction (right, down, left, up)
• how many steps we can take in the current direction before turning

Key idea:

• Spiral traversal alternates between moving along a row length and a column length
  • first we move right cols steps
  • then down rows - 1 steps
  • then left cols - 1 steps
  • then up rows - 2 steps
  • and so on...
• After completing a direction, the available steps in that “dimension” shrink by 1.

We store the remaining step counts in an array:

• steps[0] = how many moves left in the horizontal direction
• steps[1] = how many moves left in the vertical direction

d & 1 tells us whether the current direction is horizontal (0) or vertical (1).

Steps

1. Create a list of direction vectors in clockwise order:
   • right (0, 1), down (1, 0), left (0, -1), up (-1, 0)
2. Initialize step counts:
   • steps[0] = number of columns
   • steps[1] = number of rows - 1
3. Start just outside the matrix at (r, c) = (0, -1) so the first move goes into (0, 0).
4. Set direction index d = 0 (start moving right).
5. While the current step count steps[d & 1] is greater than 0:
   • Move steps[d & 1] times in direction d:
     • update (r, c) by the direction vector
     • append matrix[r][c] to the result
   • After finishing those moves, shrink the step count for that dimension:
     • steps[d & 1] -= 1
   • Turn to the next direction:
     • d = (d + 1) % 4
6. Return the result list.

Complexity

• Time complexity: O(m * n)
• Space complexity:
  • O(1) extra space.
  • O(m * n) space for the output list.

Where m is the number of rows and n is the number of columns.

Things to watch for

Not Checking Boundaries After Each Direction

After completing a horizontal traversal, the vertical bounds may have crossed (or vice versa). Failing to check left < right && top < bottom before the third and fourth directions causes duplicate elements to be added when the matrix reduces to a single row or column.

Mishandling Non-Square Matrices

Rectangular matrices with significantly different row and column counts can cause issues if the algorithm assumes square behavior. The spiral may terminate early or add extra elements if boundary checks do not account for both dimensions independently.

Incorrect Direction Rotation

When using direction vectors, rotating incorrectly (e.g., counterclockwise instead of clockwise, or incorrect sign changes) produces a non-spiral traversal pattern. The correct clockwise rotation transforms (dr, dc) to (dc, -dr).

from typing import List

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        steps = [len(matrix[0]), len(matrix) - 1]

        r, c, d = 0, -1, 0
        while steps[d & 1]:
            for i in range(steps[d & 1]):
                r += directions[d][0]
                c += directions[d][1]
                res.append(matrix[r][c])
            steps[d & 1] -= 1
            d += 1
            d %= 4
        return res

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        vector<pair<int, int>> directions = {{0, 1}, {1, 0},
                                             {0, -1}, {-1, 0}};
        vector<int> steps = {static_cast<int>(matrix[0].size()), static_cast<int>(matrix.size()) - 1};

        int r = 0, c = -1, d = 0;
        while (steps[d % 2]) {
            for (int i = 0; i < steps[d % 2]; i++) {
                r += directions[d].first;
                c += directions[d].second;
                res.push_back(matrix[r][c]);
            }
            steps[d % 2]--;
            d = (d + 1) % 4;
        }
        return res;
    }
};