Spiral Matrix

2D MatrixSimulation

MediumLeetCode #54

25 min

Problem Statement

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

Example

Example 1:

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

Solution

The problem can be solved by simulating the spiral traversal. We can use four pointers to define the boundaries of the current layer of the matrix: `rowStart`, `rowEnd`, `colStart`, and `colEnd`.

We traverse the matrix layer by layer, from the outside towards the center. In each layer, we traverse right, then down, then left, and finally up, adding the elements to our result list and shrinking the boundaries after each traversal.

Algorithm Steps

Initialize four boundary pointers: `rowStart`, `rowEnd`, `colStart`, `colEnd`.
While `rowStart <= rowEnd` and `colStart <= colEnd`:
Traverse right across the top row (`rowStart`). After, increment `rowStart`.
Traverse down the rightmost column (`colEnd`). After, decrement `colEnd`.
If boundaries are still valid, traverse left across the bottom row (`rowEnd`). After, decrement `rowEnd`.
If boundaries are still valid, traverse up the leftmost column (`colStart`). After, increment `colStart`.
Repeat until the boundaries cross.

Spiral Matrix Traversal

Progress1 / 1

Ready to start.

Result: []

Spiral Matrix


class Solution:
    def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
        if not matrix:
            return []
        
        res = []
        rows, cols = len(matrix), len(matrix[0])
        row_start, row_end = 0, rows - 1
        col_start, col_end = 0, cols - 1
        
        while row_start <= row_end and col_start <= col_end:
            # Traverse Right
            for j in range(col_start, col_end + 1):
                res.append(matrix[row_start][j])
            row_start += 1
            
            # Traverse Down
            for i in range(row_start, row_end + 1):
                res.append(matrix[i][col_end])
            col_end -= 1
            
            if row_start <= row_end:
                # Traverse Left
                for j in range(col_end, col_start - 1, -1):
                    res.append(matrix[row_end][j])
                row_end -= 1
            
            if col_start <= col_end:
                # Traverse Up
                for i in range(row_end, row_start - 1, -1):
                    res.append(matrix[i][col_start])
                col_start += 1
                
        return res