Problem Statement:
You are given a binary matrix of size n x m, where each cell contains either a 0 or a 1. Your task is to find the distance of the nearest cell having 1 for each cell that contains 0. The distance between two adjacent cells is 1.
- If a cell contains
1, its distance is0. - For cells containing
0, the distance is defined as the shortest path from that cell to the nearest1.
The result should be a matrix where each cell contains its distance to the nearest 1.
Input:
- A binary matrix
gridof sizen x m(wherenandmare the number of rows and columns respectively).
Output:
- A matrix of the same size where each element contains the minimum distance to the nearest
1.
Examples
Example 1:
Input: grid = [
[0, 1, 0],
[0, 0, 1],
[1, 0, 0]
]
Output: result = [
[1, 0, 1],
[1, 1, 0],
[0, 1, 1]
]
Explanation:
For cell (0, 0), the nearest 1 is at (0, 1), so the distance is 1.
For cell (0, 2), the nearest 1 is at (1, 2), so the distance is 1.
For cell (1, 1), the nearest 1 is at (1, 2), so the distance is 1.
For cell (2, 1), the nearest 1 is at (2, 0), so the distance is 1.Example 2:
Input: grid = [
[1, 0, 0],
[0, 0, 0],
[0, 0, 1]
]
Output: result = [
[0, 1, 2],
[1, 2, 1],
[2, 1, 0]
]
Explanation:
For cell (0, 1), the nearest 1 is at (0, 0), so the distance is 1.
For cell (1, 0), the nearest 1 is at (0, 0), so the distance is 1.
For cell (2, 1), the nearest 1 is at (2, 2), so the distance is 1.Different Approaches
1️⃣ BFS (Breadth-First Search)
Intuition:
To find the nearest 1 in the grid for each cell, the breadth-first search algorithm will come in handy. BFS will take a step from cells containing 1 and will reach out to all zeros that are at a distance of one.
It can be said that the nearest 1 to the 0s is at a distance of one. Again if another step is taken, the next set of zeros will be found, and for these zeros, 1 is at a distance of two. Continuing the same, all the cells having 0 can be reached.
Why using BFS and not DFS?
BFS ensures that the first time we reach a cell, we do so via the shortest path. Checking neighbors and updating distances ensures we explore all possible paths systematically.
Approach:
- Create two matrices: one for keeping track of visited cells and another for storing distances. Use a queue to facilitate the Breadth-First Search (BFS).
- Traverse the entire grid. For each cell that contains a '1', mark it as visited, set its distance to 0, and add it to the queue with a step count of 0.
- While the queue is not empty, repeat the following steps:
- Get the front element, which provides the current cell coordinates and the number of steps taken to reach it. Update the distance matrix with the current step count for the current cell.
- Check the four neighboring cells (up, down, left, right). For each neighbor, if it is within grid boundaries and has not been visited, mark it as visited, increment the step count by 1, and push the neighbor with the updated step count in the queue.
- After the BFS traversal completes, the distance matrix will have the shortest distance to the nearest '1' for each cell in the grid. Return this matrix as the result.
Dry Run:
Initialization:
Input: grid =
0 1 2
+-----+-----+-----+
0 | 0 | 0 | 0 |
+-----+-----+-----+
1 | 0 | 1 | 0 |
+-----+-----+-----+
2 | 1 | 0 | 1 |
+-----+-----+-----+
| |
| |
| |
| |
| |
| |
| |
| | it will store in the format
+------------+ {{row, column}, distance}
queue
0 1 2
+-----+-----+-----+
0 | | | |
+-----+-----+-----+
1 | | | |
+-----+-----+-----+
2 | | | |
+-----+-----+-----+
distance matrix (ans)
0 1 2
+-----+-----+-----+
0 | 0 | 0 | 0 |
+-----+-----+-----+
1 | 0 | 0 | 0 |
+-----+-----+-----+
2 | 0 | 0 | 0 |
+-----+-----+-----+
visited matrixEnqueue all cells with value 1, and mark them visited:
grid =
0 1 2
+-----+-----+-----+
0 | 0 | 0 | 0 |
+-----+-----+-----+
1 | 0 |[ 1 ]| 0 |
+-----+-----+-----+
2 |[ 1 ]| 0 |[ 1 ]|
+-----+-----+-----+
| |
| |
| |
| |
| |
|{(2, 2), 0} |
|{(2, 0), 0} |
|{(1, 1), 0} |
+------------+
queue
0 1 2
+-----+-----+-----+
0 | 0 | 0 | 0 |
+-----+-----+-----+
1 | 0 | 1 | 0 |
+-----+-----+-----+
2 | 1 | 0 | 1 |
+-----+-----+-----+
visited matrix
0 1 2
+-----+-----+-----+
0 | | | |
+-----+-----+-----+
1 | | | |
+-----+-----+-----+
2 | | | |
+-----+-----+-----+
distance matrix (ans)Process while queue is not empty:
Iteration 1:
| |
| |
| |
| |
| |
|{(2, 2), 0} |
|{(2, 0), 0} |
+------------+
queue
front = {(1, 1), 0} -> {{row, column}, distance}
update its distance in the distance matrix
0 1 2
+-----+-----+-----+
0 | | | |
+-----+-----+-----+
1 | | 0 | |
+-----+-----+-----+
2 | | | |
+-----+-----+-----+
distance matrix (ans)
Process its adjacent direction neighbors,
Enqueue them if they are valid, not visited yet
and have value 0.
So, the neighbors of (1, 1) are:
(0, 1), (1, 0), (2, 1) and (1, 2)
Enqueue them with distance + 1, mark them visited.
queue will be like this after this step:
| |
|{(1, 0), 1} |
|{(2, 1), 1} |
|{(1, 2), 1} |
|{(0, 1), 1} |
|{(2, 2), 0} |
|{(2, 0), 0} | <-- front
+------------+
queue
visted matrix would be as follow:
0 1 2
+-----+-----+-----+
0 | 0 | 1 | 0 |
+-----+-----+-----+
1 | 1 | 1 | 1 |
+-----+-----+-----+
2 | 1 | 1 | 1 |
+-----+-----+-----+
visited matrix
Iteration 2:
| |
|{(1, 0), 1} |
|{(2, 1), 1} |
|{(1, 2), 1} |
|{(0, 1), 1} |
|{(2, 2), 0} |
+------------+
queue
front = {(2, 0), 0} -> {{row, column}, distance}
update its distance in the distance matrix
0 1 2
+-----+-----+-----+
0 | | | |
+-----+-----+-----+
1 | | 0 | |
+-----+-----+-----+
2 | 0 | | |
+-----+-----+-----+
distance matrix (ans)
Process its adjacent direction neighbors,
Enqueue them if they are valid, not visited yet
and have value 0.
So, the neighbors of (2, 0) are:
(1, 0), (2, 1)
and they are already visited.
queue will be like this after this step:
| |
|{(1, 0), 1} |
|{(2, 1), 1} |
|{(1, 2), 1} |
|{(0, 1), 1} |
|{(2, 2), 0} | <-- front
+------------+
queue
visted matrix would be as follow:
0 1 2
+-----+-----+-----+
0 | 0 | 1 | 0 |
+-----+-----+-----+
1 | 1 | 1 | 1 |
+-----+-----+-----+
2 | 1 | 1 | 1 |
+-----+-----+-----+
visited matrix
Iteration 3:
| |
|{(1, 0), 1} |
|{(2, 1), 1} |
|{(1, 2), 1} |
|{(0, 1), 1} |
+------------+
queue
front = {(2, 2), 0} -> {{row, column}, distance}
update its distance in the distance matrix
0 1 2
+-----+-----+-----+
0 | | | |
+-----+-----+-----+
1 | | 0 | |
+-----+-----+-----+
2 | 0 | | 0 |
+-----+-----+-----+
distance matrix (ans)
Process its adjacent direction neighbors,
Enqueue them if they are valid, not visited yet
and have value 0.
So, the neighbors of (2, 0) are:
(1, 2), (2, 1)
and they are already visited.
queue will be like this after this step:
| |
|{(1, 0), 1} |
|{(2, 1), 1} |
|{(1, 2), 1} |
|{(0, 1), 1} | <-- front
+------------+
queue
visted matrix would be as follow:
0 1 2
+-----+-----+-----+
0 | 0 | 1 | 0 |
+-----+-----+-----+
1 | 1 | 1 | 1 |
+-----+-----+-----+
2 | 1 | 1 | 1 |
+-----+-----+-----+
visited matrix
Iteration 4:
| |
|{(1, 0), 1} |
|{(2, 1), 1} |
|{(1, 2), 1} |
+------------+
queue
front = {(0, 1), 0} -> {{row, column}, distance}
update its distance in the distance matrix
0 1 2
+-----+-----+-----+
0 | | 1 | |
+-----+-----+-----+
1 | | 0 | |
+-----+-----+-----+
2 | 0 | | 0 |
+-----+-----+-----+
distance matrix (ans)
Process its adjacent direction neighbors,
Enqueue them if they are valid, not visited yet
and have value 0.
So, the neighbors of (0, 1) are:
(0, 0), (0, 2)
enqueue them with distance + 1 and mark
them visited.
queue will be like this after this step:
| |
|{(0, 2), 2} |
|{(0, 0), 2} |
|{(1, 0), 1} |
|{(2, 1), 1} |
|{(1, 2), 1} | <-- front
+------------+
queue
visted matrix would be as follow:
0 1 2
+-----+-----+-----+
0 | 1 | 1 | 1 |
+-----+-----+-----+
1 | 1 | 1 | 1 |
+-----+-----+-----+
2 | 1 | 1 | 1 |
+-----+-----+-----+
visited matrix
Iteration 5:
Keep doing it until the que is empty.Return the distance matrix:
At last return the distance matrix
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// DelRow and delCol for neighbors
vector<int> delRow = {-1, 0, 1, 0};
vector<int> delCol = {0, 1, 0, -1};
/* Helper Function to check if a
cell is within boundaries */
bool isValid(int &i, int &j,
int &n, int &m) {
// Return false if cell is invalid
if(i < 0 || i >= n) return false;
if(j < 0 || j >= m) return false;
// Return true if cell is valid
return true;
}
public:
/* Function to find the distance of the
nearest 1 in the grid for each cell. */
vector<vector<int>>nearest(vector<vector<int>>grid) {
// Determine the dimensions
int n = grid.size();
int m = grid[0].size();
// visited and distance matrix
vector<vector<int>> vis(n, vector<int>(m, 0));
vector<vector<int>> dist(n, vector<int>(m, 0));
// Queue to store the pair {coordinates, steps}
queue<pair<pair<int,int>, int>> q;
// Traverse the matrix
for(int i=0; i < n; i++) {
for(int j=0; j < m; j++) {
// Start BFS if cell contains 1
if(grid[i][j] == 1) {
q.push({{i,j}, 0});
vis[i][j] = 1;
}
else {
// mark unvisited
vis[i][j] = 0;
}
}
}
// Traverse till queue becomes empty
while(!q.empty()) {
// Determine the top of queue
auto it = q.front();
q.pop();
// Determine the coordinates of cell
int row = it.first.first;
int col = it.first.second;
// Get the steps
int steps = it.second;
// Update the distance matrix
dist[row][col] = steps;
// Traverse the 4 neighbours
for(int i = 0;i<4;i++) {
// Coordinates of new cell
int nRow = row + delRow[i];
int nCol = col + delCol[i];
// Check for valid, unvisited cell
if(isValid(nRow, nCol, n, m)
&& vis[nRow][nCol] == 0) {
// Mark the cell as visited
vis[nRow][nCol] = 1;
q.push({{nRow, nCol}, steps+1});
}
}
}
// return distance matrix
return dist;
}
};
int main() {
vector<vector<int>> grid = {
{0, 1, 1, 0},
{1, 1, 0, 0},
{0, 0, 1, 1}
};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to find the distance of the
nearest 1 in the grid for each cell. */
vector<vector<int>> ans = sol.nearest(grid);
int n = ans.size();
int m = ans[0].size();
// Output
cout << "The distance of the nearest 1 in the grid for each cell is: " << endl;
for(int i=0; i < n; i++) {
for(int j=0; j < m; j++) {
cout << ans[i][j] << " ";
}
cout << endl;
}
return 0;
}Complexity Analysis:
- Time Complexity:
O(N*M)(where N and M are the dimensions of grid)- For the worst case, the BFS function will be called for (
N x M) nodes, and for every node, we are traversing for 4 neighbors, so it will takeO(N x M x 4)time.
- For the worst case, the BFS function will be called for (
- Space Complexity:
O(N*M)The visited array and distance matrix will takeO(N*M)space each, and the queue will store at maximum ofO(N*M)cells (in case of grid having all cells as 1).