Problem Statement & Formal Constraints

You are given four integers rows, cols, rCenter, and cCenter. There is a rows x cols matrix and you are on the cell with coordinates (rCenter, cCenter).

Return the coordinates of all cells in the matrix, sorted by their distance from (rCenter, cCenter) from smallest distance to 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 the Manhattan distance: |r1 - r2| + |c1 - c2|.

Algorithmic Intuition & Mathematical Properties

The Manhattan distance (also known as the $L_1$ norm or Taxicab distance) represents the shortest path length between two coordinates on a strict grid where only horizontal and vertical movements are permitted. Visually, all cells sharing an identical Manhattan distance $k$ from (rCenter, cCenter) form the perimeter of a diamond centered on the starting cell.

The maximum possible distance from any coordinate in the grid is bounded by:

max_dist = max(rCenter, rows - 1 - rCenter) + max(cCenter, cols - 1 - cCenter);

Because the maximum distance is at most $ ext{rows} + ext{cols} le 200$, the key observation is that sorting keys fall into a remarkably small integer range, unlocking linear-time non-comparative sorting algorithms.

Approach 1: Multi-Directional Breadth-First Search (BFS)

Because BFS visits graph vertices in strictly non-decreasing order of edge distance in an unweighted graph, treating the matrix as an unweighted 4-directional grid allows us to discover cells in naturally distance-ordered tiers without requiring explicit sorting.

Here is the C++ implementation utilizing an iterative queue and boolean visited matrix:

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        queue<pair<int,int>> q;        
        vector<vector<int>> result;
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));        
        const vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        q.push({rCenter, cCenter});
        visited[rCenter][cCenter] = true;

        while (!q.empty()) {
            auto [currentRow, currentCol] = q.front();              
            result.push_back({currentRow, currentCol});
            q.pop();

            for (auto [dr, dc] : directions) {
                int newRow = currentRow + dr;
                int newCol = currentCol + dc;

                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols 
                    && !visited[newRow][newCol]) {                        
                    q.push({newRow, newCol});
                    visited[newRow][newCol] = true;
                }
            }
        }
        return result;
    }
};

Approach 2: Modern TypeScript Production Implementation (Bucket Sort)

In full-stack web and Node.js environments, allocating small objects inside a queue can trigger garbage collection churn. By leveraging Bucket Sort, we achieve optimal $O(R imes C)$ time complexity while minimizing heap allocations:

/**
 * Optimal O(Rows * Cols) Bucket Sort Implementation in TypeScript
 */
export function allCellsDistOrder(
  rows: number, 
  cols: number, 
  rCenter: number, 
  cCenter: number
): number[][] {
  const maxDistance = Math.max(rCenter, rows - 1 - rCenter) + Math.max(cCenter, cols - 1 - cCenter);
  const buckets: number[][][] = Array.from({ length: maxDistance + 1 }, () => []);

  // 1. Distribute each coordinate into its corresponding Manhattan distance bucket
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      const dist = Math.abs(r - rCenter) + Math.abs(c - cCenter);
      buckets[dist].push([r, c]);
    }
  }

  // 2. Flatten buckets sequentially from distance 0 to maxDistance
  const result: number[][] = [];
  for (let d = 0; d <= maxDistance; d++) {
    const bucket = buckets[d];
    for (let i = 0; i < bucket.length; i++) {
      result.push(bucket[i]);
    }
  }

  return result;
}

Complexity Evaluation Matrix (Time vs. Space)

The table below summarizes the algorithmic tradeoffs across different implementations:

Real-World Software Engineering Applications

Distance-ordered matrix traversal algorithms appear frequently in production systems:

• 2D Canvas & Game Viewport Culling: Prioritizing tile rendering around the player's viewport camera coordinates, ensuring visible foreground geometry loads before background terrain.
• Geospatial Spatial Indexing: Querying nearby database entities across discrete grid partitions (e.g., geohash buckets or QuadTree leaves).
• UI Ripple Animation Effects: Calculating staggered CSS animation delay properties across dynamic UI grid components emanating outwards from a user's click coordinate.

Frequently Asked Questions

Why is Bucket Sort faster than standard Array.prototype.sort() for this problem?

Comparison-based sorting algorithms (like TimSort in V8 or IntroSort in C++ std::sort) are mathematically bounded by $Omega(N log N)$ comparisons. In LeetCode 1030, because the maximum distance is at most $rows + cols le 200$, bucket sort distributes elements into bounded arrays in a single linear pass $O(N)$, bypassing comparison overhead entirely.

Can BFS visit the same cell multiple times if visited flags are omitted?

Yes. Because each cell has up to four neighbors, omitting the visited matrix causes exponential vertex queuing ($4^k$), rapidly triggering an Out-Of-Memory (OOM) crash. Always mark cells visited immediately upon pushing them to the queue.

Does Manhattan distance differ from Euclidean distance in practical grid traversal?

Manhattan distance ($|x_1 - x_2| + |y_1 - y_2|$) measures movement restricted to 90-degree grid axes, while Euclidean distance ($sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$) measures straight-line displacement. In discrete tile-based engines without diagonal movement, Manhattan distance is computationally cheaper and reflects true path length.

How can memory allocation be reduced in memory-constrained environments?

Instead of allocating arrays of arrays [[r, c]], flatten coordinates into a single Int32Array where index 2*i stores the row and 2*i + 1 stores the column, drastically reducing garbage collector overhead in V8.

Conclusion & Performance Takeaways

LeetCode 1030 exemplifies how mathematical domain constraints transform an apparently quadratic problem into an elegant linear-time algorithm. By analyzing the maximum distance bound and selecting Bucket Sort or BFS, software engineers achieve optimal performance and predictable memory footprints.