Python solution using dictionary to encode movement (can invert easily)


  • 0
    L

    '''
    class Solution(object):
    def spiralOrder(self, matrix):
    """
    :type matrix: List[List[int]]
    :rtype: List[int]
    """

        # get dimension
        m = len(matrix)
        if m == 0:
            return []
        n = len(matrix[0])
        if n == 0:
            return []
        
        # init movement dict
        delta_dict = {
            # current_direction: [step, next_direction]
            'right': [[0,1],  'down'], 
            'down':  [[1,0],  'left'],
            'left':  [[0,-1], 'up'],
            'up':    [[-1,0], 'right']
            }
            
        # init vars
        delta_key = 'right'
        count = 0
        minI, minJ = 0,0
        maxI, maxJ = m-1, n-1
        i,j = 0,0
        res = []
        
        # add 1st value
        res.append(matrix[i][j])
        count += 1
        
        # start loop, break when return all numbers
        while count < m*n:
            
            # get stop boundary for this movement
            if delta_key == 'right':
                maxj = maxJ
            elif delta_key == 'left':
                minj = minJ
            elif delta_key == 'down':
                maxi = maxI
            elif delta_key == 'up':
                mini = minI
                
            # get movement step and direction for next
            delta, next_delta_key = delta_dict[delta_key]
            
            while True:
                # move a step
                i,j = i+delta[0], j+delta[1]
                
                # check boundary
                if delta_key == 'right' and j > maxj:
                    minI += 1
                    break
                elif delta_key == 'left' and j < minj:
                    maxI -= 1
                    break
                elif delta_key == 'down' and i > maxi:
                    maxJ -= 1
                    break
                elif delta_key == 'up' and i < mini:
                    minJ += 1
                    break
                
                # add current value
                res.append(matrix[i][j])
                print "add %i: , count %i" % (matrix[i][j], count)
                count += 1
                
            # void the last invalid move
            i,j = i-delta[0], j-delta[1]
                   
            # next direction
            delta_key = next_delta_key
            
        return res
    

    '''


Log in to reply
 

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