54. Spiral Matrix

Quick Identifier

• Topic: arrays-hashing
• Pattern: Matrix Simulation (Shrinking Boundaries)
• Hint: Set up four invisible walls: top, bottom, left, right. Walk along a wall, then shrink it inward. Repeat until the walls crush you.
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Microsoft, Apple
• LeetCode: 54

Quick Sights

• Time Complexity: O(m * n). We visit every single cell in the $M \times N$ matrix exactly once.
• Space Complexity: O(1). Excluding the space required for the output array, we only use four integer pointers to represent the boundaries. No visited matrix is needed.
• Core Mechanism: Maintain four boundaries: top, bottom, left, right.
  1. Traverse from left to right along the top row. Then increment top (move the top wall down).
  2. Traverse from top to bottom along the right column. Then decrement right (move the right wall left).
  3. Traverse from right to left along the bottom row. Then decrement bottom (move the bottom wall up).
  4. Traverse from bottom to top along the left column. Then increment left (move the left wall right).
  5. Repeat while left <= right and top <= bottom.

Concept Explanation

As a senior engineer, don't overcomplicate this with Direction Vectors (dx, dy) and visited matrices. That is an $O(m \cdot n)$ space approach designed for Graph Traversals (DFS/BFS). This is not a graph problem; it's a rigid geometry problem.

The simplest way to conceptualize this is the Crushing Room trap from Indiana Jones.

1. You are in a room with four walls.
2. You walk flush against the Top wall from the Left corner to the Right corner.
3. Once you finish, the Top wall violently shifts downward one step. You can never walk there again.
4. Now you walk flush against the Right wall, from Top to Bottom.
5. The Right wall shifts inward.
6. You repeat this clockwise pattern. Because the walls actually physically shrink the dimensions of the room, you never have to "remember" where you've been (no visited matrix). The walls prevent you from going back.
7. The loop terminates when the walls crash into each other (top > bottom or left > right).

Diagram

This flowchart highlights the clockwise traversal and the critical boundary checks needed for non-square matrices.

Study Pattern (SDE3+)

• 0–3 min: Immediately describe the "Four Boundaries" shrinking strategy. Clearly contrast it against the naive "Direction Array + Visited Matrix" approach, pointing out that yours saves $O(m \cdot n)$ space.
• Implementation pass: The most common mistake in this problem happens with non-square rectangles (e.g., $1 \times 3$ or $3 \times 1$). After you sweep Top and Right, the walls might have crossed. You must add an if (top <= bottom && left <= right) check before attempting to sweep the Bottom and Left rows to prevent duplicate counting.
• 5 min extension: Discuss how to reverse the algorithm. What if you were given an empty matrix and the 1D array of numbers, and asked to fill the matrix in a spiral pattern? (LeetCode 59: Spiral Matrix II). The code structure is 100% identical, you just swap result.push(matrix[r][c]) with matrix[r][c] = currentNum++.

Approaches

• Simulation with Visited Map — Use dx, dy arrays [0, 1, 0, -1]. If you hit an edge or a visited cell, turn 90 degrees. Time: $O(m \cdot n)$, Space: $O(m \cdot n)$ extra space for visited map. Suboptimal.
• Layer-by-Layer Shrinking Boundaries — Track four integer walls. Time: $O(m \cdot n)$, Space: $O(1)$ extra space. (Always pick this)

Optimal Solution

Go

func spiralOrder(matrix [][]int) []int {
	if len(matrix) == 0 {
		return nil
	}

	result := make([]int, 0, len(matrix)*len(matrix[0]))

	top := 0
	bottom := len(matrix) - 1
	left := 0
	right := len(matrix[0]) - 1

	for top <= bottom && left <= right {
		// 1. Sweep Top Row (Left to Right)
		for c := left; c <= right; c++ {
			result = append(result, matrix[top][c])
		}
		top++ // Shrink top wall downward

		// 2. Sweep Right Column (Top to Bottom)
		for r := top; r <= bottom; r++ {
			result = append(result, matrix[r][right])
		}
		right-- // Shrink right wall leftward

		// CRITICAL: Check if walls crossed before sweeping back.
		// This prevents duplicates in non-square matrices (e.g., 1x3 or 3x1)
		if top <= bottom && left <= right {
			// 3. Sweep Bottom Row (Right to Left)
			for c := right; c >= left; c-- {
				result = append(result, matrix[bottom][c])
			}
			bottom-- // Shrink bottom wall upward

			// 4. Sweep Left Column (Bottom to Top)
			for r := bottom; r >= top; r-- {
				result = append(result, matrix[r][left])
			}
			left++ // Shrink left wall rightward
		}
	}

	return result
}

JavaScript

function spiralOrder(matrix) {
	if (matrix.length === 0) return [];

	const result = [];
	let top = 0;
	let bottom = matrix.length - 1;
	let left = 0;
	let right = matrix[0].length - 1;

	while (top <= bottom && left <= right) {
		// 1. Top Row
		for (let c = left; c <= right; c++) {
			result.push(matrix[top][c]);
		}
		top++;

		// 2. Right Col
		for (let r = top; r <= bottom; r++) {
			result.push(matrix[r][right]);
		}
		right--;

		// Check condition before backwards sweeps
		if (top <= bottom && left <= right) {
			// 3. Bottom Row
			for (let c = right; c >= left; c--) {
				result.push(matrix[bottom][c]);
			}
			bottom--;

			// 4. Left Col
			for (let r = bottom; r >= top; r--) {
				result.push(matrix[r][left]);
			}
			left++;
		}
	}

	return result;
}

Walkthrough

Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] (3x3 square)

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

Edge Cases

• A single row matrix [[1, 2, 3]]. The Top sweep grabs everything. The Right sweep grabs nothing. The check fails, preventing the Bottom sweep from grabbing [2, 1] redundantly.
• A single column matrix [[1], [2], [3]]. The Top sweep grabs [1]. The Right sweep grabs [2, 3]. The check fails, preventing Left/Bottom sweeps.

Pitfalls

• Forgetting the if (top <= bottom && left <= right) check in the middle of the while loop. If you have a $3 \times 5$ matrix, the loops will execute perfectly for the outer rings. But the innermost ring will just be a 1D line. Without the middle check, you will sweep down the line, and then mistakenly sweep back up the exact same line.

Similar Problems

• 59. Spiral Matrix II — Generating the matrix instead of reading it. Same loop structure.
• 048. Rotate Image — Matrix transformation.

Mind-Map Tags

#matrix #simulation #boundaries #spiral