#59

Medium

LeetCode Problem Workspace

Spiral Matrix II

Generate a spiral matrix of size n x n, filled with elements from 1 to n² in spiral order, for interview-focused solving.

array matrix simulation

Problem Statement

Given a positive integer n, your task is to generate an n x n matrix filled with integers from 1 to n² in a spiral order. The matrix must begin by filling the top-left corner, then proceed right, down, left, and up in a spiral until all cells are filled.

For example, for n = 3, the correct output would be [[1, 2, 3], [8, 9, 4], [7, 6, 5]]. For n = 1, the output would be [[1]].

Examples

Example 1

Input: n = 3

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

Example details omitted.

Example 2

Input: n = 1

Output: [[1]]

Example details omitted.

Constraints

1 <= n <= 20

Solution Approach

Simulate Spiral Traversal

Start from the top-left corner of the matrix and fill numbers from 1 to n². Move in a right, down, left, and up pattern while adjusting the boundaries to avoid overwriting already filled cells.

Boundary Adjustments

After filling each row or column, adjust the boundaries (top, bottom, left, right) to prevent revisiting cells. These adjustments are key to maintaining the correct spiral order.

Efficient Space Usage

Use an in-place matrix filling approach to minimize space complexity. The matrix is filled row by row, and column by column, within a pre-allocated n x n array.

Complexity Analysis

Metric	Value
Time	\mathcal{O}(n^2)
Space	\mathcal{O}(1)

The time complexity is O(n²) due to the need to visit every cell in the n x n matrix exactly once. The space complexity is O(1) as we are using an in-place filling strategy.

What Interviewers Usually Probe

The candidate demonstrates an understanding of array traversal techniques.
They can describe how to adjust matrix boundaries during traversal.
They understand how to optimize for space complexity with an in-place solution.

Common Pitfalls or Variants

Common pitfalls

Forgetting to adjust the boundaries after completing a row or column, causing an infinite loop or overwriting cells.
Not properly handling edge cases, like n = 1 or a very small matrix.
Overcomplicating the solution by using extra space when in-place filling is possible.

Follow-up variants

Generate the matrix in reverse spiral order, starting from n² and going down to 1.
Create a matrix that is filled in a diagonal pattern from top-left to bottom-right.
Simulate the matrix traversal in a zigzag pattern, filling values in a back-and-forth manner.

FAQ

What is the time complexity of Spiral Matrix II?

The time complexity is O(n²) since each element in the n x n matrix must be visited once.

How can I handle the matrix boundaries during traversal?

Adjust the boundaries (top, bottom, left, right) after completing each row or column to prevent overwriting or revisiting cells.

Can I use extra space for the matrix in this problem?

The problem specifies an in-place solution, meaning no extra space should be used apart from the matrix itself.

What happens if n = 1?

For n = 1, the matrix is simply [[1]]. The solution still works correctly with this edge case.

How does the spiral pattern work in this problem?

The pattern starts from the top-left corner and moves right, down, left, and up in a continuous loop, filling numbers in this order until the matrix is complete.

terminal

Solution

Solution 1: Simulation

We can directly simulate the process of generating the spiral matrix.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        ans = [[0] * n for _ in range(n)]
        dirs = (0, 1, 0, -1, 0)
        i = j = k = 0
        for v in range(1, n * n + 1):
            ans[i][j] = v
            x, y = i + dirs[k], j + dirs[k + 1]
            if x < 0 or x >= n or y < 0 or y >= n or ans[x][y]:
                k = (k + 1) % 4
            i, j = i + dirs[k], j + dirs[k + 1]
        return ans

Continue Practicing

#54 spiral matrix #289 game of life #498 diagonal traverse