Spiral Matrix medium

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]

Example 2

Input: matrix = [[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]

Steps

The core idea is to simulate the spiral traversal using four pointers: top, bottom, left, and right. These pointers define the boundaries of the unvisited portion of the matrix. We repeatedly traverse the outer layer of the matrix, updating the pointers as we go, until all elements are visited.

1. Initialization: Initialize top = 0, bottom = m - 1, left = 0, right = n - 1, and an empty result list result.

2. Iteration: While left <= right and top <= bottom:

   • Traverse Right: Iterate from left to right, adding each element in the current row (matrix[top][i]) to result. Then increment top.
   • Traverse Down: If top <= bottom, iterate from top to bottom, adding each element in the current column (matrix[i][right]) to result. Then decrement right.
   • Traverse Left: If left <= right and top <= bottom, iterate from right to left in reverse order, adding each element in the current row (matrix[bottom][i]) to result. Then decrement bottom.
   • Traverse Up: If left <= right and top <= bottom, iterate from bottom to top in reverse order, adding each element in the current column (matrix[i][left]) to result. Then increment left.

3. Return: Return the result list.

Explanation

The algorithm systematically peels off layers from the matrix. Each iteration processes one layer, moving from right to down to left to up. The conditions left <= right and top <= bottom ensure that we don't go out of bounds and that we stop when all elements have been visited. The nested if conditions handle cases where the matrix has an odd number of rows or columns, preventing duplicate traversal of elements.

Code

def spiralOrder(matrix):
    """
    Traverses a matrix in spiral order.

    Args:
      matrix: A list of lists representing the matrix.

    Returns:
      A list containing all elements of the matrix in spiral order.
    """
    m = len(matrix)
    n = len(matrix[0]) if m > 0 else 0  #Handle empty matrix case
    top, bottom = 0, m - 1
    left, right = 0, n - 1
    result = []

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

        # Traverse Down
        if top <= bottom:
            for i in range(top, bottom + 1):
                result.append(matrix[i][right])
            right -= 1

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

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

    return result

Complexity

• Time Complexity: O(m * n), where 'm' and 'n' are the dimensions of the matrix. We visit each element exactly once.
• Space Complexity: O(1) if we ignore the space used for the output list. The space used for the output list is O(m * n) in the worst case (when the matrix is completely filled). If we only consider auxiliary space, it's O(1).