Spiral matrix

You're twenty minutes into a Microsoft interview when the interviewer slides a grid of numbers across the table. "Walk me through how you'd read these values in a spiral," they say, tracing a clockwise path with their finger from the top-left corner inward. This is the spiral matrix problem, also known as "Spiral Matrix" on other platforms, and it's a staple at companies like Microsoft and Amazon. It tests your ability to simulate movement through a 2D grid while keeping track of boundaries and direction changes.

TL;DR

Traverse an m x n matrix in clockwise spiral order using direction arrays and a visited matrix. Start at the top-left cell moving right. At each step, add the current cell to the result, mark it as visited, and check if the next cell in the current direction is valid. If not, rotate clockwise. Four direction vectors (right, down, left, up) encoded as row/column increments handle all movement. This runs in O(m * n) time and space.

Why This Problem Matters

Spiral traversal appears regularly in technical interviews because it combines several skills into one problem: matrix indexing, simulation, direction management, and boundary checking. It's the kind of problem where getting the logic 90% right still produces wrong output, so it rewards precision and careful thinking. Once you internalize the direction array pattern, you'll find it useful for any grid traversal problem that involves changing direction.

Understanding the Problem

Given an m x n matrix of integers, return all elements visited in clockwise spiral order starting from the top-left corner.

Here's a 3x3 matrix to visualize the grid:

The spiral traversal visits cells in this order: [1, 2, 3, 6, 9, 8, 7, 4, 5]. Starting from the top-left, we move right along the first row, down the last column, left along the bottom row, up the first column, and finally reach the center.

Prefer a different language? Jump to solutions in other languages.

Edge Cases to Consider

1. Single row ([[1,2,3]]): Just traverse left to right
2. Single column ([[1],[3]]): Just traverse top to bottom
3. 2x2 matrix: One complete spiral with no inner cells
4. Rectangular matrices: The algorithm must handle m != n gracefully

Solution Approach

The core idea is to simulate walking through the matrix. At any point, you're facing one of four directions: right, down, left, or up. You keep moving in the current direction until you either hit the matrix boundary or land on a cell you've already visited. When that happens, you turn clockwise and continue.

Direction Arrays

Instead of writing separate loops for each direction, we encode all four directions as row and column increments in two arrays:

• Right: row stays the same, column increases (0, 1)
• Down: row increases, column stays the same (1, 0)
• Left: row stays the same, column decreases (0, -1)
• Up: row decreases, column stays the same (-1, 0)

A single direction variable (0 through 3) indexes into these arrays. When we need to turn, direction = (direction + 1) % 4 rotates us clockwise. The modulo wraps index 3 back to 0, so we cycle through right, down, left, up indefinitely.

The Seen Matrix

We allocate a boolean matrix of the same dimensions to track which cells have been visited. Before moving to the next cell, we check two things: is the next cell within bounds, and has it already been visited? If either check fails, we turn clockwise.

This is slightly different from the boundary-pointer approach where you shrink four boundary variables inward. The direction array approach treats the problem uniformly, and the seen matrix handles all the bookkeeping.

Building the Algorithm

Let's trace through a 2x2 matrix to see the algorithm in action:

Step 1: At (0,0), value 1. Direction is right. Next cell (0,1) is valid and unvisited. Move right.

Step 2: At (0,1), value 2. Direction is right. Next cell (0,2) is out of bounds. Turn clockwise to down. Move to (1,1).

Step 3: At (1,1), value 4. Direction is down. Next cell (2,1) is out of bounds. Turn clockwise to left. Move to (1,0).

Step 4: At (1,0), value 3. All cells visited. Done.

Result: [1, 2, 4, 3]

Non-Square Matrices

The same logic handles rectangular matrices without any special cases. Here's a 2x3 example where dumpSpiral([[1,2,3],[4,5,6]]) returns [1, 2, 3, 6, 5, 4]:

The direction changes happen naturally: right across the top, down one cell, then left across the bottom. The seen matrix prevents us from revisiting cells as we spiral inward.

Implementation

Here's the Java solution:

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

public class Solution {
  public List<Integer> dumpSpiral(int[][] matrix) {
    List<Integer> out = new ArrayList<>();
    int rows = matrix.length, cols = matrix[0].length;
    boolean[][] seen = new boolean[rows][cols];

    // Direction arrays: right, down, left, up
    int[] rowIncrements = {0, 1, 0, -1};
    int[] colIncrements = {1, 0, -1, 0};

    int r = 0, c = 0, direction = 0;

    for (int i = 0; i < rows * cols; i++) {
      out.add(matrix[r][c]);
      seen[r][c] = true;

      // Check if the next cell in the current direction is valid
      int maybeNextR = r + rowIncrements[direction];
      int maybeNextC = c + colIncrements[direction];

      if (maybeNextR >= 0 && maybeNextR < rows && maybeNextC >= 0 &&
            maybeNextC < cols && !seen[maybeNextR][maybeNextC]) {
        // Continue in the current direction
        r = maybeNextR;
        c = maybeNextC;
      } else {
        // Turn clockwise and move
        direction = (direction + 1) % 4;
        r += rowIncrements[direction];
        c += colIncrements[direction];
      }
    }

    return out;
  }
}

The loop runs exactly rows * cols times, once per cell. At each iteration, we add the current value, mark it visited, peek at the next cell in our current direction, and either continue or turn. The else branch handles the turn: update the direction index, then apply the new direction's increments to move.

Pro tip: The key insight is that the for loop count is fixed at rows * cols. We know exactly how many cells to visit, so there's no need for a while loop with complex termination conditions.

Complexity Analysis

Time Complexity: O(m * n)

Every cell is visited exactly once inside the loop. The direction check and bounds validation are O(1) operations per iteration. For an m x n matrix, we perform m * n iterations total.

Space Complexity: O(m * n)

Two sources contribute to this:

• The output list stores all m * n values
• The seen matrix is an m x n boolean grid

The direction arrays (size 4 each) and the index variables use O(1) additional space. If we only count auxiliary space beyond the output, it's still O(m * n) for the seen matrix.

Common Pitfalls

1. Forgetting to turn before moving: When the next cell is invalid, you must update the direction before computing the next position. Turning and then moving in the old direction produces incorrect results.

2. Off-by-one on bounds checks: The condition must check maybeNextR >= 0 && maybeNextR < rows (strict less-than), not <=. Using <= will index out of bounds.

3. Not checking the seen matrix: Without the visited check, the traversal will overwrite or revisit cells on inner layers. This is especially problematic for larger matrices where the spiral makes multiple passes.

4. Assuming square matrices: Hard-coding n for both dimensions will break on rectangular inputs. Always use separate rows and cols variables.

Interview Tips

When solving this in an interview:

1. Start with a small example: Draw a 3x3 grid and trace the spiral by hand. This helps you and the interviewer agree on the expected output before writing code.

2. Explain the direction array technique: Interviewers are often impressed when candidates use direction arrays instead of four separate traversal loops. It shows familiarity with simulation patterns.

3. Mention the alternative: Briefly note that a boundary-pointer approach also works. This demonstrates awareness of multiple solutions and lets the interviewer steer toward their preferred approach.

4. Watch for follow-ups: Common follow-ups include "spiral matrix II" (fill a matrix in spiral order) and "spiral traversal in counter-clockwise order." Both use the same direction array pattern with minor tweaks.

Key Takeaways

• Direction arrays (rowIncrements and colIncrements) encode all four movement directions in clockwise order, replacing four separate traversal loops with a single unified loop.
• The direction = (direction + 1) % 4 rotation is the heart of the algorithm. It handles every direction change, including wrapping from up back to right.
• A boolean seen matrix tracks visited cells, which is essential for knowing when to turn on inner layers of the spiral.
• The fixed loop count of rows * cols eliminates the need for complex termination logic. Every cell gets visited exactly once.
• This pattern generalizes well to other grid simulation problems like snake games, robot movement, or any traversal that involves direction changes.

Related Problems and Practice

Once you're comfortable with spiral traversal, try these related problems:

• Image matrix 90-degree twist (matrix rotation uses similar index manipulation)
• Zero out rows and columns (another matrix traversal pattern)
• Number of islands (grid traversal with direction arrays)

Solutions in Other Languages

Python

from typing import List


class Solution:
    def dump_spiral(self, matrix: List[List[int]]) -> List[int]:
        out = []
        rows, cols = len(matrix), len(matrix[0])
        seen = [[False for _ in range(cols)] for _ in range(rows)]
        row_increments = [0, 1, 0, -1]
        col_increments = [1, 0, -1, 0]
        r, c, direction = 0, 0, 0

        for i in range(rows * cols):
            out.append(matrix[r][c])
            seen[r][c] = True
            maybe_next_r = r + row_increments[direction]
            maybe_next_c = c + col_increments[direction]
            if 0 <= maybe_next_r < rows and 0 <= maybe_next_c < cols \
                    and not seen[maybe_next_r][maybe_next_c]:
                r, c = maybe_next_r, maybe_next_c
            else:
                direction = (direction + 1) % 4
                r += row_increments[direction]
                c += col_increments[direction]
        return out

JavaScript

class Solution {
  dumpSpiral(matrix) {
    const out = [];
    const rows = matrix.length, cols = matrix[0].length;
    const seen = [...Array(rows)].map(_ => Array(cols));
    const rowIncrements = [0, 1, 0, -1];
    const colIncrements = [1, 0, -1, 0];
    let r = 0, c = 0, direction = 0;

    for (let i = 0; i < rows * cols; i++) {
      out.push(matrix[r][c]);
      seen[r][c] = true;
      const maybeNextR = r + rowIncrements[direction];
      const maybeNextC = c + colIncrements[direction];
      if (maybeNextR >= 0 && maybeNextR < rows && maybeNextC >= 0 &&
        maybeNextC < cols && !seen[maybeNextR][maybeNextC]) {
        r = maybeNextR;
        c = maybeNextC;
      } else {
        direction = (direction + 1) % 4;
        r += rowIncrements[direction];
        c += colIncrements[direction];
      }
    }
    return out;
  }
}

TypeScript

class Solution {
  dumpSpiral(matrix: number[][]): number[] {
    const out: number[] = [];
    const rows = matrix.length, cols = matrix[0].length;
    const seen: boolean[][] = [...Array(rows)].map(_ => Array(cols));
    const rowIncrements = [0, 1, 0, -1];
    const colIncrements = [1, 0, -1, 0];
    let r = 0, c = 0, direction = 0;

    for (let i = 0; i < rows * cols; i++) {
      out.push(matrix[r][c]);
      seen[r][c] = true;
      const maybeNextR = r + rowIncrements[direction];
      const maybeNextC = c + colIncrements[direction];
      if (maybeNextR >= 0 && maybeNextR < rows && maybeNextC >= 0 &&
        maybeNextC < cols && !seen[maybeNextR][maybeNextC]) {
        r = maybeNextR;
        c = maybeNextC;
      } else {
        direction = (direction + 1) % 4;
        r += rowIncrements[direction];
        c += colIncrements[direction];
      }
    }
    return out;
  }
}

C++

#include <vector>

class Solution {
public:
  std::vector<int> dumpSpiral(std::vector<std::vector<int>> &matrix) {
    std::vector<int> out;
    int rows = matrix.size(), cols = matrix[0].size();
    std::vector<std::vector<bool>> seen(rows, std::vector<bool>(cols, false));
    std::vector<int> rowIncrements = {0, 1, 0, -1};
    std::vector<int> colIncrements = {1, 0, -1, 0};
    int r = 0, c = 0, direction = 0;

    for (int i = 0; i < rows * cols; i++) {
      out.push_back(matrix[r][c]);
      seen[r][c] = true;
      int maybeNextR = r + rowIncrements[direction],
          maybeNextC = c + colIncrements[direction];
      if (maybeNextR >= 0 && maybeNextR < rows &&
          maybeNextC >= 0 && maybeNextC < cols &&
          !seen[maybeNextR][maybeNextC]) {
        r = maybeNextR;
        c = maybeNextC;
      } else {
        direction = (direction + 1) % 4;
        r += rowIncrements[direction];
        c += colIncrements[direction];
      }
    }
    return out;
  }
};

Scala

import scala.collection.mutable

class Solution {
  def dumpSpiral(matrix: Array[Array[Int]]): List[Int] = {
    val out = mutable.ArrayBuffer[Int]()
    val rows = matrix.length
    val cols = matrix(0).length
    val seen = Array.ofDim[Boolean](rows, cols)
    val rowIncrements = Array(0, 1, 0, -1)
    val colIncrements = Array(1, 0, -1, 0)
    var r = 0
    var c = 0
    var direction = 0

    for (_ <- 0 until rows * cols) {
      out.append(matrix(r)(c))
      seen(r)(c) = true
      val maybeNextR = r + rowIncrements(direction)
      val maybeNextC = c + colIncrements(direction)
      if (maybeNextR >= 0 && maybeNextR < rows && maybeNextC >= 0 &&
        maybeNextC < cols && !seen(maybeNextR)(maybeNextC)) {
        r = maybeNextR
        c = maybeNextC
      } else {
        direction = (direction + 1) % 4
        r += rowIncrements(direction)
        c += colIncrements(direction)
      }
    }
    out.toList
  }
}

Kotlin

class Solution {
  fun dumpSpiral(matrix: Array<IntArray>): List<Int> {
    val out = mutableListOf<Int>()
    val rows = matrix.size
    val cols = matrix[0].size
    val seen = Array(rows) { BooleanArray(cols) }
    val rowIncrements = intArrayOf(0, 1, 0, -1)
    val colIncrements = intArrayOf(1, 0, -1, 0)
    var r = 0
    var c = 0
    var direction = 0

    for (i in 0 until rows * cols) {
      out.add(matrix[r][c])
      seen[r][c] = true
      val maybeNextR = r + rowIncrements[direction]
      val maybeNextC = c + colIncrements[direction]
      if (maybeNextR >= 0 && maybeNextR < rows && maybeNextC >= 0 &&
            maybeNextC < cols && !seen[maybeNextR][maybeNextC]) {
        r = maybeNextR
        c = maybeNextC
      } else {
        direction = (direction + 1) % 4
        r += rowIncrements[direction]
        c += colIncrements[direction]
      }
    }
    return out
  }
}

Swift

import Foundation

class Solution {
    func dumpSpiral(_ matrix: [[Int]]) -> [Int] {
        var out: [Int] = []
        let rows = matrix.count
        let cols = matrix[0].count
        var seen = Array(repeating: Array(repeating: false, count: cols), count: rows)
        let rowIncrements = [0, 1, 0, -1]
        let colIncrements = [1, 0, -1, 0]
        var r = 0
        var c = 0
        var direction = 0

        for _ in 0..<(rows * cols) {
            out.append(matrix[r][c])
            seen[r][c] = true
            let maybeNextR = r + rowIncrements[direction]
            let maybeNextC = c + colIncrements[direction]
            if maybeNextR >= 0 && maybeNextR < rows && maybeNextC >= 0 &&
                  maybeNextC < cols && !seen[maybeNextR][maybeNextC] {
                r = maybeNextR
                c = maybeNextC
            } else {
                direction = (direction + 1) % 4
                r += rowIncrements[direction]
                c += colIncrements[direction]
            }
        }
        return out
    }
}

Dart

class Solution {
  List<int> dumpSpiral(List<List<int>> matrix) {
    List<int> out = [];
    int rows = matrix.length;
    int cols = matrix[0].length;
    List<List<bool>> seen = List.generate(rows, (_) => List.filled(cols, false));
    List<int> rowIncrements = [0, 1, 0, -1];
    List<int> colIncrements = [1, 0, -1, 0];
    int r = 0, c = 0, direction = 0;

    for (int i = 0; i < rows * cols; i++) {
      out.add(matrix[r][c]);
      seen[r][c] = true;
      int maybeNextR = r + rowIncrements[direction];
      int maybeNextC = c + colIncrements[direction];
      if (maybeNextR >= 0 && maybeNextR < rows && maybeNextC >= 0 &&
            maybeNextC < cols && !seen[maybeNextR][maybeNextC]) {
        r = maybeNextR;
        c = maybeNextC;
      } else {
        direction = (direction + 1) % 4;
        r += rowIncrements[direction];
        c += colIncrements[direction];
      }
    }
    return out;
  }
}

C#

using System.Collections.Generic;

public class Solution {
    public List<int> DumpSpiral(int[][] matrix) {
        var output = new List<int>();
        int rows = matrix.Length, cols = matrix[0].Length;
        var seen = new bool[rows, cols];
        int[] rowIncrements = {0, 1, 0, -1};
        int[] colIncrements = {1, 0, -1, 0};
        int r = 0, c = 0, direction = 0;

        for (int i = 0; i < rows * cols; i++) {
            output.Add(matrix[r][c]);
            seen[r, c] = true;
            int maybeNextR = r + rowIncrements[direction];
            int maybeNextC = c + colIncrements[direction];
            if (maybeNextR >= 0 && maybeNextR < rows && maybeNextC >= 0 &&
                  maybeNextC < cols && !seen[maybeNextR, maybeNextC]) {
                r = maybeNextR;
                c = maybeNextC;
            } else {
                direction = (direction + 1) % 4;
                r += rowIncrements[direction];
                c += colIncrements[direction];
            }
        }
        return output;
    }
}

PHP

<?php

class Solution {
    public function dumpSpiral(array $matrix): array {
        $out = [];
        $rows = count($matrix);
        $cols = count($matrix[0]);
        $seen = array_fill(0, $rows, array_fill(0, $cols, false));
        $rowIncrements = [0, 1, 0, -1];
        $colIncrements = [1, 0, -1, 0];
        $r = 0;
        $c = 0;
        $direction = 0;

        for ($i = 0; $i < $rows * $cols; $i++) {
            $out[] = $matrix[$r][$c];
            $seen[$r][$c] = true;
            $maybeNextR = $r + $rowIncrements[$direction];
            $maybeNextC = $c + $colIncrements[$direction];
            if ($maybeNextR >= 0 && $maybeNextR < $rows && $maybeNextC >= 0 &&
                $maybeNextC < $cols && !$seen[$maybeNextR][$maybeNextC]) {
                $r = $maybeNextR;
                $c = $maybeNextC;
            } else {
                $direction = ($direction + 1) % 4;
                $r += $rowIncrements[$direction];
                $c += $colIncrements[$direction];
            }
        }
        return $out;
    }
}

Ruby

class Solution
  def dump_spiral(matrix)
    out = []
    rows = matrix.length
    cols = matrix[0].length
    seen = Array.new(rows) { Array.new(cols, false) }
    row_increments = [0, 1, 0, -1]
    col_increments = [1, 0, -1, 0]
    r = 0
    c = 0
    direction = 0

    (rows * cols).times do
      out << matrix[r][c]
      seen[r][c] = true
      maybe_next_r = r + row_increments[direction]
      maybe_next_c = c + col_increments[direction]
      if maybe_next_r >= 0 && maybe_next_r < rows && maybe_next_c >= 0 &&
           maybe_next_c < cols && !seen[maybe_next_r][maybe_next_c]
        r = maybe_next_r
        c = maybe_next_c
      else
        direction = (direction + 1) % 4
        r += row_increments[direction]
        c += col_increments[direction]
      end
    end
    out
  end
end

Rust

pub struct Solution;

impl Solution {
    pub fn dump_spiral(&self, matrix: Vec<Vec<i32>>) -> Vec<i32> {
        let mut out: Vec<i32> = Vec::new();
        let rows = matrix.len();
        let cols = matrix[0].len();
        let mut seen = vec![vec![false; cols]; rows];
        let row_increments: [i32; 4] = [0, 1, 0, -1];
        let col_increments: [i32; 4] = [1, 0, -1, 0];
        let (mut r, mut c, mut direction) = (0i32, 0i32, 0usize);

        for _ in 0..rows * cols {
            out.push(matrix[r as usize][c as usize]);
            seen[r as usize][c as usize] = true;
            let maybe_next_r = r + row_increments[direction];
            let maybe_next_c = c + col_increments[direction];
            if maybe_next_r >= 0
                && (maybe_next_r as usize) < rows
                && maybe_next_c >= 0
                && (maybe_next_c as usize) < cols
                && !seen[maybe_next_r as usize][maybe_next_c as usize]
            {
                r = maybe_next_r;
                c = maybe_next_c;
            } else {
                direction = (direction + 1) % 4;
                r += row_increments[direction];
                c += col_increments[direction];
            }
        }
        out
    }
}

Practice on Firecode

Spiral matrix is the kind of problem that clicks once you've traced through it a few times. The direction array pattern shows up in many other grid problems, so time spent here pays dividends across your interview prep. This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. Build the muscle memory now, and you'll walk into your next interview with confidence.