LeetCode 1030 - Matrix Cells in Distance Order

LeetCode Problem 1030

Difficulty: 🟢 Easy
Topics: Array, Math, Geometry, Sorting, Matrix

Solution

Problem Understanding

This problem asks us to return every cell in a matrix, ordered by its Manhattan distance from a given center cell.

We are given four integers:

• rows, the number of rows in the matrix
• cols, the number of columns in the matrix
• rCenter, the row index of the reference cell
• cCenter, the column index of the reference cell

The matrix dimensions are rows x cols, meaning valid row indices range from 0 to rows - 1, and valid column indices range from 0 to cols - 1.

For every cell (r, c) in the matrix, we compute its distance from the center cell (rCenter, cCenter) using the Manhattan distance formula:

$$|r - rCenter| + |c - cCenter|$$

The goal is to return all coordinates sorted from the smallest distance to the largest distance. If multiple cells have the same distance, their relative order does not matter because the problem explicitly allows any valid ordering among equal-distance cells.

For example, if the center is (0, 0) in a 1 x 2 matrix, the distances are:

• (0,0) → 0
• (0,1) → 1

So the correct ordering is [[0,0],[0,1]].

The constraints are small:

• 1 <= rows, cols <= 100
• At most 100 × 100 = 10,000 cells exist

This tells us that even an O(n log n) sorting solution is perfectly acceptable, where n = rows × cols. Since n ≤ 10,000, sorting remains efficient.

There are several edge cases worth considering upfront. A 1 x 1 matrix contains only the center itself, so the answer is trivial. A matrix with a single row or single column reduces movement to one dimension, which can expose indexing mistakes. Another subtle case occurs when many cells share the same distance from the center. Since equal ordering is unrestricted, we only need to guarantee nondecreasing distance order, not a unique arrangement. The problem also guarantees that the center coordinates are always valid, so we never need bounds validation for the input center.

Approaches

Brute Force Approach

The most direct solution is to generate every cell in the matrix, compute its Manhattan distance from the center, and then sort all cells based on that distance.

We iterate through every row and column combination, producing coordinates (r, c). For each coordinate, we calculate:

$$|r - rCenter| + |c - cCenter|$$

We then sort all cells according to this value.

This works because sorting guarantees that cells appear in increasing order of distance. Since every matrix cell is included exactly once, the result is complete and correct.

The downside is that sorting introduces an O(n log n) time cost, where n is the number of cells. Although this is efficient enough for the problem constraints, we can do slightly better conceptually.

Optimal Approach

The key insight is that Manhattan distance forms expanding diamond-shaped layers around the center.

Instead of explicitly sorting, we can bucket cells by distance. The maximum possible Manhattan distance in the grid is limited:

$$(rows - 1) + (cols - 1)$$

We can iterate through every cell once, compute its distance, and place it into a bucket corresponding to that distance. Then, we concatenate buckets from smallest distance to largest distance.

This avoids sorting entirely. Since distance values are bounded, traversing the buckets is linear.

The reasoning works because Manhattan distance is discrete and bounded. Every cell belongs to exactly one distance level, and iterating distances in ascending order naturally produces the required ordering.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Generate all cells and sort by Manhattan distance
Optimal	O(n)	O(n)	Group cells by distance, then collect in ascending order

Here, n = rows × cols.

Algorithm Walkthrough

We will use the bucket-based optimal solution.

1. Compute the maximum possible Manhattan distance in the matrix.

Since the furthest cell can be at the opposite corner, the largest distance is:

maxDistance = (rows - 1) + (cols - 1)

This tells us how many buckets we need. 2. Create buckets for every possible distance.

We create a list where each index corresponds to a Manhattan distance. Each bucket stores coordinates whose distance equals that index. 3. Traverse every matrix cell.

Use nested loops over all row and column indices:

• Row from 0 to rows - 1
• Column from 0 to cols - 1

This guarantees every matrix cell is visited exactly once. 4. Compute Manhattan distance for each cell.

For a cell (r, c):

distance = abs(r - rCenter) + abs(c - cCenter)

This determines which bucket the cell belongs to. 5. Add the cell to the correct bucket.

Append [r, c] to buckets[distance].

Multiple cells may share the same distance, and any ordering among them is acceptable. 6. Build the final answer.

Iterate through buckets from smallest distance to largest distance, appending all stored coordinates to the result list. 7. Return the result.

Since buckets are processed in ascending distance order, the final list automatically satisfies the problem requirement.

Why it works

The algorithm works because every cell has exactly one Manhattan distance from the center. By placing each cell into a bucket indexed by its distance, we partition the matrix into distance layers. Processing buckets from distance 0 upward guarantees that all returned cells appear in nondecreasing distance order. Since every cell is inserted exactly once and later collected exactly once, the result is complete and correctly ordered.

Python Solution

from typing import List

class Solution:
    def allCellsDistOrder(
        self,
        rows: int,
        cols: int,
        rCenter: int,
        cCenter: int
    ) -> List[List[int]]:
        max_distance = (rows - 1) + (cols - 1)

        buckets = [[] for _ in range(max_distance + 1)]

        for row in range(rows):
            for col in range(cols):
                distance = abs(row - rCenter) + abs(col - cCenter)
                buckets[distance].append([row, col])

        result = []

        for bucket in buckets:
            result.extend(bucket)

        return result

The implementation begins by calculating the maximum Manhattan distance possible in the matrix. This determines the number of buckets required.

We then initialize buckets, where index i stores all cells whose Manhattan distance equals i.

The nested loops iterate through every matrix coordinate. For each cell, the Manhattan distance is computed using absolute differences in row and column positions. The cell is immediately placed into its matching bucket.

After all cells have been grouped, we build the final answer by iterating through the buckets in ascending order and extending the result list with all coordinates stored inside each bucket.

This implementation directly mirrors the algorithm walkthrough. No explicit sorting is needed because bucket indices already represent sorted distance order.

Go Solution

func allCellsDistOrder(rows int, cols int, rCenter int, cCenter int) [][]int {
	maxDistance := (rows - 1) + (cols - 1)

	buckets := make([][][]int, maxDistance+1)

	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			distance := abs(row-rCenter) + abs(col-cCenter)
			buckets[distance] = append(
				buckets[distance],
				[]int{row, col},
			)
		}
	}

	result := make([][]int, 0, rows*cols)

	for _, bucket := range buckets {
		result = append(result, bucket...)
	}

	return result
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

The Go implementation follows the same logic as the Python version. Since Go does not provide a built-in integer abs function, we define a helper function.

The bucket structure is represented as [][][]int, where each bucket stores a slice of coordinate pairs. The result slice is preallocated with capacity rows * cols, which avoids unnecessary reallocations while appending.

Unlike Python lists, Go slices benefit from explicit capacity management for performance. Since constraints are small, integer overflow is not a concern.

Worked Examples

Example 1

Input:

rows = 1
cols = 2
rCenter = 0
cCenter = 0

Maximum distance:

(1 - 1) + (2 - 1) = 1

Initial buckets:

[
  [],  // distance 0
  []   // distance 1
]

Cell	Distance	Buckets State
(0,0)	0	[[[0,0]], []]
(0,1)	1	[[[0,0]], [[0,1]]]

Final concatenation:

[[0,0],[0,1]]

Example 2

Input:

rows = 2
cols = 2
rCenter = 0
cCenter = 1

Maximum distance:

(2 - 1) + (2 - 1) = 2

Cell	Distance	Bucket
(0,1)	0	0
(0,0)	1	1
(1,1)	1	1
(1,0)	2	2

Buckets after processing:

[
  [[0,1]],
  [[0,0],[1,1]],
  [[1,0]]
]

Final output:

[[0,1],[0,0],[1,1],[1,0]]

Another valid ordering among equal-distance cells would also be accepted.

Example 3

Input:

rows = 2
cols = 3
rCenter = 1
cCenter = 2

Maximum distance:

(2 - 1) + (3 - 1) = 3

Cell	Distance
(1,2)	0
(0,2)	1
(1,1)	1
(0,1)	2
(1,0)	2
(0,0)	3

Buckets:

[
  [[1,2]],
  [[0,2],[1,1]],
  [[0,1],[1,0]],
  [[0,0]]
]

Final result:

[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(rows × cols)	Every cell is visited once and inserted into a bucket
Space	O(rows × cols)	Buckets and result storage contain all matrix cells

Let n = rows × cols.

The algorithm scans every cell exactly once, computes a constant-time Manhattan distance, and inserts the cell into a bucket. Constructing the final answer also touches each cell once. Since the number of distance buckets is bounded by rows + cols, which is at most 200, it does not affect the asymptotic complexity. Therefore, the total runtime is linear in the number of cells.

The space complexity is also linear because every matrix coordinate must be stored in the output, and buckets collectively contain exactly all cells.

Test Cases

def normalize(result):
    """Verify sorted-by-distance property."""
    return result

solution = Solution()

# Example 1
assert solution.allCellsDistOrder(
    1, 2, 0, 0
) == [[0, 0], [0, 1]]  # single row matrix

# Example 2
result = solution.allCellsDistOrder(2, 2, 0, 1)
distances = [
    abs(r - 0) + abs(c - 1)
    for r, c in result
]
assert distances == sorted(distances)  # equal distance order may vary

# Example 3
result = solution.allCellsDistOrder(2, 3, 1, 2)
distances = [
    abs(r - 1) + abs(c - 2)
    for r, c in result
]
assert distances == sorted(distances)  # valid ordering

# Minimum matrix size
assert solution.allCellsDistOrder(
    1, 1, 0, 0
) == [[0, 0]]  # single cell only

# Single column matrix
result = solution.allCellsDistOrder(4, 1, 2, 0)
distances = [
    abs(r - 2)
    for r, c in result
]
assert distances == sorted(distances)  # one-dimensional case

# Center at corner
result = solution.allCellsDistOrder(3, 3, 0, 0)
distances = [
    abs(r - 0) + abs(c - 0)
    for r, c in result
]
assert distances == sorted(distances)  # asymmetric expansion

# Center in middle
result = solution.allCellsDistOrder(5, 5, 2, 2)
distances = [
    abs(r - 2) + abs(c - 2)
    for r, c in result
]
assert distances == sorted(distances)  # symmetric layout

# Maximum constraint stress test
result = solution.allCellsDistOrder(100, 100, 50, 50)
assert len(result) == 10000  # full matrix coverage

Test	Why
1x2 example	Validates simplest nontrivial case
2x2 example	Verifies equal-distance ties
2x3 example	Confirms larger distance spread
1x1 matrix	Tests smallest possible input
Single column matrix	Verifies one-dimensional traversal
Corner center	Ensures asymmetrical distances work
Middle center	Validates balanced expansion
100x100 matrix	Confirms scalability at maximum limits

Edge Cases

Single Cell Matrix

A 1 x 1 matrix contains only the center cell itself. A careless implementation might accidentally skip the center or mishandle bucket sizing. Our implementation correctly computes a maximum distance of 0, creates one bucket, inserts the center cell, and returns [[0,0]].

Single Row or Single Column

When either dimension equals 1, movement effectively becomes one-dimensional. This can reveal indexing errors or assumptions that both row and column movement exist. Since our implementation simply iterates over valid coordinates and computes Manhattan distance generically, no special handling is needed.

Multiple Cells with Equal Distance

Several cells may share the same Manhattan distance. For example, in a 3 x 3 matrix centered at (1,1), four neighboring cells all have distance 1. A buggy implementation might incorrectly assume a strict ordering requirement. The problem explicitly allows any order among equal-distance cells, and our bucket approach naturally preserves insertion order without violating correctness.

Center at a Corner

When the center lies at a corner, distances grow unevenly across the matrix. Some algorithms that assume symmetry may fail here. Because we compute distances individually for every cell, the implementation handles corner centers exactly the same way as middle positions, ensuring correctness in asymmetric layouts.