Understanding the Problem: Grid Distance and BFS

If you are tackling LeetCode 1030, you are asked to return the coordinates of all cells in a rows x cols matrix, sorted by their Manhattan distance from a specified center cell (rCenter, cCenter). The distance between two cells is the sum of their absolute row difference and column difference.

This is a classic algorithmic challenge that tests your ability to navigate 2D arrays and understand distance metrics. While sorting all points by distance takes O(N log N) time, leveraging Breadth-First Search (BFS) reduces this to a highly efficient O(N) linear time operation, where N is the total number of cells in the matrix.

Problem Statement

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

Examples

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

Optimized C++ BFS Solution

Below is the complete C++ algorithm implementation using a queue-based Breadth-First Search. We initialize a visited matrix to ensure no cell is processed twice and use a directions array to traverse the four cardinal neighbors (up, down, left, right) sequentially.

class Solution {
public:

    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {

        queue<pair<int,int>> q;        
        vector<vector<int>> result;

        vector<vector<bool>> visited( rows , vector<bool>(cols, false));        
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        q.push({rCenter, cCenter});
        visited[rCenter][cCenter] = true;

        while( !q.empty() ){
            int size = q.size();
            while(size > 0){
                auto [currentRow, currentCol] = q.front();              
                result.push_back({currentRow, currentCol});

                q.pop();
                for (auto [dr, dc] : directions) {
                    int newRow = currentRow + dr;
                    int newCol = currentCol + dc;


                    if( newRow >= 0 && newRow < rows && newCol >=0 && newCol < cols 
                        && !visited[newRow][newCol]){                        
                        q.push({newRow,newCol});
                        visited[newRow][newCol] = true;
                    }
                }
                size--;
            }

        }
        return result;
        
    }
};

Algorithmic Complexity Analysis

Understanding the runtime bounds of this algorithm is crucial for technical interviews.

• Time Complexity: O(rows * cols). The Breadth-First Search guarantees that every cell in the matrix is enqueued and dequeued exactly once. Checking the neighbors takes constant time O(1). Thus, the time complexity scales linearly with the total grid size.
• Space Complexity: O(rows * cols). We use extra memory for the queue, the boolean visited matrix, and the resulting vector containing all coordinates. All of these require memory proportional to the total number of cells.

Frequently Asked Questions

What is the time complexity of this BFS approach for Matrix Cells in Distance Order?

The time complexity is O(rows * cols) because the Breadth-First Search (BFS) algorithm visits each cell in the grid exactly once, processing it in constant time.

Why is Breadth-First Search (BFS) used for this LeetCode 1030 problem?

BFS naturally explores nodes level by level. In a grid, this ensures that we process cells in strictly increasing order of their distance from the starting center cell.

What is the space complexity of the solution?

The space complexity is O(rows * cols) required for the visited matrix, the BFS queue, and the result vector to store the coordinates of all cells.

Conclusion

Mastering distance-based matrix problems like LeetCode 1030 is essential for improving your algorithm design skills. By transitioning from a naive sorting approach to an optimized Breadth-First Search traversal, you ensure that your code runs as efficiently as possible in production environments. Practice similar grid search scenarios to deepen your understanding of dynamic programming and graph traversals.