LeetCode 1030: Matrix Cells in Distance Order

Problem Restatement

We are given an rows x cols matrix and a center cell (rCenter, cCenter).

We need to return all cells of the matrix sorted by their distance from the center, where distance is defined as:

abs(r - rCenter) + abs(c - cCenter)

(Manhattan distance).

Ties can be broken in any order.

The official constraints state that 1 <= rows, cols <= 100 and 0 <= rCenter < rows, 0 <= cCenter < cols.

Input and Output

Function shape:

def allCellsDistOrder(rows: int, cols: int, rCenter: int, cCenter: int) -> list[list[int]]:
    ...

Examples

Example 1:

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

Cells: [0,0] (distance 0), [0,1] (distance 1).

Answer:

[[0,0],[0,1]]

Example 2:

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

Cells sorted by distance from (0,1):

Answer:

[[0,1],[0,0],[1,1],[1,0]]

Key Insight

Simply collect all cells and sort by Manhattan distance. The matrix is small enough (at most 100 x 100 = 10000 cells) that this is efficient.

Alternatively, use BFS from the center to enumerate cells in distance order.

Algorithm

1. Generate all cells [r, c] for 0 <= r < rows and 0 <= c < cols.
2. Sort by abs(r - rCenter) + abs(c - cCenter).
3. Return the sorted list.

Correctness

Sorting by the exact Manhattan distance formula correctly orders all cells. Ties are broken arbitrarily.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> list[list[int]]:
        cells = [[r, c] for r in range(rows) for c in range(cols)]
        cells.sort(key=lambda cell: abs(cell[0] - rCenter) + abs(cell[1] - cCenter))
        return cells

Testing

def run_tests():
    s = Solution()

    assert s.allCellsDistOrder(1, 2, 0, 0) == [[0, 0], [0, 1]]
    result = s.allCellsDistOrder(2, 2, 0, 1)
    dists = [abs(r - 0) + abs(c - 1) for r, c in result]
    assert dists == sorted(dists)

    print("all tests passed")

run_tests()