Leetcode 54: Spiral Matrix

spiral_order.py

"""
Problem: Given a 2D array of integers, create a spiral_copy function 
that copies the input matrix's values into a 1D array in spiral order, 
clockwise. The function should return only that array and analyze the 
time/space complexities after you have a solution.

Solution: Return a 1D spiral copy of the input matrix.

Approach: 
1. Extract the width and height of the input matrix into separate variables
2. Iterate through the matrix in a spiral fashion...
  a. The iteration will change direction as we progress and hit width and height
     boundaries.
    - Use "row" and "column" variables to access the matrix.
  b. How do we know when to switch iteration (cardinal) direction?
    - First (NW -> NE): increment only the column index: inputMatrix[0][0..width - 1]
    - Second (NE -> SE): increment only the row index: inputMatrix[1..height - 1][width - 1]
    - Third (SE -> SW): decrement only the column index: inputMatrix[height - 1][width - 1..0]
    - Fourth (SW -> NW - 1): decrement only the row index: inputMatrix[height - 1..1][0]
  c. While we iterate, push each value into the output array.
  d. Use four boundary "walls" to ensure the row and column variables progress in a spiral:
    - North: start at 0 and increment after each NW -> NE traversal.
    - East: start at (width - 1) and decrement after each NE -> SE traversal.
    - South: start at (height - 1) and decrement after each SE -> SW traversal.
    - West: start at 0 and increment after each SW -> NW traversal.
  e. The iteration stopping condition is when both pairs of parallel walls have 
     "collided", i.e., (north == south) and (west == east).


input: matrix = [ [1,   2,  3, 4,   5],
                  [6,   7,  8, 9,  10],
                  [11, 12, 13, 14, 15],
                  [16, 17, 18, 19, 20] ]

output: [1, 2, 3, 4, 5, 10, 15, 20, 19, 18, 17, 16, 11, 6, 7, 8, 9, 14, 13, 12]

"""

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # initialize output list
        result = []
        
        # extract width, height
        width, height = len(matrix[0]), len(matrix)
        
        # initialize the walls, one per cardinal direction
        north, east, south, west = 0, (width - 1), (height - 1), 0
        
        # iterate through the matrix in a spiral fashion, pushing each value 
        # into the result list along the way
        while north != south and west != east:
            # traverse NW -> NE (rightwards)
            for column in range(west, east + 1):
                result.append(matrix[north][column])
            north += 1
                
            # traverse NE -> SE (downwards)
            for row in range(north, south + 1):
                result.append(matrix[row][east])
            east -= 1
                
            # traverse SE -> SW (leftwards)
            for column in range(east, west - 1, -1):
                result.append(matrix[south][column])
            south -= 1
                
            # traverse SW -> NW (upwards)
            for row in range(south, north - 1, -1):
                result.append(matrix[row][west])
            west += 1
            
        return result