Matrix Cells in Distance Order - Video Solutions
Matrix Cells in Distance Order | Leetcode 1030 Solution | Searching and Sorting
Matrix Cells in Distance Order - Video Solution
Watch 10 video solutions for Matrix Cells in Distance Order, a easy level problem involving Array, Math, Geometry. This walkthrough by Pepcoding has 5,509 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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
Approach Overview
Problem 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.
Complexity Analysis
| 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 |