Leetcode - Spiral Matrix

Leetcode : Spiral Matrix

Description

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1

Input

matrix = [[1,2,3],[4,5,6],[7,8,9]]

Output

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

Example 2

Input

matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

Output

[1,2,3,4,8,12,11,10,9,5,6,7]

Approach

The spiral order goes in a direction of "Right -> Down -> Left -> Up" and repeats itself. Create variables i & j to track the size of height and width and cnt to traverse through every elements in matrix. Additionally create dictionary type dict to check whether the element was visited or not.

Solution (Python)

class Solution(object):
    def spiralOrder(self, matrix):
        if len(matrix) == 0 or matrix is None:
            return []
        
        h, w = len(matrix), len(matrix[0])
        i, j = 0, 0 
        cnt = 0 
        
        ans = []
        dict = {}
        
        dir = 'right'
        
        while cnt < h * w:
            ans = ans + [matrix[i][j]]
            dict[matrix[i][j]] = True
            cnt = cnt + 1
            
            if dir == 'right':
                if j == w - 1 or matrix[i][j+1] in dict:
                    dir = 'down'
                    i = i + 1
                else:
                    j = j + 1
            elif dir == 'down':
                if i == h - 1 or matrix[i+1][j] in dict:
                    dir = 'left'
                    j = j - 1
                else:
                    i = i + 1
            elif dir == 'left':
                if j == 0 or matrix[i][j-1] in dict:
                    dir = 'up'
                    i = i - 1
                else:
                    j = j - 1
            else:
                if i == 0 or matrix[i-1][j] in dict:
                    dir = 'right'
                    j = j + 1
                else:
                    i = i - 1
                    
        return ans 
                    

Result

Runtime : 20ms
Memory Usage : 13.4MB
Runtime Beats 46.32% of Python Submission