Domain 1EasyCORE

Matrix Cells in Distance Order

The problem requires sorting all cells in an `R x C` matrix based on their Manhattan distance from a given cell `(r0, c0)`. The Manhattan distance between two points `(r1, c1)` and `(r2, c2)` is calculated as `|r1 - r2| + |c1 - c2|`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Sort

1030. Matrix Cells in Distance Order

Model: qwen2.5-coder:14b
Topics: Sort
FAANG asked: 0
Acceptance rate: 68.2%


Problem Breakdown

The problem requires sorting all cells in an R x C matrix based on their Manhattan distance from a given cell (r0, c0). The Manhattan distance between two points (r1, c1) and (r2, c2) is calculated as |r1 - r2| + |c1 - c2|.

Inputs:

  • R: Number of rows in the matrix.
  • C: Number of columns in the matrix.
  • r0, c0: Coordinates of the reference cell from which distances are measured.

Outputs:

  • A list of coordinates sorted by their Manhattan distance from (r0, c0).

Implicit Constraints/Edge Cases:

  • The matrix can be as large as 100x100.
  • All indices are within valid bounds.
  • The reference cell (r0, c0) is always a valid cell in the matrix.

Intuition

A brute-force approach would involve calculating the Manhattan distance for each cell and then sorting the cells based on these distances. This approach has a time complexity of O(R * C * log(R * C)) due to the sorting step, which is acceptable given the constraints.

However, we can optimize this by using a bucket sort-like approach. We first group all cells by their Manhattan distance from (r0, c0). Since the maximum possible distance in a 100x100 matrix is 200, we can use an array of lists to store cells grouped by their distances. This reduces the complexity of sorting and allows us to directly concatenate the lists in order.

Approach

  1. Initialize Buckets: Create an array of lists where each index represents a possible Manhattan distance.
  2. Populate Buckets: Iterate through all cells (r, c) in the matrix and calculate their Manhattan distance from (r0, c0). Append each cell to the corresponding bucket based on its distance.
  3. Concatenate Buckets: Concatenate all lists in the buckets array to get the final sorted list of cells.

Complexity Analysis

  • Time Complexity: O(R * C) because we iterate through all cells once and perform constant-time operations for each cell.
  • Space Complexity: O(R * C) due to the storage required for the buckets array.

Solution

def allCellsDistOrder(R, C, r0, c0):
    # Initialize buckets for distances from 0 to R+C-2
    buckets = [[] for _ in range(R + C - 1)]
    
    # Populate buckets based on Manhattan distance
    for r in range(R):
        for c in range(C):
            distance = abs(r - r0) + abs(c - c0)
            buckets[distance].append([r, c])
    
    # Concatenate all cells from the buckets
    result = []
    for bucket in buckets:
        result.extend(bucket)
    
    return result

# Example usage:
print(allCellsDistOrder(1, 2, 0, 0))  # Output: [[0,0],[0,1]]
print(allCellsDistOrder(2, 2, 0, 1))  # Output: [[0,1],[0,0],[1,1],[1,0]]
print(allCellsDistOrder(2, 3, 1, 2))  # Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]

Edge Cases Handled

  • Single Cell Matrix: If R = 1 and C = 1, the output will be [[0,0]].
  • Reference Cell at Corners: The algorithm handles cases where (r0, c0) is at a corner of the matrix.
  • Uniform Distance Cells: If multiple cells have the same distance from (r0, c0), they are grouped together and concatenated in any order.