Spiral Matrix

AS
Ackshaey Singh
Difficulty Hard
Time Complexity
O(m * n)
Space Complexity
O(1)
Array Matrix
Microsoft Amazon

You're twenty minutes into a Microsoft interview when the interviewer slides a grid of numbers across the table. "Read these values back to me in a spiral," they say, tracing a clockwise path with their finger from the top-left corner inward. This is the Spiral Matrix problem, a staple at companies like Microsoft and Amazon. It tests whether you can move through a 2D grid while keeping exact track of which rows and columns are already done.

TL;DR

Keep four bounds: top, bottom, left and right. Read the top row, then move top down. Read the right column, then move right in. Read the bottom row backwards, then move bottom up. Read the left column upwards, then move left in. After each edge, stop as soon as a bound passes the one opposite it. This runs in O(m * n) time and O(1) extra space.

Why This Problem Matters

Spiral traversal appears regularly in technical interviews because it combines matrix indexing, simulation and boundary checks in one short problem. Getting the logic 90% right still produces wrong output, so it rewards precision. The shrinking-bounds idea also comes back in other layer-by-layer matrix problems, such as rotating a square image.

Understanding the Problem

You are given matrix, a grid of integers with m rows and n columns. Return all of its elements in spiral order.

Spiral order starts at the top-left element and goes clockwise around the outside of the grid: right along the top row, down the right column, left along the bottom row and up the left column. It then does the same on the part that is left inside, until every element is read once.

Constraints

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

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

Loading visualization...

The spiral order for this grid is [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.

Loading visualization...

A taller example: dumpSpiral([[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15]]) returns [1, 2, 3, 6, 9, 12, 15, 14, 13, 10, 7, 4, 5, 8, 11]. The outer ring is read clockwise, starting at 1 and ending at 4. Then only the middle column is left, and 5, 8 and 11 are read once, from top to bottom.

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

Edge Cases to Consider

  1. Single row ([[1,3]]): read left to right, then stop
  2. Single column ([[1],[3]]): read the one top element, then down the column, then stop
  3. 2x2 matrix: one complete ring with no inner cells
  4. Rectangular matrices: the last ring is often a single row or column, and it must not be read twice

Solution Approach

Spiral order reads the outer ring clockwise, then the ring inside it, and so on. The question is how to record which rows and columns are already read. Four integers are enough:

  • top: the first row that is not read yet
  • bottom: the last row that is not read yet
  • left: the first column that is not read yet
  • right: the last column that is not read yet

Together they mark out the rectangle that is still unread.

Reading One Ring

Each pass of the loop reads the four edges of the unread rectangle, and each edge removes one row or one column from it:

  1. Read row top from left to right. That row is done, so top moves down by one.
  2. Read column right from top to bottom. That column is done, so right moves left by one.
  3. Read row bottom from right to left. That row is done, so bottom moves up by one.
  4. Read column left from bottom to top. That column is done, so left moves right by one.

Stopping at the Right Moment

After each edge, the unread rectangle may be empty. If top > bottom, no rows are left. If left > right, no columns are left. The loop must stop right there, even in the middle of a ring.

This check is what makes single rows and single columns work. Take [[1,2,3]]. The top row gives 1, 2, 3, and top becomes 1 while bottom is 0. Without a check, the loop would go on and read the bottom row, which is the same row, backwards. The output would then contain 2 and 1 a second time.

Tracing a 2x2 Matrix

Let's trace [[1,2],[3,4]]. The bounds start at top = 0, bottom = 1, left = 0, right = 1.

Loading visualization...

Step 1: Read row 0 from column 0 to 1: 1, 2. Set top = 1. Rows 1 to 1 are left, so continue.

Step 2: Read column 1 from row 1 to 1: 4. Set right = 0. Columns 0 to 0 are left, so continue.

Step 3: Read row 1 from column 0 to 0: 3. Set bottom = 0. Now top > bottom, so stop.

Result: [1, 2, 4, 3]

Non-Square Matrices

Rows and columns shrink independently, so rectangles need no special handling. Here dumpSpiral([[1,2,3],[4,5,6]]) returns [1, 2, 3, 6, 5, 4]:

Loading visualization...

The top row gives 1, 2, 3. The right column now has only row 1 left, which gives 6. The bottom row is read from column 1 back to column 0, which gives 5, 4. Then bottom moves above top, and the loop stops.

Implementation

Here's the Java solution:

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

public class Solution {
  /**
   * Returns the integers in the matrix in clockwise
   * spiral order.
   *
   * @param matrix Input matrix.
   * @return List of integers in clockwise spiral order.
   */
  public List<Integer> dumpSpiral(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;
    while (true) {
      for (int col = left; col <= right; col++) {
        result.add(matrix[top][col]);
      }
      top++;
      if (top > bottom) break;
      for (int row = top; row <= bottom; row++) {
        result.add(matrix[row][right]);
      }
      right--;
      if (left > right) break;
      for (int col = right; col >= left; col--) {
        result.add(matrix[bottom][col]);
      }
      bottom--;
      if (top > bottom) break;
      for (int row = bottom; row >= top; row--) {
        result.add(matrix[row][left]);
      }
      left++;
      if (left > right) break;
    }
    return result;
  }
}

The while (true) loop reads one ring per pass. Each for loop reads one edge, and the line after it shrinks the matching bound. The break after each edge ends the traversal as soon as no rows or no columns are left, which also means the loop never needs a separate count of elements.

Complexity Analysis

Time Complexity: O(m * n)

Each element is added to result exactly once, because every edge read removes its row or column from the unread rectangle. The bound updates and checks are O(1) per edge. For an m x n matrix, that is O(m * n) work in total.

Space Complexity: O(1)

The algorithm uses four integer bounds and a loop index, whatever the size of the matrix. The result list has m * n elements, but it is the required output and is not counted as extra space. No visited grid is needed, because the bounds already record which rows and columns are done.

Common Pitfalls

  1. Checking the bounds only once per ring: if the loop checks only at the top of each pass, a last single row or column is read twice. Check after every edge.

  2. Comparing the wrong pair of bounds: after reading a row, compare top with bottom. After reading a column, compare left with right. Mixing them up stops too early or reads too far.

  3. Off-by-one loop ranges: every edge range is inclusive at both ends, from left to right or from top to bottom. An exclusive end skips the corner element.

  4. Assuming square matrices: using the row count for both dimensions breaks rectangular inputs. Take bottom from the row count and right from the column count.

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 you write code.

  2. Name the bounds out loud: say what top, bottom, left and right mean before you code. It makes each loop range easy to explain.

  3. Test a single row early: run [[1,3]] through your code by hand. It is the quickest way to show that the check after each edge is needed.

  4. Mention the alternative: a visited grid with direction turning also works, but it needs O(m * n) extra space. The bounds approach avoids that.

  5. Watch for follow-ups: a common follow-up is to fill an n x n matrix with 1 to n squared in spiral order. The same four bounds work, with writes in place of reads.

Key Takeaways

  • Four bounds, top, bottom, left and right, describe the rectangle that is still unread.
  • Each edge read shrinks exactly one bound: the top row moves top down, the right column moves right in, and so on.
  • Checking top > bottom or left > right after every edge prevents a last single row or column from being read twice.
  • Every element is read once, so the time is O(m * n), and the bounds take O(1) extra space.
  • The shrinking-bounds idea also applies to other layer-by-layer matrix problems.

Related Problems and Practice

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

  • Image matrix 90-degree twist (matrix rotation also works layer by layer)
  • Zero out rows and columns (another matrix traversal pattern)
  • Number of islands (grid traversal with neighbor checks)

Solutions in Other Languages

Every version below uses the same four bounds and the same check after each edge.

Python

from typing import List


class Solution:
    def dump_spiral(self, matrix: List[List[int]]) -> List[int]:
        """
        Returns the integers in the matrix in clockwise
        spiral order.
        :param matrix: Input matrix.
        :return: List of integers in clockwise spiral order.
        """
        result = []
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1
        while True:
            for col in range(left, right + 1):
                result.append(matrix[top][col])
            top += 1
            if top > bottom:
                break
            for row in range(top, bottom + 1):
                result.append(matrix[row][right])
            right -= 1
            if left > right:
                break
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1
            if top > bottom:
                break
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1
            if left > right:
                break
        return result

JavaScript

class Solution {
  /**
   * Returns the integers in the matrix in clockwise
   * spiral order.
   *
   * @param {Array<Array<number>>} matrix Input matrix.
   * @return {Array<number>} List of integers in clockwise spiral order.
   */
  dumpSpiral(matrix) {
    const result = [];
    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;
    while (true) {
      for (let col = left; col <= right; col++) {
        result.push(matrix[top][col]);
      }
      top++;
      if (top > bottom) break;
      for (let row = top; row <= bottom; row++) {
        result.push(matrix[row][right]);
      }
      right--;
      if (left > right) break;
      for (let col = right; col >= left; col--) {
        result.push(matrix[bottom][col]);
      }
      bottom--;
      if (top > bottom) break;
      for (let row = bottom; row >= top; row--) {
        result.push(matrix[row][left]);
      }
      left++;
      if (left > right) break;
    }
    return result;
  }
}

module.exports = Solution;

TypeScript

class Solution {
  /**
   * Returns the integers in the matrix in clockwise
   * spiral order.
   *
   * @param matrix - Input matrix.
   * @returns List of integers in clockwise spiral order.
   */
  dumpSpiral(matrix: number[][]): number[] {
    const result: number[] = [];
    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;
    while (true) {
      for (let col = left; col <= right; col++) {
        result.push(matrix[top][col]);
      }
      top++;
      if (top > bottom) break;
      for (let row = top; row <= bottom; row++) {
        result.push(matrix[row][right]);
      }
      right--;
      if (left > right) break;
      for (let col = right; col >= left; col--) {
        result.push(matrix[bottom][col]);
      }
      bottom--;
      if (top > bottom) break;
      for (let row = bottom; row >= top; row--) {
        result.push(matrix[row][left]);
      }
      left++;
      if (left > right) break;
    }
    return result;
  }
}

export { Solution };

C++

#include <vector>
#include <iostream>

class Solution {
public:
  /**
   * DumpSpiral returns the integers in the matrix in clockwise spiral order
   * @param matrix Input matrix.
   * @return Vector of integers in clockwise spiral order.
   */
  std::vector<int> dumpSpiral(std::vector<std::vector<int>> &matrix) {
    std::vector<int> result;
    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;
    while (true) {
      for (int col = left; col <= right; col++) {
        result.push_back(matrix[top][col]);
      }
      top++;
      if (top > bottom) break;
      for (int row = top; row <= bottom; row++) {
        result.push_back(matrix[row][right]);
      }
      right--;
      if (left > right) break;
      for (int col = right; col >= left; col--) {
        result.push_back(matrix[bottom][col]);
      }
      bottom--;
      if (top > bottom) break;
      for (int row = bottom; row >= top; row--) {
        result.push_back(matrix[row][left]);
      }
      left++;
      if (left > right) break;
    }
    return result;
  }
};

Go

package solution

// You can import standard packages below, like "fmt" and "strings":

// DumpSpiral returns the integers in the matrix in clockwise spiral order
func (s *Solution) DumpSpiral(matrix [][]int) []int {
	result := make([]int, 0)
	top, bottom := 0, len(matrix)-1
	left, right := 0, len(matrix[0])-1
	for {
		for col := left; col <= right; col++ {
			result = append(result, matrix[top][col])
		}
		top++
		if top > bottom {
			break
		}
		for row := top; row <= bottom; row++ {
			result = append(result, matrix[row][right])
		}
		right--
		if left > right {
			break
		}
		for col := right; col >= left; col-- {
			result = append(result, matrix[bottom][col])
		}
		bottom--
		if top > bottom {
			break
		}
		for row := bottom; row >= top; row-- {
			result = append(result, matrix[row][left])
		}
		left++
		if left > right {
			break
		}
	}
	return result
}

// Solution is required to run your method. Do not modify.
type Solution struct {
}

Go has no while loop, so the solution uses a bare for and leaves it with break when two bounds cross.

Scala

Scala has no break, so this version returns result.toList directly from the loop when the bounds cross.

import scala.collection.mutable

class Solution {
  /**
   * Returns the integers in the matrix in clockwise
   * spiral order.
   *
   * @param matrix Input matrix.
   * @return List of integers in clockwise spiral order.
   */
  def dumpSpiral(matrix: Array[Array[Int]]): List[Int] = {
    val result = mutable.ArrayBuffer[Int]()
    var top = 0
    var bottom = matrix.length - 1
    var left = 0
    var right = matrix(0).length - 1
    while (true) {
      for (col <- left to right) {
        result.append(matrix(top)(col))
      }
      top += 1
      if (top > bottom) return result.toList
      for (row <- top to bottom) {
        result.append(matrix(row)(right))
      }
      right -= 1
      if (left > right) return result.toList
      for (col <- right to left by -1) {
        result.append(matrix(bottom)(col))
      }
      bottom -= 1
      if (top > bottom) return result.toList
      for (row <- bottom to top by -1) {
        result.append(matrix(row)(left))
      }
      left += 1
      if (left > right) return result.toList
    }
    result.toList
  }
}

Kotlin

class Solution {
  /**
   * Returns the integers in the matrix in clockwise
   * spiral order.
   *
   * @param matrix Input matrix.
   * @return List of integers in clockwise spiral order.
   */
  fun dumpSpiral(matrix: Array<IntArray>): List<Int> {
    val result = mutableListOf<Int>()
    var top = 0
    var bottom = matrix.size - 1
    var left = 0
    var right = matrix[0].size - 1
    while (true) {
      for (col in left..right) {
        result.add(matrix[top][col])
      }
      top++
      if (top > bottom) break
      for (row in top..bottom) {
        result.add(matrix[row][right])
      }
      right--
      if (left > right) break
      for (col in right downTo left) {
        result.add(matrix[bottom][col])
      }
      bottom--
      if (top > bottom) break
      for (row in bottom downTo top) {
        result.add(matrix[row][left])
      }
      left++
      if (left > right) break
    }
    return result
  }
}

Swift

import Foundation

class Solution {
    /**
     * Returns the integers in the matrix in clockwise
     * spiral order.
     *
     * - Parameter matrix: Input matrix.
     * - Returns: List of integers in clockwise spiral order.
     */
    func dumpSpiral(_ matrix: [[Int]]) -> [Int] {
        var result: [Int] = []
        var top = 0, bottom = matrix.count - 1
        var left = 0, right = matrix[0].count - 1
        while true {
            for col in left...right {
                result.append(matrix[top][col])
            }
            top += 1
            if top > bottom { break }
            for row in top...bottom {
                result.append(matrix[row][right])
            }
            right -= 1
            if left > right { break }
            for col in stride(from: right, through: left, by: -1) {
                result.append(matrix[bottom][col])
            }
            bottom -= 1
            if top > bottom { break }
            for row in stride(from: bottom, through: top, by: -1) {
                result.append(matrix[row][left])
            }
            left += 1
            if left > right { break }
        }
        return result
    }
}

Dart

class Solution {
  /// Returns the integers in the matrix in clockwise
  /// spiral order.
  ///
  /// [matrix] Input matrix.
  /// Returns list of integers in clockwise spiral order.
  List<int> dumpSpiral(List<List<int>> matrix) {
    List<int> result = [];
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;
    while (true) {
      for (int col = left; col <= right; col++) {
        result.add(matrix[top][col]);
      }
      top++;
      if (top > bottom) break;
      for (int row = top; row <= bottom; row++) {
        result.add(matrix[row][right]);
      }
      right--;
      if (left > right) break;
      for (int col = right; col >= left; col--) {
        result.add(matrix[bottom][col]);
      }
      bottom--;
      if (top > bottom) break;
      for (int row = bottom; row >= top; row--) {
        result.add(matrix[row][left]);
      }
      left++;
      if (left > right) break;
    }
    return result;
  }
}

C#

using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// Returns the integers in the matrix in clockwise
    /// spiral order.
    /// </summary>
    /// <param name="matrix">Input matrix.</param>
    /// <returns>List of integers in clockwise spiral order.</returns>
    public List<int> DumpSpiral(int[][] matrix) {
        var result = new List<int>();
        int top = 0, bottom = matrix.Length - 1;
        int left = 0, right = matrix[0].Length - 1;
        while (true) {
            for (int col = left; col <= right; col++) {
                result.Add(matrix[top][col]);
            }
            top++;
            if (top > bottom) break;
            for (int row = top; row <= bottom; row++) {
                result.Add(matrix[row][right]);
            }
            right--;
            if (left > right) break;
            for (int col = right; col >= left; col--) {
                result.Add(matrix[bottom][col]);
            }
            bottom--;
            if (top > bottom) break;
            for (int row = bottom; row >= top; row--) {
                result.Add(matrix[row][left]);
            }
            left++;
            if (left > right) break;
        }
        return result;
    }
}

PHP

<?php

class Solution {
    /**
     * Returns the integers in the matrix in clockwise
     * spiral order.
     *
     * @param array $matrix Input matrix.
     * @return array List of integers in clockwise spiral order.
     */
    public function dumpSpiral(array $matrix): array {
        $result = [];
        $top = 0;
        $bottom = count($matrix) - 1;
        $left = 0;
        $right = count($matrix[0]) - 1;
        while (true) {
            for ($col = $left; $col <= $right; $col++) {
                $result[] = $matrix[$top][$col];
            }
            $top++;
            if ($top > $bottom) break;
            for ($row = $top; $row <= $bottom; $row++) {
                $result[] = $matrix[$row][$right];
            }
            $right--;
            if ($left > $right) break;
            for ($col = $right; $col >= $left; $col--) {
                $result[] = $matrix[$bottom][$col];
            }
            $bottom--;
            if ($top > $bottom) break;
            for ($row = $bottom; $row >= $top; $row--) {
                $result[] = $matrix[$row][$left];
            }
            $left++;
            if ($left > $right) break;
        }
        return $result;
    }
}

Ruby

class Solution
  # Returns the integers in the matrix in clockwise
  # spiral order.
  #
  # @param matrix [Array<Array<Integer>>] Input matrix
  # @return [Array<Integer>] List of integers in clockwise spiral order
  def dump_spiral(matrix)
    result = []
    top, bottom = 0, matrix.length - 1
    left, right = 0, matrix[0].length - 1
    loop do
      (left..right).each do |col|
        result << matrix[top][col]
      end
      top += 1
      break if top > bottom
      (top..bottom).each do |row|
        result << matrix[row][right]
      end
      right -= 1
      break if left > right
      right.downto(left) do |col|
        result << matrix[bottom][col]
      end
      bottom -= 1
      break if top > bottom
      bottom.downto(top) do |row|
        result << matrix[row][left]
      end
      left += 1
      break if left > right
    end
    result
  end
end

Rust

The bounds are i32 so that right and bottom can drop below zero without an underflow. They are cast to usize only for indexing.

pub struct Solution;

impl Solution {
    /// Returns the integers in the matrix in clockwise
    /// spiral order.
    ///
    /// # Arguments
    /// * `matrix` - Input matrix.
    ///
    /// # Returns
    /// A Vec<i32> containing integers in clockwise spiral order.
    pub fn dump_spiral(&self, matrix: Vec<Vec<i32>>) -> Vec<i32> {
        let mut result = Vec::new();
        let (mut top, mut bottom) = (0i32, matrix.len() as i32 - 1);
        let (mut left, mut right) = (0i32, matrix[0].len() as i32 - 1);
        loop {
            for col in left..=right {
                result.push(matrix[top as usize][col as usize]);
            }
            top += 1;
            if top > bottom {
                break;
            }
            for row in top..=bottom {
                result.push(matrix[row as usize][right as usize]);
            }
            right -= 1;
            if left > right {
                break;
            }
            for col in (left..=right).rev() {
                result.push(matrix[bottom as usize][col as usize]);
            }
            bottom -= 1;
            if top > bottom {
                break;
            }
            for row in (top..=bottom).rev() {
                result.push(matrix[row as usize][left as usize]);
            }
            left += 1;
            if left > right {
                break;
            }
        }
        result
    }
}

Practice on Firecode

Spiral Matrix is the kind of problem that clicks once you've traced it a few times. The shrinking-bounds pattern shows up in other matrix problems, so time spent here pays off 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 go into your next interview with confidence.

Frequently Asked Questions

What is the four-boundary approach for spiral matrix traversal?
Keep four bounds: top, bottom, left and right, the first and last rows and columns that are not read yet. Read the top row from left to right and move top down. Read the right column from top to bottom and move right in. Read the bottom row from right to left and move bottom up. Read the left column from bottom to top and move left in. Repeat until the bounds cross.
What is the time complexity of spiral matrix traversal?
O(m * n), where m is the number of rows and n is the number of columns. Each element is read exactly once, and each bound check is O(1).
What is the space complexity of the four-boundary spiral approach?
O(1) extra space. The algorithm uses four integer bounds and a loop index. The output list has m * n elements, but it is the required answer and is not counted as extra space.
Why check the bounds after every edge and not only once per ring?
A ring can end in the middle. When only one row or one column is left, reading it uses up the remaining rows or columns. If the loop goes on to the next edge without a check, it reads the same elements again in reverse. Checking after each edge stops the loop at the right moment.
How do you handle non-square matrices in spiral traversal?
The four bounds are independent, so rows and columns shrink separately. A 2x3 matrix gives [1, 2, 3, 6, 5, 4]. A 1x3 matrix stops after the top row, and a 3x1 matrix stops after the right column. The checks after each edge cover these shapes with no special cases.
What edge cases should you test for spiral matrix?
Test a 1x1 matrix, a single row (1xN), a single column (Nx1), a 2x2 matrix, and tall or wide rectangles such as 5x3 or 3x5. The last ring of a rectangle is often a single row or column, which is where a missing bound check reads elements twice.
How does the boundary approach compare to a visited grid with direction turning?
Both run in O(m * n) time. A visited grid marks each cell as read and turns clockwise when the next cell is out of range or already read, which costs O(m * n) extra space. The boundary approach needs no grid, because the four bounds already record which rows and columns are done. That brings extra space down to O(1).
Does the spiral traversal modify the input matrix?
No. The algorithm only reads matrix values and changes the four bound variables. The input is left exactly as it was passed in.
What is the difference between spiral matrix and rotate matrix problems?
Spiral matrix is a traversal problem that reads elements in spiral order without modifying the matrix. Rotate matrix is a transformation problem that moves elements to new positions. Spiral matrix produces a 1D list from a 2D grid, while rotation produces a rotated 2D grid.
How often does spiral matrix appear in coding interviews?
Spiral matrix is a common interview question at companies like Microsoft and Amazon. It tests matrix indexing and careful boundary handling. It often appears as a standalone question or as a warm-up in a matrix round.