59. Spiral Matrix II

Spiral Matrix II - LeetCode

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

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

  • code
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        if n == 1: return [[1]]
        res = [[0] * n for _ in range(n)]
        direction = {'right':(0, 1), 'left':(0, -1), 'up': (-1, 0), 'down': (1, 0)}
        
        def walk(x, y, d, value):
            if res[x][y] != 0: return
            res[x][y] = value
            dx, dy = direction[d]
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and res[nx][ny] == 0:
                walk(nx, ny, d, value + 1)
            else:
                if d == 'right': walk(x+1, y, 'down', value + 1)
                elif d == 'down': walk(x, y-1, 'left', value + 1)
                elif d == 'left': walk(x-1, y, 'up', value + 1)
                elif d == 'up': walk(x, y+1, 'right', value + 1)
        
        walk(0, 0, 'right', 1)
        return res
  • code
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        direction = [[0,1],[1,0],[0,-1],[-1,0]]
        v = 1
        d = 0
        res = [[0] * n for _ in range(n)]
        i = j = 0
        while v <= n * n:
            res[i][j] = v
            v += 1
            ni, nj = i + direction[d][0], j + direction[d][1]
            if 0 <= ni < n and 0 <= nj < n and res[ni][nj] == 0:
                i, j = ni, nj
            else:
                d = (d + 1) % 4
                i, j = i + direction[d][0], j + direction[d][1]
        return res