LeetCode Solutions Blog

Spiral Matrix

Number: 54

Difficulty: Medium

Paid? No

Problem Description

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

Key Insights

Use four boundaries: top, bottom, left, and right to track the current layer.
Traverse right across the top row, then down the right column, then left on the bottom row, and finally up the left column.
After each direction, adjust the corresponding boundary to move inward.
Continue the traversal until the boundaries cross.

Space and Time Complexity

Time Complexity: O(m * n) since each element is visited exactly once. Space Complexity: O(1) extra space (excluding the space required for the output list).

Solution

The solution uses a simulation approach with boundary pointers (top, bottom, left, right). At each step, the boundaries indicate the current submatrix to traverse. You iterate as follows:

Traverse from left to right along the top boundary.
Traverse downward along the right boundary.
If the top boundary has not passed the bottom, traverse from right to left along the bottom boundary.
If the left boundary has not passed the right, traverse upward along the left boundary. After each traversal, the boundaries are adjusted inward. This continues until all elements have been visited.

Code Solutions

def spiralOrder(matrix):
    # Initialize the boundaries of the matrix
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    result = []  # This will store the spiral order

    # Loop until the pointers cross each other
    while top <= bottom and left <= right:
        # Traverse from left to right on the current top row
        for col in range(left, right + 1):
            result.append(matrix[top][col])
        top += 1  # Move the top boundary down

        # Traverse downwards on the current right column
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1  # Move the right boundary to the left

        # Traverse from right to left on the current bottom row, if valid
        if top <= bottom:
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1  # Move the bottom boundary up

        # Traverse upwards on the current left column, if valid
        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1  # Move the left boundary right

    return result

# Example usage:
# print(spiralOrder([[1,2,3],[4,5,6],[7,8,9]]))