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.

#59

Medium

auto_awesome数组·matrix

LeetCode 题解工作台

螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n 2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。示例 1：输入： n = 3 输出： [[1,2,3],[8,9,4],[7,6,5]] 示例 2：输入： n = 1 输出： [[1]] 提示： 1

数组矩阵模拟

题目描述

给你一个正整数 n ，生成一个包含 1 到 n² 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

1 <= n <= 20

lightbulb

解题思路

方法一：模拟

我们可以直接模拟螺旋矩阵的生成过程。

定义一个二维数组 $\textit{ans}$ ，用于存储螺旋矩阵。用 $i$ 和 $j$ 分别表示当前位置的行号和列号，用 $k$ 表示当前的方向编号， $\textit{dirs}$ 表示方向编号与方向的对应关系。

从 $1$ 开始，依次填入矩阵中的每个位置。每次填入一个位置后，计算下一个位置的行号和列号，如果下一个位置不在矩阵中或者已经被填过，则改变方向，再计算下一个位置的行号和列号。

时间复杂度 $O(n^2)$ ，其中 $n$ 是矩阵的边长。忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

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

speed

复杂度分析

指标	值
时间	\mathcal{O}(n^2)
空间	\mathcal{O}(1)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#54 螺旋矩阵 #289 生命游戏 #498 对角线遍历