0059 Spiral Matrix II

0059 Spiral Matrix II#

Problem#

Given a positive integer n, generate an n x n matrix filled with elements from 1 to \(n^2\) in spiral order.

Examples#

Example 1:

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

Example 2:

Input: n = 1
Output: [[1]]

Constraints#

1 <= n <= 20

Analysis#

  • define 4 boundaries

  • traverse along the boundary clockwise until reach out of bounds

  • shrink the bounds

Solution#

def spiralOrder(n):
    
    l, r, u, d = 0, n-1, 0, n-1
    nums = list(range(n*n, 0, -1))
    matrix = [[0 for _ in range(n)] for _ in range(n)]

    while nums:
        # traverse upper bound from left to right
        if u <= d:
            for i in range(l, r+1):
                ele = nums.pop()
                matrix[u][i] = ele 
            u += 1
        # traverse right bound from upper to down
        if l <= r:
            for j in range(u, d+1):
                ele = nums.pop()
                matrix[j][r] = ele 
            r -= 1
        # traverse down bound from right to left
        if u <= d:
            for i in range(r, l-1, -1):
                ele = nums.pop()
                matrix[d][i] = ele 
            d -= 1
        # traverse left bound from down to up
        if l <= r:
            for j in range(d, u-1, -1):
                ele = nums.pop()
                matrix[j][l] = ele 
            l += 1
    
    return matrix

# test
n = 1
print(spiralOrder(n))

n = 3
print(spiralOrder(n))

n = 4
print(spiralOrder(n))

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