Spiral Matrix

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]

Constraints:

m == matrix.length n == matrix[i].length 1 <= m, n <= 10 -100 <= matrix[i][j] <= 100

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        result = []
        if not matrix:
            return result

        row_begin, row_end = 0, len(matrix) - 1
        col_begin, col_end = 0, len(matrix[0]) - 1

        while row_begin <= row_end and col_begin <= col_end:
            # Traverse right
            for j in range(col_begin, col_end + 1):
                result.append(matrix[row_begin][j])
            row_begin += 1

            # Traverse down
            for i in range(row_begin, row_end + 1):
                result.append(matrix[i][col_end])
            col_end -= 1

            if row_begin <= row_end and col_begin <= col_end:
                # Traverse left
                for j in range(col_end, col_begin - 1, -1):
                    result.append(matrix[row_end][j])
                row_end -= 1

                # Traverse up
                for i in range(row_end, row_begin - 1, -1):
                    result.append(matrix[i][col_begin])
                col_begin += 1

        return result

Explanation:

The spiral order traversal of a matrix involves traversing the outer layers of the matrix in a clockwise spiral pattern until we reach the center. We maintain boundaries (row_begin, row_end, col_begin, col_end) that define the current layer to be traversed. After traversing each layer, we shrink the boundaries to move inwards.

1. Initialization:

   • Initialize result list to store the elements in spiral order.
   • Initialize row_begin, row_end, col_begin, and col_end to represent the boundaries of the matrix.

2. Iteration:

   • The while loop continues as long as row_begin is less than or equal to row_end and col_begin is less than or equal to col_end.
   • Traverse Right: Iterate from col_begin to col_end and append the elements of the first row (matrix[row_begin][j]) to the result. Increment row_begin.
   • Traverse Down: Iterate from row_begin to row_end and append the elements of the last column (matrix[i][col_end]) to the result. Decrement col_end.
   • Traverse Left: Before traversing left and up, we check if row_begin <= row_end and col_begin <= col_end to avoid duplicate traversals when the matrix is not rectangular. Iterate from col_end to col_begin and append the elements of the last row (matrix[row_end][j]) to the result. Decrement row_end.
   • Traverse Up: Iterate from row_end to row_begin and append the elements of the first column (matrix[i][col_begin]) to the result. Increment col_begin.

3. Return:

   • After traversing all the layers, return the result list.

Example:

For the input matrix = [[1,2,3],[4,5,6],[7,8,9]],

1. Initially, row_begin = 0, row_end = 2, col_begin = 0, col_end = 2.
2. Traverse right: result = [1, 2, 3], row_begin = 1.
3. Traverse down: result = [1, 2, 3, 6, 9], col_end = 1.
4. Traverse left: result = [1, 2, 3, 6, 9, 8, 7], row_end = 1.
5. Traverse up: result = [1, 2, 3, 6, 9, 8, 7, 4], col_begin = 1.
6. Traverse right: result = [1, 2, 3, 6, 9, 8, 7, 4, 5], row_begin = 2.

Time Complexity:

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:

O(1) excluding the space used for the output list. If the output list is considered, the space complexity is O(M * N).