The problem of traversing a matrix in a spiral order can be solved by iteratively processing the outer layers of the matrix. Here’s a Python implementation:

from typing import List

def spiral_order(matrix: List[List[int]]) -> List[int]:
    result = []
    
    while matrix:
        # Traverse the top row
        result.extend(matrix.pop(0))
        
        # Traverse the right column
        if matrix and matrix[0]:
            for row in matrix:
                result.append(row.pop())
        
        # Traverse the bottom row in reverse
        if matrix and matrix[0]:
            result.extend(matrix.pop()[::-1])
        
        # Traverse the left column in reverse
        if matrix and matrix[0]:
            for row in matrix[::-1]:
                result.append(row.pop(0))
    
    return result

# Example usage:
matrix1 = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print(spiral_order(matrix1))  # Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

matrix2 = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12]
]
print(spiral_order(matrix2))  # Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Explanation:

  • We use a while loop to iteratively process the outer layers of the matrix until the matrix is empty.
  • For each iteration, we traverse the top row, right column, bottom row, and left column in a clockwise direction.
  • We adjust the matrix by popping elements from the processed rows and columns.

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.
  • We visit each element once.

Space Complexity:

  • The space complexity is O(1) as we use a constant amount of extra space.