Matrix Cells in Distance Order — Editorial

Opening the reading…

Intuitiondistance layers turn the matrix into an ordered list

The required order depends only on each cell's Manhattan distance from the center. The center has distance 0, its horizontal and vertical neighbors have distance 1, and every farther cell belongs to a later distance layer. Cells in the same layer may appear in any order, so the problem only asks you to group cells by distance, not to break ties in a special way.

The direct implementation assigns no permanent distance array: it lists every coordinate, then compares two coordinates by their computed distances. Since every coordinate must appear exactly once, this separates the job into two safe steps: generate all cells and order that complete list. The distance is bounded by rows + cols - 2, which also makes a bucket-by-distance version possible.

Manhattan distance creates concentric diamond-shaped layers, clipped by the matrix edges.

Approach

Create an empty result list and append every coordinate (r, c) in the matrix, because skipping a cell during generation cannot be repaired by the later sort.

Sort the complete list with a comparator that computes abs(r - rCenter) + abs(c - cCenter) for each coordinate, because that expression is exactly the ordering rule from the problem.

Return the coordinate with the smaller distance first, because a comparator based on any other quantity would order the matrix by something unrelated to the required metric.

Allow equal distances to compare as neither smaller than the other, because the statement permits any order among cells in the same distance layer and the sorting comparator must remain consistent.

Keep the center and matrix dimensions captured by the comparator, because the sort callback needs the original reference point while it examines pairs of stored coordinates.

Return the sorted result after the single sort, because every matrix cell is already present and no filtering or second traversal is needed.

Complexitythe comparison sort counts the same cells without duplicating them

MEASURE	BOUND	WHY
Time	O(n log n)	Generating the list touches each of the n cells once. Sorting performs O(n log n) comparisons, and each comparison computes a constant amount of arithmetic, so the sort dominates the total work.
Space	O(log n) extra	The returned coordinate list uses O(n) space but is required output and is excluded. std::sort uses O(log n) auxiliary stack space in the worst case; the comparator stores only references and fixed-size values, so the bound does not grow with the matrix shape beyond that sort stack.

Here n = rows x cols, the total number of matrix cells. The output list itself is excluded from the extra-space bound.

Annotated solutionC++ · comparison sort · direct translation of the distance definition

CPPGenerate every coordinate once, then sort coordinates by their Manhattan distance from the center.

#include <algorithm>
#include <cstdlib>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        vector<vector<int>> result;

        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                result.push_back({r, c});
            }
        }

        sort(result.begin(), result.end(), [&](const vector<int>& a, const vector<int>& b) {
            int distanceA = abs(a[0] - rCenter) + abs(a[1] - cCenter);
            int distanceB = abs(b[0] - rCenter) + abs(b[1] - cCenter);
            return distanceA < distanceB;
        });

        return result;
    }
};

The comparator deliberately uses a strict less-than check. If two cells have the same distance, it returns false in both directions, leaving their relative order unrestricted exactly as the problem allows. Computing the distance inside the comparator is also safe here because each comparison needs only constant work and the distance formula has no hidden state.

The bucket alternative avoids comparison sortinga bounded-distance optimisation when linear time matters

Because the largest possible Manhattan distance is rows + cols - 2, you can create one bucket for every possible distance. Visit each cell once, compute its distance, and append the coordinate to that bucket. Reading the buckets from distance 0 upward produces the answer without comparing pairs of cells. This changes the time bound to O(n + rows + cols), at the cost of the bucket array.

CPPBucket every cell by its bounded Manhattan distance, then concatenate buckets from near to far.

#include <cstdlib>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        int maxDistance = rows + cols - 2;
        vector<vector<vector<int>>> buckets(maxDistance + 1);

        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                int distance = abs(r - rCenter) + abs(c - cCenter);
                buckets[distance].push_back({r, c});
            }
        }

        vector<vector<int>> result;
        for (const vector<vector<int>>& bucket : buckets) {
            for (const vector<int>& cell : bucket) {
                result.push_back(cell);
            }
        }

        return result;
    }
};

This is an optimisation, not a different answer: both methods generate all cells and emit them in non-decreasing distance order. The bucket version uses O(rows + cols) extra bucket-container space, excluding the output and the coordinates stored inside it, which are temporary copies of the cells. For the given small limits, the simpler comparison sort is usually easier to read; the bucket version is useful when avoiding comparison work is the priority.