Spiral Matrix

medium matrix simulation

Problem

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

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

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

Outer ring 1→2→3→6→9→8→7→4, then the inner cell 5.

matrix (rows separated by ';', values by ',')

def spiral_order(matrix):
    out = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):
            out.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1):
            out.append(matrix[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1):
                out.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1):
                out.append(matrix[r][left])
            left += 1
    return out

function spiralOrder(matrix) {
  const out = [];
  let top = 0, bottom = matrix.length - 1;
  let left = 0, right = matrix[0].length - 1;
  while (top <= bottom && left <= right) {
    for (let c = left; c <= right; c++) out.push(matrix[top][c]);
    top++;
    for (let r = top; r <= bottom; r++) out.push(matrix[r][right]);
    right--;
    if (top <= bottom) {
      for (let c = right; c >= left; c--) out.push(matrix[bottom][c]);
      bottom--;
    }
    if (left <= right) {
      for (let r = bottom; r >= top; r--) out.push(matrix[r][left]);
      left++;
    }
  }
  return out;
}

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> out = new ArrayList<>();
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int c = left; c <= right; c++) out.add(matrix[top][c]);
            top++;
            for (int r = top; r <= bottom; r++) out.add(matrix[r][right]);
            right--;
            if (top <= bottom) {
                for (int c = right; c >= left; c--) out.add(matrix[bottom][c]);
                bottom--;
            }
            if (left <= right) {
                for (int r = bottom; r >= top; r--) out.add(matrix[r][left]);
                left++;
            }
        }
        return out;
    }
}

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> out;
    int top = 0, bottom = (int)matrix.size() - 1;
    int left = 0, right = (int)matrix[0].size() - 1;
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; ++c) out.push_back(matrix[top][c]);
        ++top;
        for (int r = top; r <= bottom; ++r) out.push_back(matrix[r][right]);
        --right;
        if (top <= bottom) {
            for (int c = right; c >= left; --c) out.push_back(matrix[bottom][c]);
            --bottom;
        }
        if (left <= right) {
            for (int r = bottom; r >= top; --r) out.push_back(matrix[r][left]);
            ++left;
        }
    }
    return out;
}

Explanation

We read a matrix in a clockwise spiral: across the top, down the right, back across the bottom, up the left, then spiral inward. The clean way to track where we are is with four shrinking boundaries.

We keep top, bottom, left, and right for the edges of the unread region. While top <= bottom and left <= right, we peel off one ring.

Each ring has four passes: collect the top row then push top down, collect the right column then pull right in, collect the bottom row then pull bottom up, collect the left column then push left in. The two if checks before the bottom and left passes prevent re-reading a row or column in non-square or thin matrices.

Shrinking the boundaries after each side is what keeps us moving inward without revisiting any cell.

Example: [[1,2,3],[4,5,6],[7,8,9]]. The outer ring reads 1,2,3,6,9,8,7,4, then only the center 5 remains, giving [1,2,3,6,9,8,7,4,5].

Time: O(m · n) Space: O(1) extra