0054 Spiral Matrix

0054 Spiral Matrix#

Problem#

Given an m x n matrix, return all elements of the matrix in spiral order.

Examples#

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints#

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

Analysis#

  • define 4 boundaries

  • traverse along the boundary clockwise until reach out of bounds

  • shrink the bounds

Solution#

def spiralOrder(matrix):
    m, n = len(matrix), len(matrix[0])
    l, r, u, d = 0, n-1, 0, m-1

    res = []
    while u <= d and l <= r:
        # move along upper boud from left to right
        for i in range(l, r+1):
            res.append(matrix[u][i])
        u += 1    
        
        # move along right bound from up to down
        for j in range(u, d+1):
            res.append(matrix[j][r])
        r -= 1

        # move along lower bound from right to left 
        if u <= d: # avoid traverse again 
            for i in range(r, l-1, -1):
                res.append(matrix[d][i])
            d -= 1

        # move along left bound from down to up
        if l <= r:
            for j in range(d, u-1, -1):
                res.append(matrix[j][l])
            l += 1

    return res

# test
matrix = [[1,2,3],[4,5,6],[7,8,9]]
print(spiralOrder(matrix))

matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
print(spiralOrder(matrix))

matrix = [[1,2,3,4,5]]
print(spiralOrder(matrix))

matrix = [[1], [2], [3], [4], [5]]
print(spiralOrder(matrix))

[1, 2, 3, 6, 9, 8, 7, 4, 5]
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
Contents