Skip to main content
Talentd

Matrix Cells in Distance Order - Solution & Explanation

EasyArrayMathGeometrySorting17 min readAsked at: Yahoo
Practice this problem

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 <= 100
  • 0 <= rCenter < rows
  • 0 <= 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.

Approach 1: Brute Force Sorting

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:

  • Initialize a list to store all cells in the matrix, along with their distances to the center.
  • Iterate over each cell in the matrix, compute the Manhattan distance from the center, and add it to the list.
  • Sort the list by the distance.
  • Return the sorted list of cell coordinates.

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.

Code

PythonJavaScriptC++JavaCC#

Python

JavaScript

C++

Java

C

C#

Complexity

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.

Try this approach in the editor →

Approach 2: Bucket Sort Method

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).

  • Create an array of empty lists for buckets, each index representing a potential distance.
  • Iterate through every cell, calculate its distance to the center cell, and place the cell in the corresponding distance bucket.
  • Iterate over the bucket array and concatenate the lists into a single result list.

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.

Code

PythonJavaScriptC++JavaCC#

Python

JavaScript

C++

Java

C

C#

Complexity

Time Complexity: O(n*m + D), where D is (rows + cols), the range of possible distances.

Space Complexity: O(n*m + D).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SortingO(R*C log(R*C))O(R*C)Simple implementation when grid size is small and readability matters
Bucket Sort by DistanceO(R*C)O(R*C)Optimal approach when distance range is bounded and linear performance is preferred

Video Solution

Matrix Cells in Distance Order | Leetcode 1030 Solution | Searching and Sorting • Pepcoding • 5,509 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Matrix Cells in Distance Order easy or hard?
Matrix Cells in Distance Order is classified as an Easy problem. The brute force solution requires simple matrix iteration and sorting, while the optimal bucket sort approach introduces a useful optimization based on the bounded range of Manhattan distances.
Matrix Cells in Distance Order Python/Java solution
In Python or Java, iterate through all grid coordinates, compute the Manhattan distance |r−r0| + |c−c0|, and either sort the list of cells by that value or place them into distance buckets. Python commonly uses list sorting with a key function, while Java uses a comparator or bucket lists.
How to solve Matrix Cells in Distance Order in O(n)?
Compute the Manhattan distance for every cell and store the coordinate in a bucket corresponding to that distance. Because the maximum distance is bounded by (rows−1)+(cols−1), you can iterate through the buckets sequentially to produce the result. This processes R*C cells once, giving O(R*C) time complexity.
What is the best approach for Matrix Cells in Distance Order?
The bucket sort method is the best approach. Since the Manhattan distance ranges from 0 to (rows−1)+(cols−1), you can group cells into distance buckets instead of sorting them. This reduces the runtime from O(R*C log(R*C)) to O(R*C) while still processing every cell exactly once.
Is Matrix Cells in Distance Order asked at Google/Amazon/Meta?
Matrix and grid traversal problems with Manhattan distance frequently appear in interviews at companies like Amazon and Google. While this exact problem may vary in wording, the underlying pattern of distance-based ordering in a grid is common in technical interviews.
What data structure is used in Matrix Cells in Distance Order?
The solution primarily uses arrays or lists to store coordinates. The optimal approach also uses an array of lists (buckets) where each index represents a Manhattan distance and stores all cells that share that distance.
What is the time complexity of Matrix Cells in Distance Order?
The optimal solution runs in O(R*C) time using bucket sort because each matrix cell is visited once and placed into a bucket indexed by its Manhattan distance. A simpler brute force solution that sorts all cells takes O(R*C log(R*C)) time.

Ready to solve this problem?

Practice Matrix Cells in Distance Order with our built-in code editor and test cases.

Practice on FleetCode
Previous

Cells in a Range on an Excel Sheet