Leetcode – Matrix Cells in Distance Order Solution

Spread the love

The problem of “Matrix Cells in Distance Order” from Leetcode is a fascinating study into matrix manipulations and algorithmic efficiencies. This challenge pushes one to think spatially and to consider the distances between cells in a structured manner. This article will provide a deep dive into the problem’s statement, its implications, potential solution avenues, and Pythonic implementations.


  1. Problem Statement
  2. The Essence of the Problem
  3. Solution Approaches
  4. Python Implementations
  5. Testing the Solution
  6. Final Thoughts

1. Problem Statement:

You are given four integers: R, C, r0, and c0. We are required to return the coordinates of all cells in a R x C matrix, sorted by their distance from the cell (r0, c0) where the distance is calculated using the Manhattan distance (not the traditional Euclidean distance).


Input: R = 1, C = 2, r0 = 0, c0 = 0
Output: [[0,0],[0,1]]

2. The Essence of the Problem:

The challenge is essentially a sorting problem but not in the traditional sense of sorting numbers. Instead, we’re sorting matrix cells based on their distance to a given cell.

3. Solution Approaches:

  1. Brute-force Approach: Calculate the Manhattan distance for each cell in the matrix to (r0, c0) and then sort based on this distance.
  2. Bucket Sort Approach: Since we know the maximum possible distance in advance, we can make use of bucket sort for a more efficient solution.

4. Python Implementations:

1. Brute-force Approach:

def allCellsDistOrder(R: int, C: int, r0: int, c0: int):
    # Calculate the Manhattan distance
    def distance(r1, c1, r2, c2):
        return abs(r1 - r2) + abs(c1 - c2)

    # List all cells
    cells = [(r, c) for r in range(R) for c in range(C)]
    # Sort cells by their distance to (r0, c0)
    cells.sort(key=lambda x: distance(r0, c0, x[0], x[1]))

    return cells

2. Bucket Sort Approach:

def allCellsDistOrderBucket(R: int, C: int, r0: int, c0: int):
    # Calculate the Manhattan distance
    def distance(r1, c1, r2, c2):
        return abs(r1 - r2) + abs(c1 - c2)

    # The maximum possible distance is R+C-2, so create buckets for each distance
    buckets = [[] for _ in range(R + C - 1)]

    # Place cells in appropriate buckets based on their distance to (r0, c0)
    for r in range(R):
        for c in range(C):
            d = distance(r0, c0, r, c)
            buckets[d].append([r, c])

    # Flatten the list of buckets
    return [cell for bucket in buckets for cell in bucket]

This bucket sort approach optimizes the sorting step, resulting in a more efficient solution compared to the brute-force method.

5. Testing the Solution:

After implementation, it’s crucial to test the solution for correctness:

print(allCellsDistOrder(1, 2, 0, 0))  # Expected output: [[0,0],[0,1]]
print(allCellsDistOrderBucket(1, 2, 0, 0))  # Expected output: [[0,0],[0,1]]

print(allCellsDistOrder(2, 3, 1, 2))  # Possible output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
print(allCellsDistOrderBucket(2, 3, 1, 2))  # Possible output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]

6. Final Thoughts:

The “Matrix Cells in Distance Order” problem serves as an excellent example of the power of optimized sorting techniques in solving computational problems. While a brute-force approach provides an intuitive understanding, the optimized bucket sort method showcases the efficiency gains possible with more advanced algorithms.

Leave a Reply