{x}
blog image

Matrix Cells in Distance Order

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

 

Example 1:

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]

Example 2:

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 correct.

Example 3:

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

 

Constraints:

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

Solution Explanation:

This problem asks us to find the coordinates of all cells in a matrix, sorted by their distance from a given center cell. The distance is calculated using Manhattan distance (|r1 - r2| + |c1 - c2|).

The most efficient approach is using Breadth-First Search (BFS). BFS guarantees that cells closer to the center are visited and added to the result before cells further away.

Algorithm:

  1. Initialization:

    • Create a queue q and add the coordinates of the center cell (rCenter, cCenter).
    • Create a boolean matrix vis of the same size as the input matrix to track visited cells. Mark the center cell as visited.
    • Create a result list ans to store the coordinates.

  2. BFS Traversal:

    • While the queue is not empty:
      • Iterate through the current level of the queue (the number of elements currently in q).
      • For each cell (r, c) in the current level:
        • Add (r, c) to the result list ans.
        • Explore the four neighboring cells (up, down, left, right).
        • If a neighbor is within the matrix bounds and not yet visited:
          • Mark the neighbor as visited.
          • Add the neighbor to the queue.

  3. Return: Return the ans list containing the cell coordinates sorted by distance from the center.

Time Complexity Analysis:

  • Each cell in the matrix is visited exactly once.
  • The number of cells is rows * cols.
  • Therefore, the time complexity is O(rows * cols).

Space Complexity Analysis:

  • The queue q can hold at most rows * cols cells in the worst case (when all cells are visited).
  • The vis matrix has dimensions rows * cols.
  • The ans list also holds rows * cols cell coordinates.
  • Therefore, the space complexity is O(rows * cols).

Code Implementation (Python):

from collections import deque
 
class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:
        q = deque([[rCenter, cCenter]])
        vis = [[False] * cols for _ in range(rows)]
        vis[rCenter][cCenter] = True
        ans = []
        while q:
            for _ in range(len(q)):  # Process all cells at the current distance
                r, c = q.popleft()
                ans.append([r, c])
                for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: # Explore neighbors
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and not vis[nr][nc]:
                        vis[nr][nc] = True
                        q.append([nr, nc])
        return ans

The code in other languages (Java, C++, Go) follows the same algorithm, only differing in syntax and data structure implementations. The core logic of BFS and distance-based sorting remains the same.