[LeetCode] Spiral Matrix

 

 

Problem

 

 

---

 

Solution

 

We can change the direction to right(1,0), down(0,1), left(0,-1) and up(0,-1), and rotating in that order. Set these pairs of movements into a list so that they can be easily accessed in the right order.

The code should keep printing until it meets one of two conditions:

1. The row number of column number goes out of boundaries of the matrix
2. The position has already been visited

Checking for the first condition is easy. Update the row and column number with the movement list and see if the updated numbers are not within the boundaries.

For the second condition, make a double array of the same size as matrix that keeps track of all visited numbers. Everytime the row and column are updated, check if the visited matrix in that position is True. If so, change direction. If not, set it to True and update row and column again.

 

This process should be repeated until the count of numbers is equal to the size of the matrix.

 

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        visited = [[False] * len(matrix[0]) for _ in range(len(matrix))]
        directions = [(0,1), (1,0), (0,-1), (-1,0)]
        result = []
        
        visited[0][0] = True
        direction = 0
        col = 0
        row = 0
        change_direction = 0
        
        result.append(matrix[0][0])
        counted = 1
        
        while counted < len(matrix)*len(matrix[0]):
        
            while True:
                next_row = row + directions[direction][0]
                next_col = col + directions[direction][1]

                if not(0<=next_row<len(matrix) and 0<=next_col<len(matrix[0])):
                    break
                if visited[next_row][next_col] == True:
                    break

                row = next_row
                col = next_col
                visited[row][col] = True
                result.append(matrix[row][col])
                counted += 1

            direction = (direction + 1) % 4
        
        return result