Matrix Cells in Distance Order
EasyPrompt
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 < cols
Approaches
3 approaches with complexity analysis and trade-offs.
This approach is the most straightforward and brute-force way to solve the problem. It involves two main steps. First, we generate all possible coordinates within the rows x cols matrix and store them in a list. Second, we sort this list based on a custom criterion, which is the Manhattan distance of each cell from the given center (rCenter, cCenter). The cells are sorted in ascending order of this distance.
Algorithm
- Create a list or an array to hold all
rows * colscoordinates. - Use nested loops to iterate through each row
ifrom0torows-1and each columnjfrom0tocols-1, adding the coordinate[i, j]to your list. - Use a built-in sort function on the list of coordinates.
- Provide a custom comparator to the sort function. This comparator will calculate the Manhattan distance for any two cells
aandbfrom the center(rCenter, cCenter)and order them based on the difference in their distances. - The Manhattan distance for a cell
(r, c)is|r - rCenter| + |c - cCenter|. - Convert the sorted list back to a 2D array and return it.
Walkthrough
The core of this method is to first gather all the data points (the cell coordinates) and then apply a standard sorting algorithm. We can create a 2D array result of size (rows * cols) x 2 and populate it with all the cell coordinates. Then, we use Arrays.sort() with a custom Comparator. The comparator takes two coordinate arrays, a and b, calculates their respective Manhattan distances from (rCenter, cCenter), and returns the difference. This effectively sorts the entire array based on the distance from the center.
import java.util.Arrays;import java.util.Comparator; class Solution { public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) { int[][] result = new int[rows * cols][2]; int index = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { result[index++] = new int[]{i, j}; } } // Sort using a custom comparator (lambda expression for brevity) Arrays.sort(result, (a, b) -> { int distA = Math.abs(a[0] - rCenter) + Math.abs(a[1] - cCenter); int distB = Math.abs(b[0] - rCenter) + Math.abs(b[1] - cCenter); return distA - distB; }); return result; }}Complexity
Time
O(N log N), where N = rows * cols. Populating the list of cells takes O(N) time. The dominant operation is sorting the N cells, which has an average and worst-case time complexity of O(N log N) for comparison-based sorts.
Space
O(N) or O(log N), where N = rows * cols. This space is required for storing all the cell coordinates and for the space used by the sorting algorithm. The output array itself requires O(N) space. The auxiliary space for sorting in Java's `Arrays.sort` is O(log N) for primitives and O(N) for objects in the worst case.
Trade-offs
Pros
Easy to understand and implement.
Leverages powerful, highly-optimized built-in sorting functions.
Cons
The time complexity of
O(N log N)is suboptimal compared to linear time solutions.For very large matrices, the performance degradation will be noticeable.
A more efficient approach is to use Bucket Sort, as the sorting keys (the distances) are integers with a limited range. Instead of comparing each cell with every other cell, we can group them by their distance from the center. We create a set of 'buckets', where each bucket corresponds to a specific distance. We iterate through the matrix, calculate the distance for each cell, and place it in the correct bucket. Finally, we concatenate the buckets in order, from distance 0 upwards, to get the final sorted list.
Algorithm
- First, calculate the maximum possible Manhattan distance from the center to any cell in the grid.
maxDist = max(rCenter, rows - 1 - rCenter) + max(cCenter, cols - 1 - cCenter). - Create a list of lists (or an array of lists) called
buckets, with a size ofmaxDist + 1. - Iterate through every cell
(r, c)in the matrix. - For each cell, calculate its distance
d = |r - rCenter| + |c - cCenter|. - Add the coordinate
[r, c]to the list atbuckets.get(d). - After all cells are placed in their respective distance buckets, create a final result array.
- Iterate through the
bucketsfrom index0tomaxDist. For each distance, append all cells from that bucket to the result array. - Return the populated result array.
Walkthrough
This method avoids a comparison-based sort by taking advantage of the data's properties. The distances are integers, so we can use them as indices in an array. We create an array of lists, where the index d holds a list of all cells at distance d from the center. We make one pass over the entire grid to populate these buckets. Then, we make a second pass over the bucket array itself, from index 0 to maxDist, collecting all the cells into our final result array. This process sorts the cells in linear time.
import java.util.ArrayList;import java.util.List; class Solution { public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) { int maxDist = Math.max(rCenter, rows - 1 - rCenter) + Math.max(cCenter, cols - 1 - cCenter); List<List<int[]>> buckets = new ArrayList<>(); for (int i = 0; i <= maxDist; i++) { buckets.add(new ArrayList<>()); } for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { int dist = Math.abs(i - rCenter) + Math.abs(j - cCenter); buckets.get(dist).add(new int[]{i, j}); } } int[][] result = new int[rows * cols][2]; int index = 0; for (int i = 0; i <= maxDist; i++) { for (int[] cell : buckets.get(i)) { result[index++] = cell; } } return result; }}Complexity
Time
O(N), where N = rows * cols. We iterate through all N cells once to place them into buckets (O(N)). We then iterate through the buckets to build the result array. Since there are N cells in total across all buckets, this second step also takes O(N). The total time is O(N).
Space
O(N), where N = rows * cols. The `buckets` data structure needs to store all N cells, and the final `result` array also takes O(N) space.
Trade-offs
Pros
Optimal time complexity of O(N).
Conceptually simple for those familiar with non-comparison sorts.
Cons
Requires extra space for the buckets, which can be large depending on the maximum distance.
It's a two-pass algorithm: one pass to distribute cells into buckets and a second pass to collect them.
The most efficient and idiomatic approach for this type of problem is to use Breadth-First Search (BFS). We can view the matrix as a graph where each cell is a node. A BFS, by its nature, explores a graph layer by layer from a starting source. In our case, the source is (rCenter, cCenter). The first layer of exploration contains cells at distance 1, the second layer contains cells at distance 2, and so on. This perfectly matches the problem's requirement to order cells by their distance.
Algorithm
- Initialize a queue and add the starting cell
[rCenter, cCenter]. - Create a 2D boolean array
visitedof sizerows x colsto track visited cells. Mark the starting cell as visited. - Create the
resultarray of sizerows * colsand anindexto populate it. - While the queue is not empty:
- Dequeue a cell, let's say
currentCell. - Add
currentCellto theresultarray at the currentindex. - Explore the four neighbors of
currentCell(up, down, left, right). - For each neighbor, if it is within the grid boundaries and has not been visited:
- Enqueue the neighbor.
- Mark the neighbor as visited.
- Dequeue a cell, let's say
- Once the queue is empty, all cells have been visited in distance order, and the
resultarray is fully populated. Return it.
Walkthrough
We start the BFS by putting the center cell (rCenter, cCenter) into a queue. We also use a visited matrix to ensure we process each cell only once. In a loop, we dequeue a cell, add it to our result list, and then enqueue all its valid, unvisited neighbors. A valid neighbor is one that is within the matrix bounds. Because BFS explores level by level, we are guaranteed to add cells to our result list in increasing order of their Manhattan distance from the center.
import java.util.LinkedList;import java.util.Queue; class Solution { public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) { boolean[][] visited = new boolean[rows][cols]; int[][] result = new int[rows * cols][2]; int index = 0; Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{rCenter, cCenter}); visited[rCenter][cCenter] = true; int[] dr = {0, 0, 1, -1}; // Direction vectors for row changes int[] dc = {1, -1, 0, 0}; // Direction vectors for col changes while (!queue.isEmpty()) { int[] cell = queue.poll(); result[index++] = cell; for (int i = 0; i < 4; i++) { int newR = cell[0] + dr[i]; int newC = cell[1] + dc[i]; if (newR >= 0 && newR < rows && newC >= 0 && newC < cols && !visited[newR][newC]) { visited[newR][newC] = true; queue.offer(new int[]{newR, newC}); } } } return result; }}Complexity
Time
O(N), where N = rows * cols. Each cell is enqueued and dequeued exactly once. For each cell, we perform a constant amount of work (checking its four neighbors). Thus, the runtime is linear with respect to the number of cells.
Space
O(N), where N = rows * cols. The `visited` array requires O(N) space. The queue's maximum size is proportional to the perimeter of the largest diamond shape, which is O(rows + cols). The space is dominated by the `visited` array.
Trade-offs
Pros
Optimal time complexity of O(N).
Generates the result in a single pass over the grid cells.
It's a very natural and common pattern for shortest-path problems on unweighted grids.
Cons
Requires auxiliary space for both the queue and the
visitedarray.
Solutions
Solution
import java.util.Deque ; class Solution { public int [][] allCellsDistOrder ( int rows , int cols , int rCenter , int cCenter ) { Deque < int []> q = new ArrayDeque <>(); q . offer ( new int [] { rCenter , cCenter }); boolean [][] vis = new boolean [ rows ][ cols ]; vis [ rCenter ][ cCenter ] = true ; int [][] ans = new int [ rows * cols ][ 2 ]; int [] dirs = {- 1 , 0 , 1 , 0 , - 1 }; int idx = 0 ; while (! q . isEmpty ()) { for ( int n = q . size (); n > 0 ; -- n ) { var p = q . poll (); ans [ idx ++] = p ; for ( int k = 0 ; k < 4 ; ++ k ) { int x = p [ 0 ] + dirs [ k ], y = p [ 1 ] + dirs [ k + 1 ]; if ( x >= 0 && x < rows && y >= 0 && y < cols && ! vis [ x ][ y ]) { vis [ x ][ y ] = true ; q . offer ( new int [] { x , y }); } } } } return ans ; } }class Solution {public: vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) { queue<pair<int, int>> q; q.emplace(rCenter, cCenter); vector<vector<int>> ans; bool vis[rows][cols]; memset(vis, false, sizeof(vis)); vis[rCenter][cCenter] = true; int dirs[5] = {-1, 0, 1, 0, -1}; while (!q.empty()) { for (int n = q.size(); n; --n) { auto [i, j] = q.front(); q.pop(); ans.push_back({i, j}); for (int k = 0; k < 4; ++k) { int x = i + dirs[k]; int y = j + dirs[k + 1]; if (x >= 0 && x < rows && y >= 0 && y < cols && !vis[x][y]) { vis[x][y] = true; q.emplace(x, y); } } } } return ans; }};class Solution: def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]: q = deque([[rCenter, cCenter]]) vis = [[False] * cols for _ in range(rows)] vis[rCenter][cCenter] = True ans = [] while q: for _ in range(len(q)): p = q . popleft() ans . append(p) for a, b in pairwise((- 1, 0, 1, 0, - 1)): x, y = p[0] + a, p[1] + b if 0 <= x < rows and 0 <= y < cols and not vis[x][y]: vis[x][y] = True q . append([x, y]) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.