🔃54. Spiral Matrix

Medium | Grind 75 | March 3rd Friday, 2023

Given an m x n matrix, return all elements of the matrix in spiral order.

Constraints:

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 10

• -100 <= matrix[i][j] <= 100

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

SOLUTION

Notice that the spiral pattern in this code follows a clockwise movement, starting from the top left of the input matrix. With this in mind, we can break down the solution into 4 simple steps.

Firstly, we declare four variables to represent the four positions required to traverse the matrix:

• top: representing the topmost unprocessed row.

• bottom: representing the bottommost unprocessed row.

• right: representing the rightmost unprocessed column.

• left: representing the leftmost unprocessed column.

We also initialize an empty list, called "result," to store the elements as we process them.

Step 1: Since we always start from the top left and move right until we read all the elements in the top row, we iterate over the top row, appending each element to our "result" list. Once we have processed every element in the top row, we decrement the top variable since we don't need to return to this row.

Step 2: The second step is to move from the top right to the bottom right. We set the column index to right since we need to process the rightmost column elements while iterating through the rows from top to bottom. Once every element from the rightmost column is processed, we decrement the right variable since we have processed all elements in that column.

Step 3: The third step involves processing elements from every column of the last row. To do this, we iterate through the columns from right to left, using bottom as the row index. Once we have processed every element in the bottom row, we decrement the bottom variable.

Step 4: The final step is to iterate over the leftmost column, moving our row index from bottom to top by decrementing by 1 while keeping the column index as left. Once this is finished, we increment the left variable by 1.

We repeat this process until we have processed every element in the grid. We know we have processed every element in the grid when right is smaller than the left or top is larger than bottom.

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        left, right = 0, len(matrix[0])-1
        top, bottom = 0, len(matrix)-1

        result = []
        step = 0

        while left <= right and top <= bottom: 
            step = step % 4

            if step == 0: 
                for i in range(left, right+1): 
                    result.append(matrix[top][i])
                top += 1
            
            if step == 1: 
                for i in range(top, bottom+1): 
                    result.append(matrix[i][right])
                right -= 1
            
            if step == 2: 
                for i in range(right, left-1, -1): 
                    result.append(matrix[bottom][i])
                bottom -= 1
            
            if step == 3: 
                for i in range(bottom, top-1, -1): 
                    result.append(matrix[i][left])
                left += 1
        
            step += 1
        
        return result 

TIME AND SPACE COMPLEXITY

TIME: O(n*m) where n is the number of rows and m is the number of columns in the matrix.

SPACE: O(n*m) the result variable is a one-dimensional list of size n*m where n and m are the width and height of the grid respectively.

**written with help from ChatGPT