Matrix Cells in Distance Order — Problem & Solution
Matrix Cells in Distance Order solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Matrix Cells in Distance Order is an easy coding problem on arrays, math and sorting, asked in Amazon, Adobe and Yahoo interviews.
- Difficulty: Easy
- Topics: Arrays, Math, Sorting, Matrix
- Asked at: Amazon, Adobe, Yahoo
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given four integers describing a rows × cols matrix and a starting cell (rCenter, cCenter).
Return the coordinates of all the cells, sorted by their Manhattan distance from the centre. Ties are broken by row and then by column, both ascending.
The Manhattan distance between (r1, c1) and (r2, c2) is abs(r1 - r2) + abs(c1 - c2).
Example 1
Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]
Example 2
Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1
Output: [[0,1],[0,0],[1,1],[1,0]]
Example 3
Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2
Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
Constraints
1 <= rows, cols <= 80 <= rCenter < rows0 <= cCenter < cols
Hints for Matrix Cells in Distance Order
Hint 1
Generate every cell, then sort by the distance key.
Hint 2
State the tie-break explicitly — distance alone leaves many valid orders, and this problem fixes one.
Hint 3
A bucket sort by distance also works, since the distance is bounded by
rows + cols.
How to solve Matrix Cells in Distance Order
Generate every cell and sort by (distance, row, column).
Approach
- List all
[r, c]. - Sort with key
(|r - rCenter| + |c - cCenter|, r, c).
Why it works
The composite key encodes the required order including the stated tie-break, so a stable comparison sort produces exactly the expected output.
Complexity
- Time —
O(rc · log(rc)) - Space —
O(rc)
Pitfalls
- Distance is bounded by
rows + cols, so bucket sort by distance is linear if needed.
Reference solution
Python
def allCellsDistOrder(rows: int, cols: int, rCenter: int, cCenter: int):
cells = [[r, c] for r in range(rows) for c in range(cols)]
cells.sort(key=lambda cell: (abs(cell[0] - rCenter) + abs(cell[1] - cCenter), cell[0], cell[1]))
return cellsJava
public static int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
int[][] cells = new int[rows * cols][2];
int pos = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
cells[pos][0] = r;
cells[pos][1] = c;
pos++;
}
}
Arrays.sort(cells, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
int da = Math.abs(a[0] - rCenter) + Math.abs(a[1] - cCenter);
int db = Math.abs(b[0] - rCenter) + Math.abs(b[1] - cCenter);
if (da != db) return da - db;
if (a[0] != b[0]) return a[0] - b[0];
return a[1] - b[1];
}
});
return cells;
}C++
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(), [rCenter, cCenter](const vector<int>& a, const vector<int>& b) {
int da = abs(a[0] - rCenter) + abs(a[1] - cCenter);
int db = abs(b[0] - rCenter) + abs(b[1] - cCenter);
if (da != db) return da < db;
if (a[0] != b[0]) return a[0] < b[0];
return a[1] < b[1];
});
return cells;
}JavaScript
var allCellsDistOrder = function(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(function(a, b) {
const da = Math.abs(a[0] - rCenter) + Math.abs(a[1] - cCenter);
const db = Math.abs(b[0] - rCenter) + Math.abs(b[1] - cCenter);
if (da !== db) return da - db;
if (a[0] !== b[0]) return a[0] - b[0];
return a[1] - b[1];
});
return cells;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms