# Matrix Cells in Distance Order
**Difficulty:** EASY
[External](https://leetcode.com/problems/matrix-cells-in-distance-order)
Canonical: https://scaleengineer.com/dsa/problems/matrix-cells-in-distance-order
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Matrix
---
## Problem
You are given four integers `row`, `cols`, `rCenter`, and `cCenter`. There is a `rows x cols` matrix and you are on the cell with the coordinates `(rCenter, cCenter)`.

Return _the coordinates of all cells in the matrix, sorted by their **distance** from_ `(rCenter, cCenter)` _from the smallest distance to the largest distance_. You may return the answer in **any order** that satisfies this condition.

The **distance** between two cells `(r1, c1)` and `(r2, c2)` is `|r1 - r2| + |c1 - c2|`.

**Example 1:**

**Input:** rows = 1, cols = 2, rCenter = 0, cCenter = 0
**Output:** [[0,0],[0,1]]
**Explanation:** 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]]
**Explanation:** 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]]
**Explanation:** 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`

# Approaches
## Brute Force with Sorting
This approach is the most straightforward and brute-force way to solve the problem. It involves two main steps. First, we generate all possible coordinates within the `rows x cols` matrix and store them in a list. Second, we sort this list based on a custom criterion, which is the Manhattan distance of each cell from the given center `(rCenter, cCenter)`. The cells are sorted in ascending order of this distance.
**Time:** O(N log N), where N = rows * cols. Populating the list of cells takes O(N) time. The dominant operation is sorting the N cells, which has an average and worst-case time complexity of O(N log N) for comparison-based sorts. · **Space:** O(N) or O(log N), where N = rows * cols. This space is required for storing all the cell coordinates and for the space used by the sorting algorithm. The output array itself requires O(N) space. The auxiliary space for sorting in Java's `Arrays.sort` is O(log N) for primitives and O(N) for objects in the worst case.
**Pros:** Easy to understand and implement.; Leverages powerful, highly-optimized built-in sorting functions.
**Cons:** The time complexity of `O(N log N)` is suboptimal compared to linear time solutions.; For very large matrices, the performance degradation will be noticeable.
### Explanation
The core of this method is to first gather all the data points (the cell coordinates) and then apply a standard sorting algorithm. We can create a 2D array `result` of size `(rows * cols) x 2` and populate it with all the cell coordinates. Then, we use `Arrays.sort()` with a custom `Comparator`. The comparator takes two coordinate arrays, `a` and `b`, calculates their respective Manhattan distances from `(rCenter, cCenter)`, and returns the difference. This effectively sorts the entire array based on the distance from the center.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        int[][] result = new int[rows * cols][2];
        int index = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                result[index++] = new int[]{i, j};
            }
        }

        // Sort using a custom comparator (lambda expression for brevity)
        Arrays.sort(result, (a, b) -> {
            int distA = Math.abs(a[0] - rCenter) + Math.abs(a[1] - cCenter);
            int distB = Math.abs(b[0] - rCenter) + Math.abs(b[1] - cCenter);
            return distA - distB;
        });

        return result;
    }
}
```
### Algorithm
- Create a list or an array to hold all `rows * cols` coordinates.
- Use nested loops to iterate through each row `i` from `0` to `rows-1` and each column `j` from `0` to `cols-1`, adding the coordinate `[i, j]` to your list.
- Use a built-in sort function on the list of coordinates.
- Provide a custom comparator to the sort function. This comparator will calculate the Manhattan distance for any two cells `a` and `b` from the center `(rCenter, cCenter)` and order them based on the difference in their distances.
- The Manhattan distance for a cell `(r, c)` is `|r - rCenter| + |c - cCenter|`.
- Convert the sorted list back to a 2D array and return it.

## Bucket Sort
A more efficient approach is to use Bucket Sort, as the sorting keys (the distances) are integers with a limited range. Instead of comparing each cell with every other cell, we can group them by their distance from the center. We create a set of 'buckets', where each bucket corresponds to a specific distance. We iterate through the matrix, calculate the distance for each cell, and place it in the correct bucket. Finally, we concatenate the buckets in order, from distance 0 upwards, to get the final sorted list.
**Time:** O(N), where N = rows * cols. We iterate through all N cells once to place them into buckets (O(N)). We then iterate through the buckets to build the result array. Since there are N cells in total across all buckets, this second step also takes O(N). The total time is O(N). · **Space:** O(N), where N = rows * cols. The `buckets` data structure needs to store all N cells, and the final `result` array also takes O(N) space.
**Pros:** Optimal time complexity of O(N).; Conceptually simple for those familiar with non-comparison sorts.
**Cons:** Requires extra space for the buckets, which can be large depending on the maximum distance.; It's a two-pass algorithm: one pass to distribute cells into buckets and a second pass to collect them.
### Explanation
This method avoids a comparison-based sort by taking advantage of the data's properties. The distances are integers, so we can use them as indices in an array. We create an array of lists, where the index `d` holds a list of all cells at distance `d` from the center. We make one pass over the entire grid to populate these buckets. Then, we make a second pass over the bucket array itself, from index 0 to `maxDist`, collecting all the cells into our final result array. This process sorts the cells in linear time.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        int maxDist = Math.max(rCenter, rows - 1 - rCenter) + Math.max(cCenter, cols - 1 - cCenter);
        List<List<int[]>> buckets = new ArrayList<>();
        for (int i = 0; i <= maxDist; i++) {
            buckets.add(new ArrayList<>());
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int dist = Math.abs(i - rCenter) + Math.abs(j - cCenter);
                buckets.get(dist).add(new int[]{i, j});
            }
        }

        int[][] result = new int[rows * cols][2];
        int index = 0;
        for (int i = 0; i <= maxDist; i++) {
            for (int[] cell : buckets.get(i)) {
                result[index++] = cell;
            }
        }
        return result;
    }
}
```
### Algorithm
- First, calculate the maximum possible Manhattan distance from the center to any cell in the grid. `maxDist = max(rCenter, rows - 1 - rCenter) + max(cCenter, cols - 1 - cCenter)`.
- Create a list of lists (or an array of lists) called `buckets`, with a size of `maxDist + 1`.
- Iterate through every cell `(r, c)` in the matrix.
- For each cell, calculate its distance `d = |r - rCenter| + |c - cCenter|`.
- Add the coordinate `[r, c]` to the list at `buckets.get(d)`.
- After all cells are placed in their respective distance buckets, create a final result array.
- Iterate through the `buckets` from index `0` to `maxDist`. For each distance, append all cells from that bucket to the result array.
- Return the populated result array.

## Breadth-First Search (BFS)
The most efficient and idiomatic approach for this type of problem is to use Breadth-First Search (BFS). We can view the matrix as a graph where each cell is a node. A BFS, by its nature, explores a graph layer by layer from a starting source. In our case, the source is `(rCenter, cCenter)`. The first layer of exploration contains cells at distance 1, the second layer contains cells at distance 2, and so on. This perfectly matches the problem's requirement to order cells by their distance.
**Time:** O(N), where N = rows * cols. Each cell is enqueued and dequeued exactly once. For each cell, we perform a constant amount of work (checking its four neighbors). Thus, the runtime is linear with respect to the number of cells. · **Space:** O(N), where N = rows * cols. The `visited` array requires O(N) space. The queue's maximum size is proportional to the perimeter of the largest diamond shape, which is O(rows + cols). The space is dominated by the `visited` array.
**Pros:** Optimal time complexity of O(N).; Generates the result in a single pass over the grid cells.; It's a very natural and common pattern for shortest-path problems on unweighted grids.
**Cons:** Requires auxiliary space for both the queue and the `visited` array.
### Explanation
We start the BFS by putting the center cell `(rCenter, cCenter)` into a queue. We also use a `visited` matrix to ensure we process each cell only once. In a loop, we dequeue a cell, add it to our result list, and then enqueue all its valid, unvisited neighbors. A valid neighbor is one that is within the matrix bounds. Because BFS explores level by level, we are guaranteed to add cells to our result list in increasing order of their Manhattan distance from the center.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        boolean[][] visited = new boolean[rows][cols];
        int[][] result = new int[rows * cols][2];
        int index = 0;
        Queue<int[]> queue = new LinkedList<>();
        
        queue.offer(new int[]{rCenter, cCenter});
        visited[rCenter][cCenter] = true;
        
        int[] dr = {0, 0, 1, -1}; // Direction vectors for row changes
        int[] dc = {1, -1, 0, 0}; // Direction vectors for col changes

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            result[index++] = cell;
            
            for (int i = 0; i < 4; i++) {
                int newR = cell[0] + dr[i];
                int newC = cell[1] + dc[i];
                
                if (newR >= 0 && newR < rows && newC >= 0 && newC < cols && !visited[newR][newC]) {
                    visited[newR][newC] = true;
                    queue.offer(new int[]{newR, newC});
                }
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Initialize a queue and add the starting cell `[rCenter, cCenter]`.
- Create a 2D boolean array `visited` of size `rows x cols` to track visited cells. Mark the starting cell as visited.
- Create the `result` array of size `rows * cols` and an `index` to populate it.
- While the queue is not empty:
  - Dequeue a cell, let's say `currentCell`.
  - Add `currentCell` to the `result` array at the current `index`.
  - Explore the four neighbors of `currentCell` (up, down, left, right).
  - For each neighbor, if it is within the grid boundaries and has not been visited:
    - Enqueue the neighbor.
    - Mark the neighbor as visited.
- Once the queue is empty, all cells have been visited in distance order, and the `result` array is fully populated. Return it.

# Solutions
### Java

```java
import java.util.Deque ; class Solution { public int [][] allCellsDistOrder ( int rows , int cols , int rCenter , int cCenter ) { Deque < int []> q = new ArrayDeque <>(); q . offer ( new int [] { rCenter , cCenter }); boolean [][] vis = new boolean [ rows ][ cols ]; vis [ rCenter ][ cCenter ] = true ; int [][] ans = new int [ rows * cols ][ 2 ]; int [] dirs = {- 1 , 0 , 1 , 0 , - 1 }; int idx = 0 ; while (! q . isEmpty ()) { for ( int n = q . size (); n > 0 ; -- n ) { var p = q . poll (); ans [ idx ++] = p ; for ( int k = 0 ; k < 4 ; ++ k ) { int x = p [ 0 ] + dirs [ k ], y = p [ 1 ] + dirs [ k + 1 ]; if ( x >= 0 && x < rows && y >= 0 && y < cols && ! vis [ x ][ y ]) { vis [ x ][ y ] = true ; q . offer ( new int [] { x , y }); } } } } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter,
                                        int cCenter) {
    queue<pair<int, int>> q;
    q.emplace(rCenter, cCenter);
    vector<vector<int>> ans;
    bool vis[rows][cols];
    memset(vis, false, sizeof(vis));
    vis[rCenter][cCenter] = true;
    int dirs[5] = {-1, 0, 1, 0, -1};
    while (!q.empty()) {
      for (int n = q.size(); n; --n) {
        auto [i, j] = q.front();
        q.pop();
        ans.push_back({i, j});
        for (int k = 0; k < 4; ++k) {
          int x = i + dirs[k];
          int y = j + dirs[k + 1];
          if (x >= 0 && x < rows && y >= 0 && y < cols && !vis[x][y]) {
            vis[x][y] = true;
            q.emplace(x, y);
          }
        }
      }
    }
    return ans;
  }
};

```

### Python

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

```