Java | 2ms 100% O(max_dist^2) | Equal distance diamond patterns | No sorting | Explanation
This code will usually run in 3ms, but about ⅓ of my submits will run in 2ms.Update 2025:  If you want to see my updated solution with this approach, plus 3 oth
This code will usually run in 3ms, but about &frac13; of my submits will run in 2ms.

*Update 2025:*  If you want to see my updated solution with this approach, plus 3 other approaches, with more formalized explations and analyses, with all approaches having sample code in Java, C++, and Python, then see my [updated post here](https://leetcode.com/problems/matrix-cells-in-distance-order/solutions/6432773/c-java-python3-4-approaches-sort-counting-sort-bfs-contour/).  But the code in this post is faster.

Cells at equal distance from the start point r0,c0 will form concentric nested diamond-shaped paths of cells in the matrix, as seen in the diagram below.  This code follows the four sides of these diamond-shaped paths, adding valid cells' row and column to the result.  Then move to the next outward diamond-shape path which will have a distance value of one more than the previous inner diamond-shape path.  

In the diagram below, the digits within the grid represent the distance of each cell from the r0,c0 start cell.  The colored diamond-shapes are paths through cells of equal distance.  Some of the larger diamond-shaped paths are not shown in the diagram because the full pattern became too hard on my eyes.

![image](https://assets.leetcode.com/users/images/830204ae-859d-47d7-8ab9-cd66c2e172e4_1619242807.8858745.png)


The order for processing the sides of the diamond-shapes, and the direction of processing the side, is listed below as a series of paths between vertices of a diamond-shape:
1. top to left
2. left to bottom
3. bottom to right
4. right to top

Each side of the diamond-shaped path has its own section within the code below.

Please upvote if useful.
```java []
class Solution {
    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
        int[][] result = new int[R * C][];
        result[0] = new int[] {r0, c0};            // Add start point r0,c0 which has distance 0.
        int resultIdx = 1;
        int lim = Math.max( r0, R-r0-1 ) + Math.max( c0, C-c0-1 );
		                                           // lim is highest distance value.
        for (int dist = 1; dist <= lim; dist++) {  // Process 'lim' diamond-shapes having distance 'dist'.
            int r = r0 - dist;
            int c = c0;
            // Diamond side: Top Left
            for (int count = dist; count > 0; count--) {    
                if (r >= 0 && c >= 0)  result[resultIdx++] = new int[] {r, c};
                r++;
                c--;
            }
            
            // Diamond side: Left Bottom
            for (int count = dist; count > 0; count--) {
                if (r < R && c >= 0)  result[resultIdx++] = new int[] {r, c};
                r++;
                c++;
            }
            
            // Diamond side: Bottom Right
            for (int count = dist; count > 0; count--) {
                if (r < R && c < C)  result[resultIdx++] = new int[] {r, c};
                r--;
                c++;
            }
            
            // Diamond side: Right Top
            for (int count = dist; count > 0; count--) {
                if (r >= 0 && c < C)  result[resultIdx++] = new int[] {r, c};
                r--;
                c--;
            }
        }
        return result;
    }
}
```
['Java']