Skip to main content
CodeEasy v0.1

Spiral Matrix

Medium Subject: Math & Geometry
Time Complexity
O(M * N)
Space Complexity
O(1)

Problem Description

Problem Statement

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

Example 1:

  • Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
  • Output: [1,2,3,6,9,8,7,4,5]

Optimal Solution

Python

Approach: Layer by Layer Simulation

Maintain four boundaries: top, bottom, left, and right. Simulate the spiral traversal. Go left to right on top, then top to bottom on right, then right to left on bottom, then bottom to top on left. After each pass, shrink the corresponding boundary.

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1

        while top <= bottom and left <= right:
            # Traverse Right
            for c in range(left, right + 1): res.append(matrix[top][c])
            top += 1

            # Traverse Down
            for r in range(top, bottom + 1): res.append(matrix[r][right])
            right -= 1

            if top <= bottom:
                # Traverse Left
                for c in range(right, left - 1, -1): res.append(matrix[bottom][c])
                bottom -= 1

            if left <= right:
                # Traverse Up
                for r in range(bottom, top - 1, -1): res.append(matrix[r][left])
                left += 1

        return res