Simple Python solution by mutating the matrix

  • 36

    The con is mutating the matrix, if this is not allowed, we can make a deep copy of the matrix first. And of course it comes with the additional memory usage.

    def spiralOrder(self, matrix):
        ret = []
        while matrix:
            ret += matrix.pop(0)
            if matrix and matrix[0]:
                for row in matrix:
            if matrix:
                ret += matrix.pop()[::-1]
            if matrix and matrix[0]:
                for row in matrix[::-1]:
        return ret

  • 0

    really a smart idea!

  • 0

    Interesting idea, but the running time will be larger than O(mn), since the last case, which is

            for row in matrix[::-1]:

    needs O(mn) for each stage and there are O(min(m, n)) stages.

    Of course, you may use collections.deque to remedy that.

  • 0

    neat solution without using recursion

  • 0
    This post is deleted!

  • 0

    python solution without using recursion too.

    def spiralOrder(self, matrix):
            if len(matrix) == 0: return []
            M, N, result = len(matrix), len(matrix[0]), []
            CN = min(M, N)/2
            for i in xrange(CN):
                result += matrix[i][i:~i]
                result += [arow[~i] for arow in matrix[i:~i]]
                result += matrix[~i][::-1][i:~i]
                result += [arow[i] for arow in matrix[::-1][i:~i]]
            if M > N and N % 2 == 1: result += [arow[N/2] for arow in matrix[CN:M-CN]]
            elif N >= M and M % 2 == 1: result += matrix[M/2][CN:N-CN]
            return result

  • 1


  • 0

    @tju_xu97 what does ~ mean?

  • 0

    smart solution!

  • 0

    @ChuntaoLu It is a good idea, very well in use python feature, thank you

  • 0

    @Zura You can check the post on SO
    Basically, it's a neat way to represent index like len(n)-1

  • 0

    My solution with comments:

    class Solution(object):
        def spiralOrder(self, matrix):
            :type matrix: List[List[int]]
            :rtype: List[int]
            output_list = []
            if not matrix or len(matrix[0]) < 1:
                return output_list
            current_item, starting_row_index, ending_row_index = 0, 0, len(matrix)  # -1 because of length vs index
            starting_column_index, ending_column_index = 0, len(matrix[0])  # -1 because of length vs index
            while starting_row_index < ending_row_index and starting_column_index < ending_column_index:
                # Print the first row of the remaining rows, the size of the row is from first column to last column
                for current_item in range(starting_column_index, ending_column_index):
                    output_list.append(matrix[starting_row_index][current_item])  # Appends horizontally
                starting_row_index += 1  # we change up the starting row index so that it is one higher
                # Print last column of the remaining columns
                for current_item in range(starting_row_index, ending_row_index):
                    output_list.append(matrix[current_item][ending_column_index - 1])
                ending_column_index -= 1  # we reduce the size of he ending columns
                # Print the last row of the remaining rows
                if starting_row_index < ending_row_index:
                    for current_item in range(ending_column_index - 1, starting_column_index - 1, -1):
                        output_list.append(matrix[ending_row_index - 1][current_item])
                    ending_row_index -= 1  # Reduce the number of the ending row index
                # Print the first column of the remaining columns
                if starting_column_index < ending_column_index:
                    for current_item in range(ending_row_index - 1, starting_row_index - 1, -1):
                    starting_column_index += 1
            return output_list
    solution = Solution()

Log in to reply

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