mattlevan · April 20, 2020 18:52
diff --git a/spiral_order.py b/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
	"""
	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