Matrix Cells in Distance Order

Matrix Cells in Distance Order

What is this problem about?

The Matrix Cells in Distance Order problem gives you the dimensions of a matrix (rows and cols) and the coordinates of a specific starting cell (rCenter, cCenter). You must return the coordinates of all cells in the matrix, sorted by their Manhattan distance from the starting cell. The Manhattan distance between (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|.

Why is this asked in interviews?

This is a fantastic problem for evaluating a candidate's practical knowledge of array sorting and Breadth-First Search (BFS). Interviewers use it to see which tool you reach for: will you generate all coordinates and apply a custom sorting comparator ($O(N \log N)$), or will you recognize that the geometry of the grid allows for a BFS ripple-effect that naturally sorts them in $O(N)$ time?

Algorithmic pattern used

There are two valid patterns here:

1. Sorting with Custom Comparator: Generate all (r, c) pairs, store them in a list, and sort them using abs(r - rCenter) + abs(c - cCenter).
2. Breadth-First Search (BFS): This is the more elegant approach. Start a BFS queue with (rCenter, cCenter). Explore the 4 directional neighbors. Because BFS inherently explores nodes layer by layer (distance 1, then distance 2...), simply appending visited nodes to your result array naturally orders them by distance!

Example explanation

Matrix 2x2, Center (0, 0). Using BFS:

1. Start at (0,0). Distance 0. Add to result. Queue: [(0,0)]. Visited: (0,0).
2. Pop (0,0). Check 4 neighbors. Valid neighbors: (0,1) and (1,0).
3. Add (0,1) and (1,0) to result. Both are distance 1. Queue: [(0,1), (1,0)]. Visited marked.
4. Pop (0,1). Valid unvisited neighbor: (1,1). Add to result. Queue: [(1,0), (1,1)].
5. Pop (1,0). Valid unvisited neighbor: (1,1) (already visited!).
6. Pop (1,1). No unvisited neighbors. Result is [[0,0], [0,1], [1,0], [1,1]].

Common mistakes candidates make

If using the Sorting approach, a common mistake is creating heavy object wrappers for the coordinates just to use built-in sorting libraries, which wastes memory and processing time. If using the BFS approach, candidates often forget to use a visited boolean matrix. Without it, the BFS will process the same cells repeatedly and get trapped in an infinite loop, crashing the program.

Interview preparation tip

For the Matrix Cells in Distance Order coding problem, if you are comfortable with BFS, write the BFS solution. It demonstrates an understanding of graph traversal and algorithmic optimization (reducing $O(N \log N)$ sorting to $O(N)$ traversal). Always mention why BFS works here: "Because BFS traverses in concentric circles of increasing distance, the output array is naturally sorted by distance."