Prerequisites: Matrix, BFS.
Problem: Given is a N x M binary matrix, for each cell find its distance from the nearest 0. Distance between vertically or horizontally adjacent cells is 1.
Solution Approach:
We can solve this problem using BFS in the given matrix.
Solution processes the given binary matrix to compute the distance of each cell from the nearest 0. We can initialize a queue to store the positions of cells containing 0s. Then, iterate through each cell of the matrix. If a cell contains a 0, its position is added to the queue, and its value is set to 0. If a cell contains a 1, its value is set to -1, indicating that it needs to be processed. Then inside the BFS loop, we dequeue cells from the queue and examines their neighbors in the four cardinal directions. For each neighboring cell with a value of -1 (indicating it hasn’t been processed), the function updates its value to the distance from the nearest 0 and adds its position to the queue for further processing. This process continues until the queue is empty, and all cells have been processed.
Time Complexity: O(N * M), as we might need to process entire matrix in worst case.
Space Complexity: O(N * M), as we might need to store entire cells in the BFS queue.