Spiral Matrix

Spiral Matrix tests whether you can keep careful track of where you are. The idea is simple. You read the grid in a spiral, like peeling an onion. But the hard part is the bookkeeping. If your boundaries are off by one, you read a cell twice or you skip one. The interviewer wants to see clean, exact control of those edges.

🎯 The Problem

You get a matrix and you must read it in a spiral. Here are the rules.

• A matrix is a grid of numbers with rows and columns.
• Read every number in spiral order.
• Go right across the top, then down the right side.
• Then left across the bottom, then up the left side.
• Move inward and repeat. Return the numbers in that order as a list.

Look at this small grid. You start at the top left and spiral inward to the center.

Input:
1 2 3
4 5 6
7 8 9

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

Explanation: top row, right column, bottom row, left column, then the center.

Here is the path drawn out. Each step points to the next cell we visit.

🐢 Approach 1: Walk With a Visited Grid (Brute Force)

The idea in one line: walk cell by cell, mark where you have been, and turn right whenever you cannot go straight.

The idea:

• Keep a second grid of true and false.
• Walk in one direction. Mark each cell as visited.
• When the next step goes off the edge or hits a visited cell, turn right.
• Stop when every cell is visited.

Why it is weak:

• It needs an extra grid as big as the input.
• The space is O(m × n).
• The turning logic is fiddly and easy to get wrong.

Here is the visited-grid code:

def spiral_order(matrix):
    rows, cols = len(matrix), len(matrix[0])
    seen = [[False] * cols for _ in range(rows)]
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    r = c = direction = 0
    answer = []

    for _ in range(rows * cols):
        answer.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + dirs[direction][0], c + dirs[direction][1]
        if nr < 0 or nc < 0 or nr == rows or nc == cols or seen[nr][nc]:
            direction = (direction + 1) % 4
            nr, nc = r + dirs[direction][0], c + dirs[direction][1]
        r, c = nr, nc

    return answer

⚡ Approach 2: Four Shrinking Boundaries (Best)

The idea in one line: track four edge numbers and pull them inward one lap at a time, no extra grid.

The idea:

• Keep four numbers called boundaries: top, bottom, left, right.
• They mark the edges of the part you still need to read.
• At the start they box in the whole matrix.

How one lap works:

• Read the top row from left to right. Then move top down by one.
• Read the right column from top to bottom. Then move right left by one.
• Read the bottom row from right back to left. Then move bottom up by one.
• Read the left column from bottom up to top. Then move left right by one.

How it finishes:

• After each lap the box shrinks.
• Keep going while top is not past bottom and left is not past right.
• Guard the bottom row and left column reads. That stops a lone middle row or column from being read twice.

Why it is fast:

• It uses only four numbers, not a whole grid.
• Each cell is read exactly once.
• The extra space is O(1).

Steps to Solve

1. Set top = 0, bottom = lastRow, left = 0, right = lastCol.
2. While top <= bottom and left <= right, do the four moves below.
3. Read the top row from left to right. Then do top = top + 1.
4. Read the right column from top to bottom. Then do right = right - 1.
5. If top <= bottom, read the bottom row from right to left. Then do bottom = bottom - 1.
6. If left <= right, read the left column from bottom to top. Then do left = left + 1.

Here is how the boundaries shrink after the outer lap is done.

#include <stdio.h>

#define R 3
#define C 3

void spiralOrder(int matrix[R][C]) {
    int top = 0, bottom = R - 1, left = 0, right = C - 1;
    int first = 1;
    printf("[");
    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; j++) {        // top row
            if (!first) printf(", ");
            printf("%d", matrix[top][j]); first = 0;
        }
        top++;
        for (int i = top; i <= bottom; i++) {        // right col
            if (!first) printf(", ");
            printf("%d", matrix[i][right]); first = 0;
        }
        right--;
        if (top <= bottom) {
            for (int j = right; j >= left; j--) {    // bottom row
                if (!first) printf(", ");
                printf("%d", matrix[bottom][j]); first = 0;
            }
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {    // left col
                if (!first) printf(", ");
                printf("%d", matrix[i][left]); first = 0;
            }
            left++;
        }
    }
    printf("]\n");
}

int main(void) {
    int matrix[R][C] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    spiralOrder(matrix);
    return 0;
}

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

#include <iostream>
#include <vector>
using namespace std;

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;
}

int main() {
    vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    vector<int> result = spiralOrder(matrix);
    cout << "[";
    for (size_t i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i + 1 < result.size()) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

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

import java.util.ArrayList;
import java.util.List;

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

    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        System.out.println(spiralOrder(matrix));
    }
}

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

def spiral_order(matrix):
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for j in range(left, right + 1):      # top row left to right
            result.append(matrix[top][j])
        top += 1
        for i in range(top, bottom + 1):      # right col top to bottom
            result.append(matrix[i][right])
        right -= 1
        if top <= bottom:                     # bottom row right to left
            for j in range(right, left - 1, -1):
                result.append(matrix[bottom][j])
            bottom -= 1
        if left <= right:                     # left col bottom to top
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1
    return result


matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(spiral_order(matrix))

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

function spiralOrder(matrix) {
  const result = [];
  let top = 0;
  let bottom = matrix.length - 1;
  let left = 0;
  let right = matrix[0].length - 1;
  while (top <= bottom && left <= right) {
    for (let j = left; j <= right; j++) result.push(matrix[top][j]); // top row
    top++;
    for (let i = top; i <= bottom; i++) result.push(matrix[i][right]); // right col
    right--;
    if (top <= bottom) {
      for (let j = right; j >= left; j--) result.push(matrix[bottom][j]); // bottom
      bottom--;
    }
    if (left <= right) {
      for (let i = bottom; i >= top; i--) result.push(matrix[i][left]); // left col
      left++;
    }
  }
  return result;
}

const matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
console.log(spiralOrder(matrix));

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

Let us read the Python version line by line, because the boundary updates are the heart of it.

top, bottom = 0, len(matrix) - 1 and left, right = 0, len(matrix[0]) - 1 set the box around the whole matrix. top and left start at the first row and column. bottom and right start at the last row and column.

The while top <= bottom and left <= right loop runs while the box still has cells inside. When the box closes, both checks fail and we stop.

The first inner loop reads the top row. It goes from left to right and appends each cell. Right after, top += 1 shrinks the box from the top. That row is finished, so we never look at it again.

The second loop reads the right column from the new top down to bottom. Then right -= 1 shrinks the box from the right.

Now the guarded part. if top <= bottom checks that a bottom row still exists. Without this check, a single leftover middle row would get read twice. Inside, we read the bottom row from right back to left, then bottom -= 1.

if left <= right checks that a left column still exists. Same protection against double reading. Inside, we read the left column from bottom up to top, then left += 1.

So each lap reads the four edges and pulls all four boundaries inward. The center cell gets read on the final lap, when the box has shrunk to one cell.

⏱️ Time and Space Complexity

Both approaches read each cell exactly once. So the time is O(m × n). The visited-grid version needs a full extra grid, so its space is O(m × n). The boundary version needs only four numbers, so its extra space is O(1). The output list does not count as extra working space, since you must return it.

🧩 Key Takeaways

• ✅ Track four boundaries: top, bottom, left, and right. They box the unread region.
• ✅ Read in four moves each lap: top row, right column, bottom row, left column.
• ✅ Shrink the matching boundary right after each move.
• ✅ Guard the bottom row and left column reads, so a lone middle row or column is not read twice.
• ✅ The boundary method needs only O(1) extra space, far better than a visited grid.

🚀 What’s Next?

• Rotate Image
• Diagonal Traverse