Matrix Cells in Distance Order: BFS Rings on a Grid

You are given a matrix with rows rows and cols columns. You are also given a center cell (rCenter, cCenter). Return all cells in the matrix, sorted by their Manhattan distance from the center cell. If two cells have the same distance, they can appear in any order.

This is LeetCode 1030: Matrix Cells in Distance Order, and it is one of the cleanest introductions to distance-based grid traversal. The pattern you learn here, expanding outward from a center cell in concentric rings, shows up again and again in BFS problems on grids.

Why this problem matters

Grid problems are everywhere in interviews, and most of them involve some notion of distance. "How far is this cell from the nearest zero?" "How many minutes until rot reaches every orange?" "What is the shortest path from here to there?" All of these rely on the same core idea: expanding outward from a source cell, one distance level at a time.

Matrix Cells in Distance Order strips away the complexity and asks you to do just that. There is no obstacle to avoid, no special condition to track. You simply need to enumerate cells in order of increasing Manhattan distance. It is the purest form of the "expand from center" pattern, and once you understand it, harder BFS problems become variations on the same theme.

The key insight

You have two clean approaches. The first is to generate all cells in the matrix, compute each cell's Manhattan distance from (rCenter, cCenter), and sort by that distance. This is simple and works well for an easy problem.

The second approach is BFS. Start from (rCenter, cCenter), and expand outward level by level. Each BFS level corresponds to one ring of cells at the same Manhattan distance. You process distance 0 first (just the center), then distance 1, then distance 2, and so on. This naturally produces cells in sorted distance order without any explicit sorting step.

Both approaches produce correct results. The sort-based approach is easier to code. The BFS approach is more efficient and teaches a pattern you will reuse in harder problems.

The solution

from collections import deque

def all_cells_dist_order(rows, cols, r_center, c_center):
    result = []
    visited = [[False] * cols for _ in range(rows)]
    queue = deque()

    queue.append((r_center, c_center))
    visited[r_center][c_center] = True

    while queue:
        r, c = queue.popleft()
        result.append([r, c])
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc]:
                visited[nr][nc] = True
                queue.append((nr, nc))

    return result

Let's walk through what each piece does.

The BFS starts from the center cell. We mark it as visited and add it to the queue. Then we process cells in FIFO order: for each cell we pop, we append it to the result and explore its four neighbors. Because BFS processes cells in order of their distance from the source, the result list ends up sorted by Manhattan distance automatically.

The visited matrix prevents us from adding the same cell twice. Each cell enters the queue exactly once, so the output contains every cell in the matrix exactly once.

Visual walkthrough

Let's trace through a 3x4 grid with center at (1,1). Watch how BFS expands in concentric rings, collecting all cells at distance 0, then distance 1, then distance 2, and so on.

Each ring captures every cell at the same Manhattan distance from the center. Within a ring, the order depends on which direction BFS explores first, but the problem allows any order within the same distance. By the time all rings are processed, every cell in the matrix appears in the result exactly once.

Complexity analysis

Time for sorting is O(mn log(mn)) because you generate all m*n cells and sort them. The distance computation for each cell is O(1), but the sort dominates.

Time for BFS is O(m*n). Each cell is visited exactly once, and the work per cell (checking four neighbors) is constant. No sorting step is needed because BFS naturally produces cells in distance order.

Space is O(m*n) for both approaches. The sort approach stores all cells in a list. The BFS approach uses a visited matrix and a queue, both bounded by the total number of cells.

The building blocks

1. Manhattan distance

The Manhattan distance between two cells (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|. It measures how many single-step horizontal and vertical moves you need to travel between them. On a grid where you can only move up, down, left, or right, this is the shortest path distance.

def manhattan(r1, c1, r2, c2):
    return abs(r1 - r2) + abs(c1 - c2)

You will see Manhattan distance in any grid problem that involves "closest cell," "distance from source," or "expanding wavefront." Recognizing it quickly saves you time in interviews.

2. BFS level-by-level

BFS from a single source naturally visits cells in order of increasing distance. You do not even need the for _ in range(len(queue)) level-tracking trick here, because simple FIFO order already guarantees distance ordering. But if you did want to process one ring at a time (for example, to count how many cells are at each distance), you would use the level-by-level pattern:

while queue:
    for _ in range(len(queue)):
        r, c = queue.popleft()
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr, nc = r + dr, c + dc
            if valid(nr, nc) and not visited[nr][nc]:
                visited[nr][nc] = True
                queue.append((nr, nc))
    distance += 1

This same structure powers Rotting Oranges (multi-source BFS with a timer), 01 Matrix (shortest distance from each cell to the nearest zero), and many other grid problems.

Edge cases

Before submitting, think through these scenarios:

• 1x1 grid: only one cell exists, and it is the center. Return [[rCenter, cCenter]].
• Center at a corner: the maximum distance is (rows - 1) + (cols - 1). BFS still works correctly since it only explores valid in-bounds neighbors.
• Center on an edge: one side has fewer rings than the other. BFS handles this naturally because out-of-bounds neighbors are skipped.
• Large grid: the sort approach handles up to 100x100 grids comfortably within the constraints. BFS is even faster.
• Same distance cells: multiple cells can share the same Manhattan distance. The problem accepts any ordering among cells at the same distance, so both BFS and sorting produce valid answers.

From understanding to recall

You have seen how BFS expands from a center cell in concentric distance rings, and how sorting by Manhattan distance achieves the same result with less code. The logic is clean for both approaches. But writing either one from scratch under time pressure requires muscle memory, not just understanding.

The details that trip people up are small but costly. Do you initialize the visited matrix before or after adding the center to the queue? Do you mark a cell as visited when you add it to the queue, or when you pop it? (The answer: when you add it, to prevent duplicates.) These are recall gaps, and they show up in every BFS problem, not just this one.

Spaced repetition closes them. You practice writing BFS initialization, the neighbor exploration loop, and the visited check from memory at increasing intervals. After a few rounds, the template is automatic. You see "cells in distance order" and the BFS code flows out without hesitation.

Related posts

• Rotting Oranges - Multi-source BFS that spreads outward from multiple starting cells simultaneously, the natural next step after single-source distance expansion
• Flood Fill - Grid DFS/BFS from a single source that fills connected regions, a simpler version of the "expand from center" pattern
• 01 Matrix - Multi-source BFS that computes the shortest distance from every cell to the nearest zero, directly building on the distance ring concept

CodeBricks breaks Matrix Cells in Distance Order into its Manhattan distance and BFS expansion building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a grid BFS problem shows up in your interview, you do not think about it. You just write it.