Approaches To Problem Solving #18 (BFS | 2-D Matrix)
Problem: Given a 2-D list of integers containing 1s and 0s. Return a 2-D matrix representing the Manhattan distance of the current cell from the nearest 0 cell. It can be assumed that at least one 0 exists in the matrix.
Let us consider an example to understand what we are required to do.
We can explain the above example as follows,
We can identify the given matrix as a graph, with all the cells of the matrix depicting the nodes in the graph. Since, we are dealing with manhattan distances, the iterations from one node to the other can only be made from one cell to an adjacent cell.
As we are dealing with finding the nearest zero for every cell in the given matrix, we can safely assume that we are supposed to find the shortest distance of all cells from some cell containing a value of 0.
We know that the cost of iteration from one cell to another is constant (i.e., 1). Hence, we can use a standard Breadth First Search to figure out the shortest distances that we seek.
Which cell should we start our iterations from?
Since we can have multiple 0 values in our matrix and all of them can act as the source node, we can use Multi-source BFS to solve this problem.
Approach : We iterate over the matrix and push all the cells containing 0 in them to a queue. We keep popping the front element of the queue, keep pushing the adjacent element to the queue and updating the minimum distances for each cell from the source cells.
We keep an answer matrix and update the answers for each cell by using the above method i.e., BFS. When we are done with all the cells, the answer matrix obtained is what we return as our solution.
The time complexity for this solution is O(N * M), where ’N’ is the number of rows and ‘M’ is the number of columns in the matrix.
In our next article, one of the problems that we are going to discuss is given below,
Problem : Given a binary tree root, return the top view of the tree, sorted left to right.
We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Multi-source BFS and 2-D matrices further!
We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.
For hugs and bugs, please comment down below. Till then.. Happy Coding!
This is the 18th article of the “Approaches To Problem Solving” series.
More such posts can be found at :-
