What is the main pattern used in Matrix Cells in Distance Order?

The primary pattern is array generation combined with math to calculate Manhattan distances for sorting.

Can I return cells with the same distance in any order?

Yes, any order among cells with the same distance is acceptable as long as the distance order is maintained.

What is the time complexity for this approach?

Time complexity is O(rows*cols*log(rows*cols)) due to sorting all matrix cells by distance.

Is there a more efficient method than sorting all coordinates?

Yes, a bucket sort by distance can avoid comparison-based sorting, especially when rows and cols are large.

What common mistakes occur with this problem?

Mistakes include using Euclidean distance instead of Manhattan distance and manually layering cells unnecessarily.

#1030

Easy

auto_awesome数组·数学

LeetCode 题解工作台

距离顺序排列矩阵单元格

给定四个整数 rows , cols , rCenter 和 cCenter 。有一个 rows x cols 的矩阵，你在单元格上的坐标是 (rCenter, cCenter) 。返回矩阵中的所有单元格的坐标，并按与 (rCenter, cCenter) 的距离从最小到最大的顺序排。你可以按…

数组数学几何排序矩阵

题目描述

给定四个整数 rows , cols , rCenter 和 cCenter 。有一个 rows x cols 的矩阵，你在单元格上的坐标是 (rCenter, cCenter) 。

返回矩阵中的所有单元格的坐标，并按与 (rCenter, cCenter) 的距离从最小到最大的顺序排。你可以按任何满足此条件的顺序返回答案。

单元格(r1, c1) 和 (r2, c2) 之间的距离为|r1 - r2| + |c1 - c2|。

示例 1：

输入：rows = 1, cols = 2, rCenter = 0, cCenter = 0
输出：[[0,0],[0,1]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1]

示例 2：

输入：rows = 2, cols = 2, rCenter = 0, cCenter = 1
输出：[[0,1],[0,0],[1,1],[1,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]
[[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。

示例 3：

输入：rows = 2, cols = 3, rCenter = 1, cCenter = 2
输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]
其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。

提示：

1 <= rows, cols <= 100
0 <= rCenter < rows
0 <= cCenter < cols

lightbulb

解题思路

方法一：BFS

我们定义一个队列 $q$ ，初始时将坐标点 $(rCenter, cCenter)$ 入队，用一个二维布尔数组 $vis$ 记录已经访问过的点，初始时 $vis[rCenter][cCenter]$ 为 $true$ 。

接下来，我们不断地从队列中取出一个点，将其加入答案数组，然后将其上下左右四个相邻点加入队列，注意要判断这些点是否已经访问过，如果没有访问过，就将其标记为已访问，并将其加入队列。一直重复这个过程，直到队列为空，此时答案数组中的点就是按照距离从小到大的顺序排列的。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def allCellsDistOrder(
        self, rows: int, cols: int, rCenter: int, cCenter: int
    ) -> List[List[int]]:
        q = deque([[rCenter, cCenter]])
        vis = [[False] * cols for _ in range(rows)]
        vis[rCenter][cCenter] = True
        ans = []
        while q:
            for _ in range(len(q)):
                p = q.popleft()
                ans.append(p)
                for a, b in pairwise((-1, 0, 1, 0, -1)):
                    x, y = p[0] + a, p[1] + b
                    if 0 <= x < rows and 0 <= y < cols and not vis[x][y]:
                        vis[x][y] = True
                        q.append([x, y])
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(rows _cols_ log(rows _cols)) due to sorting all cells by distance. Space complexity is O(rows_ cols) to store all coordinates and their distances before returning.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
You quickly identify the Manhattan distance formula.
question_mark
You recognize the matrix is small enough for direct enumeration.
question_mark
You propose sorting coordinates by computed distance without missing cells.

warning

常见陷阱

外企场景

error
Forgetting that ties in distance can be returned in any order, causing unnecessary constraints.
error
Computing Euclidean distance instead of Manhattan distance.
error
Attempting to traverse the matrix in layers manually, which is more complex than needed.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return cells in spiral order around the center.
arrow_right_alt
Compute distances from multiple centers and merge results.
arrow_right_alt
Handle very large matrices efficiently using bucket sort by distance.

help

常见问题

外企场景

继续练习

#973 最接近原点的 K 个点 #939 最小面积矩形 #892 三维形体的表面积