Code Implementation

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int):
        cells = []
        for r in range(rows):
            for c in range(cols):
                dist = abs(r - rCenter) + abs(c - cCenter)
                cells.append([r, c, dist])
        cells.sort(key=lambda x: x[2])
        return [[r, c] for r, c, _ in cells]
      

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        vector<vector<int>> cells;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                int dist = abs(r - rCenter) + abs(c - cCenter);
                cells.push_back({r, c, dist});
            }
        }
        sort(cells.begin(), cells.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[2] < b[2];
        });
        vector<vector<int>> result;
        for (auto& v : cells) result.push_back({v[0], v[1]});
        return result;
    }
};
      

class Solution {
    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        List<int[]> cells = new ArrayList<>();
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                int dist = Math.abs(r - rCenter) + Math.abs(c - cCenter);
                cells.add(new int[]{r, c, dist});
            }
        }
        cells.sort((a, b) -> Integer.compare(a[2], b[2]));
        int[][] result = new int[cells.size()][2];
        for (int i = 0; i < cells.size(); ++i) {
            result[i][0] = cells.get(i)[0];
            result[i][1] = cells.get(i)[1];
        }
        return result;
    }
}
      

var allCellsDistOrder = function(rows, cols, rCenter, cCenter) {
    let cells = [];
    for (let r = 0; r < rows; ++r) {
        for (let c = 0; c < cols; ++c) {
            let dist = Math.abs(r - rCenter) + Math.abs(c - cCenter);
            cells.push([r, c, dist]);
        }
    }
    cells.sort((a, b) => a[2] - b[2]);
    return cells.map(([r, c, _]) => [r, c]);
};
      

Problem Description

Given the dimensions of a matrix (rows x cols) and the coordinates (rCenter, cCenter) of a starting cell, return a list of all cell coordinates in the matrix, sorted by their Manhattan distance from the center cell. The Manhattan distance between two cells (r1, c1) and (r2, c2) is defined as |r1 - r2| + |c1 - c2|.

• Each cell in the matrix should appear exactly once in the output.
• Do not reuse or duplicate any cell.
• The result must be sorted in non-decreasing order of distance from the center cell.

Thought Process

At first glance, the problem seems to ask for a way to traverse a matrix such that we start from a given center and visit all other cells, sorted by how close they are to the center using Manhattan distance.

A brute-force method would be to:

• List all possible cells in the matrix.
• Calculate the distance of each cell to the center.
• Sort the cells by this distance.

We can consider optimizing by generating cells in order of increasing distance, possibly using a BFS (breadth-first search) approach, since BFS naturally visits cells in layers of increasing distance. However, because the matrix size is not huge and sorting is fast, the brute-force approach is often sufficient for this problem.

Solution Approach

Let's break down the steps to solve this problem:

1. Enumerate all cells:
   • Loop through every row and every column to get all cell coordinates (r, c) in the matrix.
2. Calculate Manhattan Distance:
   • For each cell, compute |r - rCenter| + |c - cCenter|, which tells us how far the cell is from the center.
3. Store and Sort:
   • Store each cell with its distance in a list or array.
   • Sort the list by distance.
4. Output:
   • Return the coordinates only, dropping the distance information.

Why this works: Sorting is efficient for the matrix sizes in this problem, and calculating the distance is O(1) per cell. This approach is simple, readable, and leverages built-in sort functions.

Alternative Approach: If we wanted to avoid sorting, we could use BFS starting from the center cell, marking cells as visited to ensure each cell is visited once, and collecting cells in the order we visit them. BFS would also guarantee the correct distance order.

Example Walkthrough

Suppose rows = 3, cols = 3, rCenter = 1, cCenter = 1.

The matrix is:
[ (0,0), (0,1), (0,2) ]
[ (1,0), (1,1), (1,2) ]
[ (2,0), (2,1), (2,2) ]

For each cell, calculate the Manhattan distance to (1,1):

• (0,0): |0-1| + |0-1| = 2
• (0,1): |0-1| + |1-1| = 1
• (0,2): |0-1| + |2-1| = 2
• (1,0): |1-1| + |0-1| = 1
• (1,1): |1-1| + |1-1| = 0
• (1,2): |1-1| + |2-1| = 1
• (2,0): |2-1| + |0-1| = 2
• (2,1): |2-1| + |1-1| = 1
• (2,2): |2-1| + |2-1| = 2

After sorting, the order is:

• (1,1) - distance 0
• (0,1), (1,0), (1,2), (2,1) - distance 1
• (0,0), (0,2), (2,0), (2,2) - distance 2

Time and Space Complexity

Brute-force Approach:

• Enumerating all cells: O(R * C), where R = rows, C = cols.
• Calculating distance: O(1) per cell, so total O(R * C).
• Sorting: O(N log N), where N = R * C (number of cells).
• Overall: O(R * C * log(R * C))
• Space: O(R * C) to store all cells and their distances.

• Visit each cell once: O(R * C).
• No sorting needed.
• Space: O(R * C) for the queue and visited set.
• Overall: O(R * C)

For most practical cases, the brute-force approach is fast and simple, but BFS is more optimal for very large matrices.

Summary

The problem asks us to list all matrix cells ordered by their Manhattan distance from a center cell. The direct solution is to enumerate all cells, compute their distance, and sort them. This approach is clear, easy to code, and efficient for typical constraints. For very large matrices, a BFS-based approach can avoid explicit sorting and provide further optimization. The key insight is leveraging the definition of Manhattan distance and recognizing that sorting or BFS both naturally produce the required order.