You are given four integers row, cols, rCenter, and cCenter. There is a rows x cols matrix and you are on the cell with the coordinates (rCenter, cCenter).
Return the coordinates of all cells in the matrix, sorted by their distance from (rCenter, cCenter) from the smallest distance to the 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 |r1 - r2| + |c1 - c2|.
Example 1:
Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0 Output: [[0,0],[0,1]] Explanation: The distances from (0, 0) to other cells are: [0,1]
Example 2:
Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1 Output: [[0,1],[0,0],[1,1],[1,0]] Explanation: The distances from (0, 1) to other cells are: [0,1,1,2] The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.
Example 3:
Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2 Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]] Explanation: The distances from (1, 2) to other cells are: [0,1,1,2,2,3] There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].
Constraints:
1 <= rows, cols <= 1000 <= rCenter < rows0 <= cCenter < colsIn #1030 Matrix Cells in Distance Order, the goal is to return all matrix coordinates sorted by their Manhattan distance from a given cell (r0, c0). The Manhattan distance is defined as |r - r0| + |c - c0|, which measures grid distance without diagonals.
A straightforward strategy is to generate every coordinate in the matrix and then sort them based on their computed Manhattan distance. Since the number of cells is rows × cols, this approach works efficiently for the constraints and is easy to implement.
An optimized idea leverages the fact that distances are bounded by the matrix dimensions. Instead of general sorting, we can group cells by distance (similar to bucketing) or explore outward from the start cell in layers, similar to BFS. These strategies avoid comparison-based sorting while naturally producing cells in increasing distance order.
Choosing the right approach depends on simplicity versus optimization, but all valid strategies process each matrix cell once.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Generate all cells + Sort by Manhattan distance | O(R × C log(R × C)) | O(R × C) |
| Bucket sort / BFS by distance layers | O(R × C) | O(R × C) |
Striver
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of problem appears in coding interviews because it tests understanding of matrix traversal, sorting strategies, and distance calculations. It is commonly categorized as an easy-level problem but still checks algorithmic thinking.
Manhattan distance between two cells is calculated as |r1 - r2| + |c1 - c2|. It represents the number of grid moves required when movement is restricted to vertical and horizontal directions.
A common approach is to generate all matrix coordinates and sort them by their Manhattan distance from the starting cell. A more optimized solution groups cells by distance or performs a BFS-style expansion from the start cell, which avoids comparison sorting and runs in linear time.
Arrays or lists are typically sufficient for storing coordinates. For optimized approaches, buckets (lists indexed by distance) or a queue for BFS can help process cells in increasing Manhattan distance order efficiently.