Straight-forward O(n) recursive Python solution


  • 0
    R
    class Solution(object):
        def spiralOrder(self, matrix):
            if not matrix:
                return []
            rows = len(matrix)
            cols = len(matrix[0])
            
            return self.traverse_left(matrix = matrix, 
                                      left_bound = 0, 
                                      right_bound = cols,
                                      upper_bound = 0,
                                      lower_bound = rows)
            
        # inclusive of left_bound, upper_bound
        # exclusive of right_bound, lower_bound
        def traverse_left(self, matrix, left_bound, right_bound, upper_bound, lower_bound):
            if right_bound - left_bound <= 0:
                return []
            return matrix[upper_bound][left_bound:right_bound] + self.traverse_down(
                matrix = matrix, 
                left_bound = left_bound,
                right_bound = right_bound, 
                upper_bound = upper_bound + 1,
                lower_bound = lower_bound
            )
    
        def traverse_down(self, matrix, left_bound, right_bound, upper_bound, lower_bound):
            if lower_bound - upper_bound <= 0:
                return []
            return [matrix[r][right_bound-1] for r in range(upper_bound, lower_bound)] + self.traverse_right(
                matrix = matrix, 
                left_bound = left_bound,
                right_bound = right_bound - 1, 
                upper_bound = upper_bound,
                lower_bound = lower_bound
            )
    
        def traverse_right(self, matrix, left_bound, right_bound, upper_bound, lower_bound):
            if right_bound - left_bound <= 0:
                return []
            return list(reversed(matrix[lower_bound-1][left_bound:right_bound])) + self.traverse_up(
                matrix = matrix, 
                left_bound = left_bound,
                right_bound = right_bound, 
                upper_bound = upper_bound,
                lower_bound = lower_bound - 1
            )
    
        def traverse_up(self, matrix, left_bound, right_bound, upper_bound, lower_bound):
            if lower_bound - upper_bound <= 0:
                return []
            return [matrix[r][left_bound] for r in range(lower_bound -1, upper_bound-1, -1)] + self.traverse_left(
                matrix = matrix, 
                left_bound = left_bound + 1,
                right_bound = right_bound, 
                upper_bound = upper_bound,
                lower_bound = lower_bound
            )
    

Log in to reply
 

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