Matrix Cells in Distance Order

Problem Description

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. The distance between two cells (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|.

Key Insights

• The problem requires calculating the Manhattan distance from a center cell to all other cells in a matrix.
• The output should contain all cell coordinates sorted by their distance from the center cell.
• The distance calculation can be efficiently done using a simple loop iterating through all matrix coordinates.
• Any order of coordinates that maintains the distance condition is acceptable.

Space and Time Complexity

Time Complexity: O(rows * cols)
Space Complexity: O(rows * cols)

Solution

To solve the problem, we can follow these steps:

1. Create a list to store the coordinates of each cell in the matrix.
2. Use nested loops to iterate through each cell in the matrix and compute its distance from the center cell (rCenter, cCenter).
3. Store each cell's coordinates along with its distance in a list of tuples.
4. Sort the list of tuples based on the distance.
5. Extract and return the sorted cell coordinates.

The main data structures used are lists to store the coordinates and tuples to pair each coordinate with its corresponding distance.

Code Solutions