Python Simulation Without Extra Space (Beats 90%)


  • 0
    Z

    In many of the simulation solutions, we iterate through the matrix cell by cell, and maintaining an extra same-size boolean matrix to keep track of cells we've already seen. Here I propose a simulation method without using extra space.

    The idea is simple: maintaining top, down, left, right 4 paddings. During simulation, the padding expands as we finish a whole row or whole column. Once there is no way to go, we finish simulation. Here is the code:

    def spiralOrder(self, matrix):
    
        ans = []
        if matrix == [[]] or matrix == []:
            return ans
        nrow = len(matrix)
        ncol = len(matrix[0])
        top, down, left, right = 0, 0, 0, 0
        x, y = 0, 0
        d = 1 # 1 right, 2 left, 3 down, 4 up
        
        while True:
            if d == 1 and y < ncol - right - 1:
                ans.append(matrix[x][y])
                y += 1
            elif d == 1 and y == ncol - right - 1:
                ans.append(matrix[x][y])
                right += 1
                if x + 1 == nrow - down:
                    break
                d = 3
                ans.pop()
            
            if d == 3 and x < nrow - down - 1:
                ans.append(matrix[x][y])
                x += 1
            elif d == 3 and x == nrow - down - 1:
                ans.append(matrix[x][y])
                down += 1
                if y == left:
                    break
                d = 2
                ans.pop()
            
            if d == 2 and y > left:
                ans.append(matrix[x][y])
                y -= 1
            elif d == 2 and y == left:
                ans.append(matrix[x][y])
                left += 1
                if x - 1 == top:
                    break
                d = 4
                ans.pop()
            
            if d == 4 and x > top + 1:
                ans.append(matrix[x][y])
                x -= 1
            elif d == 4 and x == top + 1:
                ans.append(matrix[x][y])
                top += 1
                if y + 1 == ncol - right:
                    break
                d = 1
                ans.pop()
                
        return ans

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.