0054-spiral-matrix¶

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        #   matrix = [[1,2,3],[4,5,6],[7,8,9]]
        #  
        #  1 2 3  6 9  8 7 4 5
        #  
        #  1 ... n**2
        #  direction_r= 0 direction_c = 1
        # viisted = {}
        #  r = 0 c= 0 
        #   r < m c < n add 1
        #  r =0 c = 1 
        #         1 < 3 add 2
        # r= 0 c = 2
        #          add 3
        # r = 0     c =3 
        #     c +1 < 3 ; f 
        #       direction_r = 1 direction_c = 0
        #  r =  0 ,1,2
        #    r + 1 < 3
        #      direction_r = 0 direction_c = -1
        #  c = 2 1 0
        #     direction_r = -1 direction_c = 0
        #  r = 2 1 
        #      direction_r = 0 direction_c = 1

        #  1 2 
        #  3 4  r =0 c =0 ; res = [1]
        #       r = 0 c =1; res = [ 1 2]
        #     change direction 
        #       r = 1 c = 1 res = [12 4]
        #     change direction
        #     r = 1 c= 0 res =[ 1 2 4 3]
        #  0 1 , 1 0, -1, 0, 0, -1
        #  colmun change 
        # m = len(matrix)
        # n = len(matrix[0])

        # res = [0] * (m*n)
        # directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        # i = 0
        # r,c = 0,0
        # direction = 0
        # while i < len(res):
        #     res[i] = matrix[r][c]


        #     dr, dc = directions[direction]
        #     nr, nc = r + dr, c + dc
        #     # Change direction if next cell is invalid
        #     if (
        #         nr < 0 or nr >= m or
        #         nc < 0 or nc >= n or
        #         (nr, nc) in visited
        #     ):
        #         direction = (direction + 1) % 4
        #         dr, dc = directions[direction]
        #         nr, nc = r + dr, c + dc

        #     r, c = nr, nc
        #     i+=1
        # return res

        # goal to create spira pattern
        # need correct r,c indexes
        # invariant -> boundary
        #  when we reachthe boundary update the boundar
        # left = 0 right = m up = 0 and down = n
        #    
        #    left - > right 
        #    right -> down
        #    right -> left 
        #    left -> up
        #   left += 1
        #   right -= 1
        #   up += 1
        #   down -= 1

        m = len(matrix)
        n = len(matrix[0])

        left = 0
        right = n  - 1
        up = 0
        down = m - 1
        res = []
        while len(res) < (m*n):
            for col in range(left, right + 1):
                res.append(matrix[up][col])
            
            for row in range(up+1, down + 1):
                res.append(matrix[row][col])

            
                    # Make sure we are now on a different row.
            if up != down:
                # Traverse from right to left.
                for col in range(right - 1, left - 1, -1):
                    res.append(matrix[down][col])

            # Make sure we are now on a different column.
            if left != right:
                # Traverse upwards.
                for row in range(down - 1, up, -1):
                    res.append(matrix[row][left])
            left += 1
            right -= 1
            up += 1
            down -= 1

        return res