54. Spiral Matrix

• python3

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]

Constraints:

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

Pseudocode

1. First, create the array for checking if a location has been visited.
2. Set up a directions array to determin the next move.
3. Move step by step.
4. Return the result Array.

Code

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        
        m = len(matrix)
        n = len(matrix[0])
        r = 0
        c = 0
        # visited array
        visited = [[False for j in range(n)]for i in range(m)]
        # result array
        result = [0] * (m * n)

        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # right, down, left, up
        direction = 0

        for i in range(0, len(result)):
            result[i] = matrix[r][c]
            visited[r][c] = True
            
            next_r, next_c = r + directions[direction][0], c + directions[direction][1]

            if 0 <= next_r < m and 0 <= next_c < n and not visited[next_r][next_c]:
                    r, c = next_r, next_c
            else:
                direction = (direction + 1) % 4
                r, c = r + directions[direction][0], c + directions[direction][1]
        return result

Result

• Time Complexity:O(m*n)
• Space Complexity: O(m*n)