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 < colsProblem Overview: You are given a grid with rows and cols and a starting cell (r0, c0). The task is to list every cell in the matrix ordered by their Manhattan distance from the starting position, where distance is calculated as |r - r0| + |c - c0|. The result should include all rows * cols cells sorted from the closest to the farthest.
Approach 1: Brute Force Sorting (O(R*C log(R*C)) time, O(R*C) space)
The most direct solution is to generate every coordinate in the grid, compute its Manhattan distance to (r0, c0), and sort the list by that distance. Iterate through the matrix with two nested loops, push each coordinate [r, c] into an array, and compute |r - r0| + |c - c0| as the sorting key. Then run a standard sort using a custom comparator based on this distance. The approach relies on basic array iteration and a sorting step to order the cells. Time complexity is dominated by sorting R*C elements, which takes O(R*C log(R*C)), while the array storing all coordinates uses O(R*C) space.
Approach 2: Bucket Sort by Manhattan Distance (O(R*C) time, O(R*C) space)
The Manhattan distance between any cell and (r0, c0) has a predictable upper bound. The maximum possible value is (rows - 1) + (cols - 1). This bounded range allows you to group cells into buckets indexed by distance instead of sorting them. Iterate through the entire matrix, compute the Manhattan distance for each cell, and append the coordinate to buckets[distance]. After filling the buckets, iterate from distance 0 up to the maximum distance and collect the cells in order. Because each cell is processed exactly once and bucket traversal is linear, the total runtime becomes O(R*C) with O(R*C) additional space for buckets.
This approach works because Manhattan distance behaves like layers expanding outward from the origin cell, a concept often used in geometry and grid traversal problems. Instead of sorting all cells globally, the bucket structure naturally groups cells that belong to the same distance layer.
Recommended for interviews: The brute force sorting approach is perfectly acceptable for small constraints and demonstrates clear understanding of Manhattan distance and matrix traversal. However, interviewers typically expect you to notice the bounded distance range and convert the sort into a bucket-based grouping. The bucket sort method reduces the complexity from O(R*C log(R*C)) to O(R*C) and shows stronger algorithmic awareness.
This approach involves iterating over all cells in the matrix to compute their Manhattan distance from the center cell. After computing the distances, the cells are sorted based on these distances.
The algorithm can be broken down into the following steps:
The solution iterates over all cells, calculates the Manhattan distance for each cell with respect to (rCenter, cCenter), and stores them as tuples in a list. After sorting these tuples by the distance value, the list is transformed to contain only the coordinates of the cells (without distances) in the desired order.
Time Complexity: The complexity is O(n*m log(n*m)), where n is the number of rows and m is the number of columns. This stems from the need to sort n*m cells.
Space Complexity: O(n*m), since we'll store all the matrix cells and their distances in a list.
This approach leverages the bounding nature of Manhattan distances by using a bucket sort-like strategy, given that the maximum possible distance is bound by (rows - 1) + (cols - 1).
We calculate the maximum possible distance and create an array 'buckets' where each index holds lists of coordinates having that index as their distance value. By effectively organizing distances with direct list insertions, this approach can avoid a computationally expensive sort step.
Time Complexity: O(n*m + D), where D is (rows + cols), the range of possible distances.
Space Complexity: O(n*m + D).
| Approach | Complexity |
|---|---|
| Brute Force Sorting | Time Complexity: The complexity is O(n*m log(n*m)), where n is the number of rows and m is the number of columns. This stems from the need to sort n*m cells. Space Complexity: O(n*m), since we'll store all the matrix cells and their distances in a list. |
| Bucket Sort Method | Time Complexity: O(n*m + D), where D is (rows + cols), the range of possible distances. Space Complexity: O(n*m + D). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Sorting | O(R*C log(R*C)) | O(R*C) | Simple implementation when grid size is small and readability matters |
| Bucket Sort by Distance | O(R*C) | O(R*C) | Optimal approach when distance range is bounded and linear performance is preferred |
Matrix Cells in Distance Order | Leetcode 1030 Solution | Searching and Sorting • Pepcoding • 5,461 views views
Watch 9 more video solutions →Practice Matrix Cells in Distance Order with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor