Python3 Solution | Beats 96.01% | Explain Step by Step
Intuition

Use a dictionary distance_dict to record distance.


Sort distance_dict according to keys -> sorted_dict.


Use sorted_dict to return the final answe
# Intuition
1. Use a dictionary `distance_dict` to record distance.

2. Sort `distance_dict` according to keys -> `sorted_dict`.

3. Use `sorted_dict` to return the final answer `ans`.

# Approach
# **1. Fill `distance_dict` while iterating matrix.**

 - Initialize an empty dictionary `distance_dict`.   

```python3 []
distance_dict = {}
```
 - Iterate through the matrix and calculate the distance.

```python3 []
for r in range(rows):
    for c in range(cols):
        distance = abs(r - rCenter) + abs(c - cCenter)
```

- Update `distance_dict`:

```python3 []
        if distance in distance_dict:
            distance_dict[distance].append([r, c])
        else:
            distance_dict[distance] = [[r, c]]
```
# **2. Sort the distance_dict**
- Sort the dict by key (by distance) in non-decreasing order.

# **3. Return the final answer**

```python3 []
ans = []
for value in sorted_dict.values():
    ans.extend(value)
return ans
```


# Complexity
- Time complexity: $$O(n^2)$$, iterate through every grid of the matrix.

- Space complexity: $$O(n)$$, the cost of the dictionary.

# Code
```python3 []
import math

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:

        # Fill distance_dict while iterating matrix
        # Key represents the distance
        # Value represents the list including all cells that have the same distance
        distance_dict = {}
        for r in range(rows):
            for c in range(cols):
                distance = abs(r - rCenter) + abs(c - cCenter)
                if distance in distance_dict:
                    distance_dict[distance].append([r, c])
                else:
                    distance_dict[distance] = [[r, c]]
        
        # Sort the distance_dict
        sorted_keys = sorted(distance_dict.keys())
        sorted_dict = {x: distance_dict[x] for x in sorted_keys}

        # Use sorted_dict to return the final answer
        ans = []
        for value in sorted_dict.values():
            ans.extend(value)
        return ans
```
['Sorting', 'Matrix', 'Python3']