Spiral Matrix II

Simulation Array

Problem

Given a positive integer n, generate a square matrix filled with elements from 1 to $n^2$ in spiral order.

For example:

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

Thought Process

• How would we go about changing the directions when filling the 2D matrix?

  • Have a variable d for the direction and updating this variable whenever we "shave" off a row or column.

• How would we generate the numbers to fill the 2D matrix from 1 to $n^2$.

  • Have a varaible called num initially set 1, incrementing this variable at each cell, and filling each cell with the variable.

Solution

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        
        matrix = [[0 for j in range(n)] for i in range(n)]
        d = 0
        num = 1
        top, bottom = 0, len(matrix)-1
        left,right = 0, len(matrix[0])-1
        
        while top<=bottom and left<=right:
            if d == 0:
                for j in range(left,right+1):
                    matrix[top][j] = num
                    num+=1
                top+=1
                d+=1
            elif d == 1:
                for i in range(top, bottom+1):
                    matrix[i][right] = num
                    num+=1
                right-=1
                d+=1
            elif d == 2:
                for j in range(right, left-1,-1):
                    matrix[bottom][j] = num
                    num+=1
                bottom-=1
                d+=1
            elif d == 3:
                for i in range(bottom, top-1,-1):
                    matrix[i][left] = num
                    num+=1
                left+=1
                d = 0
        return matrix
        

Key Facts

• The direction and boundary variables are most important

• For updating the number, just have a num variable and increment by 1 in the for-loops

• With each direction, there is either a constant row or column (i.e. when doing in the down direction, the constant is the right column.)

Time Complexity

Time: O($n^2$) because we have to fill every row and column

Space: O($n^2$) because we are initilizing a matrix and storing the numbers here.