Description:
Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Example:
Input: 3
Output:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
Solution:
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
result = []
for i in range(n):
result.append([0]*n)
shift = {
(0,1):((1,0),(0,1)),
(1,0):((0,-1),(3,-1)),
(0,-1):((-1,0),(1,-1)),
(-1,0):((0,1),(2,1))
}
wall = [-1,n,-1,n] # top bottom left right
row,col = 0,0
direction = (0,1)
for i in range(1,n*n+1):
# print(row,col,i)
result[row][col] = i
row += direction[0]
col += direction[1]
if row in wall[:2] or col in wall[2:]:
row -= direction[0]
col -= direction[1]
direction,(i,j) = shift[direction]
row += direction[0]
col += direction[1]
wall[i] += j
return result
Performance:
- Runtime: 36 ms, faster than 86.61% of Python3 online submissions for Spiral Matrix II.
- Memory Usage: 13.2 MB, less than 30.65% of Python3 online submissions for Spiral Matrix II.
