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.
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 ; } }Video 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.