Matrix Cells in Distance Order
Easy · Matrix · Array · Math · Geometry · Sorting · Matrix
Problem
A grid has rows rows and cols columns, and (rCenter, cCenter) is one of its cells. The Manhattan distance between cells (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|.
Return every cell of the grid as an [r, c] pair, ordered by distance to the center, nearest first. Cells at the same distance are listed by row, and cells in the same row by column, both in increasing order.
Examples
Input: rows = 1, cols = 3, rCenter = 0, cCenter = 1 Output: [[0,1],[0,0],[0,2]]
The center is at distance 0; both neighbors are at distance 1 and are listed by column.
Input: rows = 2, cols = 2, rCenter = 1, cCenter = 1 Output: [[1,1],[0,1],[1,0],[0,0]]
Distance 0: [1,1]. Distance 1: [0,1] (row 0) before [1,0] (row 1). Distance 2: [0,0].
Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2 Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
Distance 1 holds [0,2] and [1,1]; distance 2 holds [0,1] and [1,0]; [0,0] is farthest at 3.
Constraints
- 1 <= rows, cols <= 100
- 0 <= rCenter < rows
- 0 <= cCenter < cols
Approaches
- Sort every cell by (distance, row, column) — time O(R · C · log(R · C)), space O(R · C)
Follow-up
What if only the cells within distance d are wanted? Walk the diamond directly: for each row r with |r - rCenter| <= d, the columns run from cCenter - (d - |r - rCenter|) to cCenter + (d - |r - rCenter|), clipped to the grid. That costs only the size of the output.
Related problems
Start free on Cariara · Coding problems · System design studio
