SA
Skip to main content

0059 Spiral Matrix II

Solved at: 2023-02-09

Question

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

Solution

class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
row = 0
col = 0
incrementing = True
changingRow = False
grid = [[-1 for _ in range(n)] for _ in range(n)]
for i in range(n ** 2):
# print(i, grid)
# print(row, col, incrementing, changingRow)
if row >= n or row < 0 or col >= n or col < 0:
continue
grid[row][col] = i + 1

if changingRow and incrementing:
if row + 1 >= n or grid[row + 1][col] != -1:
changingRow = False
incrementing = False
elif changingRow and not incrementing:
if row - 1 < 0 or grid[row - 1][col] != -1:
changingRow = False
incrementing = True
elif not changingRow and incrementing:
if col + 1 >= n or grid[row][col + 1] != -1:
changingRow = True
elif not changingRow and not incrementing:
if col - 1 < 0 or grid[row][col - 1] != -1:
changingRow = True
incrementing = False

if changingRow and incrementing:
row += 1
elif changingRow and not incrementing:
row -= 1
elif not changingRow and incrementing:
col += 1
elif not changingRow and not incrementing:
col -= 1
return grid

Results

  • Runtime 25 ms, Beats 97.6%
  • Memory 14 MB, Beats 32.65%

Complexity Analysis

Time O(N2)O(N^2) Space O(1)O(1)