# 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:

```python
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

| Item | Meaning |
|---|---|
| Input | `rows`, `cols`, `rCenter`, `cCenter` |
| Output | All `[r, c]` cells sorted by Manhattan distance from center |

Function shape:

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

## Examples

Example 1:

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

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

Answer:

```python
[[0,0],[0,1]]
```

Example 2:

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

Cells sorted by distance from `(0,1)`:

| Cell | Distance |
|---|---:|
| `[0,1]` | 0 |
| `[0,0]` | 1 |
| `[1,1]` | 1 |
| `[1,0]` | 2 |

Answer:

```python
[[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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m * n * log(m * n))` | Generating and sorting all cells |
| Space | `O(m * n)` | Storing all cells |

## 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

```python
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

```python
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()
```

| Test | Verification | Why |
|---|---|---|
| `1x2` grid | Exact match | Unique order |
| `2x2` grid | Distances are non-decreasing | Ties can be in any order |