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