Matrix Cells in Distance Order

easy matrix manhattan distance sorting

Problem

You are given four integers rows, cols, rCenter, and cCenter. There is a grid of size rows × cols and you start at the cell (rCenter, cCenter). Return the coordinates of all cells in the grid, sorted by their Manhattan distance from (rCenter, cCenter), from smallest to largest. The Manhattan distance between (r1, c1) and (r2, c2) is |r1 − r2| + |c1 − c2|. You may return the answer in any order that satisfies this constraint.

Inputrows = 2, cols = 3, rCenter = 1, cCenter = 2

Output[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]

Distances from (1,2) are 0, 1, 1, 2, 2, 3 — any ordering with non-decreasing distance is accepted.

rows

cols

rCenter

cCenter

def all_cells_dist_order(rows, cols, r_center, c_center):
    cells = []
    for r in range(rows):
        for c in range(cols):
            cells.append([r, c])
    cells.sort(key=lambda p: abs(p[0] - r_center) + abs(p[1] - c_center))
    return cells

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

class Solution {
    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        int[][] cells = new int[rows * cols][2];
        int idx = 0;
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                cells[idx++] = new int[]{ r, c };
        Arrays.sort(cells, (a, b) ->
            (Math.abs(a[0] - rCenter) + Math.abs(a[1] - cCenter)) -
            (Math.abs(b[0] - rCenter) + Math.abs(b[1] - cCenter)));
        return cells;
    }
}

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++)
            cells.push_back({ r, c });
    sort(cells.begin(), cells.end(), [&](auto& a, auto& b) {
        return abs(a[0] - rCenter) + abs(a[1] - cCenter) <
               abs(b[0] - rCenter) + abs(b[1] - cCenter);
    });
    return cells;
}

Explanation

We need every cell of the grid listed in order of how far it is from a center cell. The cleanest approach is to list all the cells first, then sort them by distance.

The double loop over r and c simply visits each cell and appends its [r, c] coordinates to cells, so we end up with the whole grid in a flat list.

Then we sort that list using the Manhattan distance as the key: abs(r - r_center) + abs(c - c_center). This is the number of horizontal plus vertical steps to reach the center, and sorting by it puts the closest cells first.

Example: for a 2x3 grid centered at (1,2), the center itself has distance 0, its neighbors have distance 1, and the far corner (0,0) has distance 3. After sorting we get an order like [[1,2],[0,2],[1,1],...].

Any ties (cells with the same distance) can come in any order, which is exactly what the problem allows, so a plain sort is enough.

Time: O(rows · cols · log(rows · cols)) Space: O(rows · cols)