5/25/2020

[LeetCode] 54. Spiral Matrix

Problem : https://leetcode.com/problems/spiral-matrix/

Use FSM to simulate the process of iterating element and put the visited element to result array.
Stop iterating when result array size equals to the matrix size. 

Remember to handle the edge case when input matrix is empty.

Time Complexity : O ( M * N )
Space Complexity: O ( M * N )

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        nextPos = {'right': (0, 1), 'down': (1, 0), 'left': (0, -1), 'up': (-1, 0)}
        nextDir = {'right': 'down', 'down': 'left', 'left': 'up', 'up': 'right'}
        
        y, x = 0, -1
        direction = 'right'
        
        result = []
        visited = defaultdict(bool)
        
        while len(result) < ROW * COLUMN:
            ny, nx = y + nextPos[direction][0], x + nextPos[direction][1]
            
            if 0 <= ny < ROW and 0 <= nx < COLUMN and not visited[ny,nx]:
                visited[ny, nx] = True
                result.append(matrix[ny][nx])
                y, x = ny, nx
            else:
                direction = nextDir[direction]
            
        return result

Edited on 09/16/2021. Refactor by using dictionary to save next position to move forward and next direction when need to make a turn.

No comments:

Post a Comment