How to Solve Matrix Cells in Distance Order

Start by generating all coordinates of the matrix into a list. Compute the Manhattan distance from each cell to the center using |r1-rCenter| + |c1-cCenter|. Sort the coordinates by distance; any tie-breaking order is acceptable. This approach uses straightforward array generation plus simple math, ensuring correctness and easy verification for interview scenarios.

Problem Statement

Given a matrix of size rows x cols and a center cell (rCenter, cCenter), return all cell coordinates sorted by their Manhattan distance from the center. The distance between two cells (r1,c1) and (r2,c2) is |r1-r2| + |c1-c2|.

Implement a function that outputs the coordinates as an array of arrays. The order must start from the smallest distance to the largest. Any ordering that preserves distance sorting is valid, and the function should handle matrices up to 100 x 100 efficiently.

Examples

Example 1

Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0

Output: [[0,0],[0,1]]

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]]

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]]

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

Solution Approach

Generate all coordinates

Iterate through all rows and columns to build a list of [row, col] pairs. This ensures you have every matrix cell to calculate distances.

Compute Manhattan distances

For each cell [r, c], calculate the Manhattan distance to the center as |r - rCenter| + |c - cCenter|. Store the distance along with the coordinate for sorting.

Sort by distance

Sort the list of coordinates based on the computed distances. Return only the coordinates, dropping distance values. Any tie-breaking order among equal distances is valid.

Complexity Analysis

Time complexity is O(rowscolslog(rowscols)) due to sorting all cells by distance. Space complexity is O(rowscols) to store all coordinates and their distances before returning.

What Interviewers Usually Probe

• You quickly identify the Manhattan distance formula.
• You recognize the matrix is small enough for direct enumeration.
• You propose sorting coordinates by computed distance without missing cells.

Common Pitfalls or Variants

Common pitfalls

• Forgetting that ties in distance can be returned in any order, causing unnecessary constraints.
• Computing Euclidean distance instead of Manhattan distance.
• Attempting to traverse the matrix in layers manually, which is more complex than needed.

Follow-up variants

• Return cells in spiral order around the center.
• Compute distances from multiple centers and merge results.
• Handle very large matrices efficiently using bucket sort by distance.

How GhostInterview Helps

• GhostInterview auto-generates the sorted cell list and validates distances.
• It highlights tie-breaking flexibility, avoiding common overconstraints.
• It ensures distance calculation and sorting logic are correct and efficient.

Topic Pages

• Array
• Math
• Geometry
• Sorting
• Matrix

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main pattern used in Matrix Cells in Distance Order?

The primary pattern is array generation combined with math to calculate Manhattan distances for sorting.

Can I return cells with the same distance in any order?

Yes, any order among cells with the same distance is acceptable as long as the distance order is maintained.

What is the time complexity for this approach?

Time complexity is O(rowscolslog(rows*cols)) due to sorting all matrix cells by distance.

Is there a more efficient method than sorting all coordinates?

Yes, a bucket sort by distance can avoid comparison-based sorting, especially when rows and cols are large.

What common mistakes occur with this problem?

Mistakes include using Euclidean distance instead of Manhattan distance and manually layering cells unnecessarily.