</>Ali · LeetCode
#0054·MediumArrays

Spiral Matrix

LeetCode #54 · Medium · Arrays · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Layer-by-layer traversal with boundary tracking

Key insight

Traverse the matrix in a spiral by processing one layer at a time, moving from outer to inner layers. Each layer consists of four sides.

Strategy

  1. 1Maintain four boundaries: top, bottom, left, right
  2. 2For each layer, traverse in order:
  3. 3After each side, shrink the corresponding boundary
  4. 4Continue until boundaries cross
Time
O(m * n)
visit each element once
Space
O(1)
excluding the result vector
Problem description(from LeetCode)

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]

Constraints

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

C++ Solution

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

    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;

    while (top <= bottom && left <= right) {
      for (int j = left; j <= right; j++) {
        result.push_back(matrix[top][j]);
      }
      top++;

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

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

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

    return result;
  }
};

More Arrays problems