#1030

Easy

LeetCode Problem Workspace

Matrix Cells in Distance Order

Compute all matrix cell coordinates sorted by Manhattan distance from a given center using array and math techniques efficiently.

array math geometry sorting matrix

Problem Statement

Given a matrix of size rows x cols and a center cell (rCenter, cCenter), return all cell coordinates sorted by their Manhattan distance from the center. The distance between two cells (r1,c1) and (r2,c2) is |r1-r2| + |c1-c2|.

Implement a function that outputs the coordinates as an array of arrays. The order must start from the smallest distance to the largest. Any ordering that preserves distance sorting is valid, and the function should handle matrices up to 100 x 100 efficiently.

Examples

Example 1

Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0

Output: [[0,0],[0,1]]

The distances from (0, 0) to other cells are: [0,1]

Example 2

Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1

Output: [[0,1],[0,0],[1,1],[1,0]]

The distances from (0, 1) to other cells are: [0,1,1,2] The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.

Example 3

Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2

Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]

The distances from (1, 2) to other cells are: [0,1,1,2,2,3] There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].

Constraints

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

Solution Approach

Generate all coordinates

Iterate through all rows and columns to build a list of [row, col] pairs. This ensures you have every matrix cell to calculate distances.

Compute Manhattan distances

For each cell [r, c], calculate the Manhattan distance to the center as |r - rCenter| + |c - cCenter|. Store the distance along with the coordinate for sorting.

Sort by distance

Sort the list of coordinates based on the computed distances. Return only the coordinates, dropping distance values. Any tie-breaking order among equal distances is valid.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

Continue Practicing

#973 k closest points to origin #939 minimum area rectangle #892 surface area of 3d shapes