Problem Statement in English

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

Approach

Brute Force Approach

We can reuse the code from 54. Spiral Matrix to generate a spiral matrix of size n x n.

Instead of reading values from an existing matrix, we will fill the matrix with increasing integers starting from 1.

Optimized Approach with Constant Space

We can optimize the space complexity by using a single loop to fill the matrix in spiral order, without needing to store the visited positions.

We maintain pointers for the top, bottom, left, and right boundaries of the matrix that we need to fill next. Next we fill the matrix in layers, moving inward after completing each layer.

And we’re done!

Solution in Python

  • Brute Force Approach $O(n^2)$ Space

class Solution:
    def generateMatrix(self, n: int) -> list[list[int]]:
        matrix = [[0] * n for _ in range(n)]
        seen = set()

        x, y = 0, 0
        counter = 1

        moves = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        move_index = 0

        while len(seen) < n * n:
            if (x, y) not in seen:
                matrix[x][y] = counter
                counter += 1
                seen.add((x, y))

            nx = x + moves[move_index][0]
            ny = y + moves[move_index][1]

            if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in seen:
                x, y = nx, ny
            else:
                move_index += 1
                move_index %= 4

        return matrix
  • Optimized Approach $O(1)$ Space

class Solution:
    def generateMatrix(self, n: int) -> list[list[int]]:
        matrix = [[0] * n for _ in range(n)]
        
        top, bottom = 0, n - 1
        left, right = 0, n - 1
        counter = 1

        while top <= bottom and left <= right:
            # Fill top row (left to right)
            for col in range(left, right + 1):
                matrix[top][col] = counter
                counter += 1
            top += 1

            # Fill right column (top to bottom)
            for row in range(top, bottom + 1):
                matrix[row][right] = counter
                counter += 1
            right -= 1

            # Fill bottom row (right to left)
            for col in range(right, left - 1, -1):
                matrix[bottom][col] = counter
                counter += 1
            bottom -= 1

            # Fill left column (bottom to top)
            for row in range(bottom, top - 1, -1):
                matrix[row][left] = counter
                counter += 1
            left += 1

        return matrix

Mistakes I Made

The constant space solution didn’t occur to me.

And we are done.