Spiral Matrix - Leetcode Solution

Problem: 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]

To solve this problem, we can use a simulation method, where we simulate the spiral traversal of the matrix.

Approach:

1. Initialize four variables - top, bottom, left, right to represent the boundaries of the matrix.

2. Initialize a variable called direction to represent the direction of the traversal. Start with direction = 0 (left to right).

3. Initialize an empty list called result to store the spiral traversal of the matrix.

4. While top<=bottom and left<=right, do the following:

   a) If direction == 0 (left to right), traverse the top row, i.e. for each element in matrix[top][left:right+1], append it to result. Then increment top and change direction to 1 (top to bottom).

   b) If direction == 1 (top to bottom), traverse the right column, i.e. for each element in matrix[top+1:bottom+1][right], append it to result. Then decrement right and change direction to 2 (right to left).

   c) If direction == 2 (right to left), traverse the bottom row, i.e. for each element in matrix[bottom][left:right+1][::-1], append it to result (we need to reverse the order). Then decrement bottom and change direction to 3 (bottom to top).

   d) If direction == 3 (bottom to top), traverse the left column, i.e. for each element in matrix[top+1:bottom+1][left], append it to result. Then increment left and change direction to 0 (left to right).

5. Return the result list.

Implementation:

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

top, bottom = 0, len(matrix)-1
left, right = 0, len(matrix[0])-1
direction = 0 # 0: left to right, 1: top to bottom, 2: right to left, 3: bottom to top

result = []
while top<=bottom and left<=right:
    if direction == 0:
        for i in range(left, right+1):
            result.append(matrix[top][i])
        top += 1
        direction = 1
    elif direction == 1:
        for i in range(top, bottom+1):
            result.append(matrix[i][right])
        right -= 1
        direction = 2
    elif direction == 2:
        for i in range(right, left-1, -1):
            result.append(matrix[bottom][i])
        bottom -= 1
        direction = 3
    else:
        for i in range(bottom, top-1, -1):
            result.append(matrix[i][left])
        left += 1
        direction = 0
        
return result

Time Complexity: O(m*n), where m is the number of rows and n is the number of columns.

Space Complexity: O(1), as we are not using any extra space.

Thus, we have successfully solved the Spiral Matrix problem on Leetcode.

1