Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.Example 1:
Input:
0 0 0 0 1 0 0 0 0Output:
0 0 0 0 1 0 0 0 0
Example 2:
Input:
0 0 0 0 1 0 1 1 1Output:
0 0 0 0 1 0 1 2 1
Note:
Intuition
Do what the question says.
Algorithm
dist[i][j]=INT_MAX
for all {i,j}
cells.0
, dist[i][j]=0
,1
cell,0
, calculate its distance from current cell as abs(k-i)+abs(l-j)
.Complexity Analysis
Time complexity: .
Iterating over the entire matrix for each 1
in the matrix.
Space complexity: .
No extra space required than the vector<vector<int> > dist
Intuition
A better brute force:
Looking over the entire matrix appears wasteful and hence, we can use Breadth First Search(BFS) to limit the search to the nearest 0
found for each 1
. As soon as a 0
appears during the BFS, we know that the 0
is nearest, and hence, we move to the next 1
.
Think again:
But, in this approach, we will only be able to update the distance of one 1
using one BFS, which could in fact, result in slightly higher complexity than the Approach #1 brute force.
But hey,this could be optimised if we start the BFS from 0
s and thereby, updating the distances of all the 1
s in the path.
Algorithm
q
to maintain the queue of cells to be examined next.0
s to q
.0
cell is 0
and distance for each 1
is INT_MAX
, which is updated during the BFS.{i,j}
is smaller, we add {i,j}
to q
and update dist[i][j]
.Complexity analysis
Since, the new cells are added to the queue only if their current distance is greater than the calculated distance, cells are not likely to be added multiple times.
Space complexity: . Additional for queue than in Approach #1
Intuition
The distance of a cell from 0
can be calculated if we know the nearest distance for all the neighbours, in which case the distance is minimum distance of any neightbour + 1. And, instantly, the word come to mind DP!!
For each 1
, the minimum path to 0
can be in any direction. So, we need to check all the 4 direction. In one iteration from top to bottom, we can check left and top directions, and we need another iteration from bottom to top to check for right and bottom direction.
Algorithm
Complexity analysis
dist vector<vector<int> >
Analysis written by @abhinavbansal0.