Matrix Spiral Traversal

January 9, 2024

Problem #

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

Example: #

1. Input:

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

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

2. Input:

   [
     [1,  2,  3,  4],
     [5,  6,  7,  8],
     [9, 10, 11, 12]
   ]
   

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

Solution Approach #

The solution involves iterating over the matrix in a spiral manner. This can be achieved by maintaining four boundaries (top, bottom, left, right) and iteratively traversing the edges of the matrix, moving the boundaries inward each time an edge is traversed.

Algorithm Steps #

1. Initialize four boundaries: top, bottom, left, and right.
2. While top <= bottom and left <= right:
   • Traverse from left to right along the top row and increase top.
   • Traverse from top to bottom along the right column and decrease right.
   • If top <= bottom, traverse from right to left along the bottom row and decrease bottom.
   • If left <= right, traverse from bottom to top along the left column and increase left.
3. Return the spiral order traversal.

Code (Python) #

def spiralOrder(matrix):
    if not matrix:
        return []

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

    while top <= bottom and left <= right:
        for i in range(left, right + 1):
            spiral.append(matrix[top][i])
        top += 1

        for i in range(top, bottom + 1):
            spiral.append(matrix[i][right])
        right -= 1

        if top <= bottom:
            for i in range(right, left - 1, -1):
                spiral.append(matrix[bottom][i])
            bottom -= 1

        if left <= right:
            for i in range(bottom, top - 1, -1):
                spiral.append(matrix[i][left])
            left += 1

    return spiral

# Test the function
print(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))  # Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
print(spiralOrder([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]))  # Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Time Complexity #

The time complexity is O(m*n), where m is the number of rows and n is the number of columns in the matrix.

Space Complexity #

The space complexity is O(1) if we ignore the output array, as no additional space is used for computation.