Matrix Cells in Distance Order

Difficulty: Easy | Acceptance: 74.10% | Paid: No Topics: Array, Math, Geometry, Sorting, Matrix

You are given four integers rows, 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|.

• Examples
• Constraints
• Brute Force with Sorting
• BFS Traversal
• Bucket Sort

Examples

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]

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 [0,1,1,2].

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 such as [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]].

Constraints

1 <= rows, cols <= 100
0 <= rCenter < rows
0 <= cCenter < cols

Brute Force with Sorting

Intuition Generate all cell coordinates, calculate their Manhattan distance from the center, and sort by distance. Python’s sort is stable, so cells with equal distance maintain their natural row-major order.

Steps

• Iterate through all cells in the matrix
• Calculate Manhattan distance for each cell
• Sort cells by their distance from the center
• Return the sorted list

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:
        cells = []
        for r in range(rows):
            for c in range(cols):
                cells.append([r, c])
        cells.sort(key=lambda x: abs(x[0] - rCenter) + abs(x[1] - cCenter))
        return cells

Complexity

• Time: O(rows × cols × log(rows × cols)) for sorting
• Space: O(rows × cols) to store all cells
• Notes: Simple but not optimal due to sorting overhead

BFS Traversal

Intuition Breadth-First Search naturally explores cells in order of increasing distance from the starting point. Starting from the center, we visit all adjacent cells level by level.

Steps

• Initialize a queue with the center cell and mark it as visited
• Use BFS to explore cells in 4 directions
• Add each visited cell to the result
• Continue until all cells are visited

from collections import deque
from typing import List

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:
        result = []
        visited = [[False] * cols for _ in range(rows)]
        queue = deque([(rCenter, cCenter)])
        visited[rCenter][cCenter] = True
        
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        while queue:
            r, c = queue.popleft()
            result.append([r, c])
            
            for dr, dc in directions:
                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

Complexity

• Time: O(rows × cols) - each cell visited exactly once
• Space: O(rows × cols) for visited array and queue
• Notes: Optimal time complexity, but uses extra space for tracking visited cells

Bucket Sort

Intuition The maximum possible distance from the center is bounded. We can use bucket sort where each bucket contains cells at a specific distance, eliminating the need for comparison-based sorting.

Steps

• Calculate the maximum possible distance from center
• Create buckets indexed by distance
• Place each cell in its corresponding distance bucket
• Concatenate all buckets in order

from typing import List

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:
        max_dist = max(rCenter, rows - 1 - rCenter) + max(cCenter, cols - 1 - cCenter)
        buckets = [[] for _ in range(max_dist + 1)]
        
        for r in range(rows):
            for c in range(cols):
                dist = abs(r - rCenter) + abs(c - cCenter)
                buckets[dist].append([r, c])
        
        result = []
        for bucket in buckets:
            result.extend(bucket)
        
        return result

Complexity

• Time: O(rows × cols) - linear time without sorting
• Space: O(rows × cols) for buckets
• Notes: Optimal approach with linear time complexity, leverages bounded distance range