Spiral Matrix I

Simulation Array

Problem

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Thought Process:

• How do we know when we reach the end of one of the inner arrays inside the matrix?

  • By setting boundaries for top, bottom, left, and right. We update the boundaries when a row or column is complete.

• How do we know when to go down, left, right, or up?

  • By having a variable representing the direction to go in. d = 0 (right), d = 1 (down), d = 2 (left), d = 3 (up)

• How do we know when we reach the end of the spiral?

  • We have an outer while loop checking the boundaries. When the top boundary has passed the bottom boundary and when the left boundary has passed the right boundary, the loop will break.

Solution

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if len(matrix) == 0:
            return []
        d = 0
        top,bottom = 0, len(matrix)-1
        left,right = 0, len(matrix[0])-1
        soln = []
        
        while top <= bottom and left <= right:
            if d == 0:
                for j in range(left, right+1):
                    soln.append(matrix[top][j])
                top+=1
                d+=1
            elif d == 1:
                for i in range(top, bottom+1):
                    soln.append(matrix[i][right])
                right-=1
                d+=1
            elif d == 2:
                for j in range(right, left-1, -1):
                    soln.append(matrix[bottom][j])
                bottom-=1
                d+=1
            elif d == 3:
                for i in range(bottom, top-1,-1):
                    soln.append(matrix[i][left])
                left+=1
                d = 0
        return soln
                    
                
        

Key Facts

• The direction variable and boundary variables is what really helps solve this problem and are the main driving force for this solution.

• We are essentially "shaving off" each row and column.

Time Complexity

Time: O(n) because we are going through every number in the matrix

Space: O(n) for the single array we are storing our solution in