A straightforward O(mn) python solution without the mutating the matrix, 44ms


  • 0
    C

    Ideas:

    1. use two pointers for row (i and iend) and columns (j and jend).
    2. use turn to record the number of while loop so that turn%4 indicates what direction it should be in this loop.

    In this solution, every element would be visited exactly once (O(mn)) and this solution does not mutate the matrix. (many shared solutions on OJ use matrix.pop(), which would mutate the matrix )

        def spiralOrder(self, matrix):
            if not matrix:
                return []
            i, iend , j, jend = 0, len(matrix)-1, 0, len(matrix[0])-1
            ans, turn = [], 0
            while i <= iend and j <= jend:
                if turn%4 == 0: # left to right
                    ans += matrix[i][j:jend+1]
                    i += 1
                elif turn%4 == 1: # top to bottom
                    ans += [matrix[k][jend] for k in xrange(i, iend+1)]
                    jend -=1
                elif turn%4 == 2: # right to left
                    ans += matrix[iend][j:jend+1][::-1]
                    iend -=1
                elif turn%4 == 3: # bottom to top
                    ans += [matrix[k][j] for k in xrange(iend, i-1,-1)]
                    j += 1
                turn += 1
            return ans
    

Log in to reply
 

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