28. Distance of Nearest Cell Having 1
✅ GFG solution to the Distance of Nearest Cell Having 1 problem: find minimum distance to nearest 1 for every cell using multi-source BFS technique. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
You are given a binary grid grid[][], where each cell contains either 0 or 1. Your task is to find the distance of the nearest 1 for every cell in the grid.
The distance between two cells (i1, j1) and (i2, j2) is calculated as |i1 - i2| + |j1 - j2| (Manhattan distance). You need to return a matrix of the same size, where each cell (i, j) contains the minimum distance from grid[i][j] to the nearest cell having value 1.
📘 Examples
Example 1
Input: grid[][] = [[0, 1, 1, 0],
[1, 1, 0, 0],
[0, 0, 1, 1]]
Output: [[1, 0, 0, 1],
[0, 0, 1, 1],
[1, 1, 0, 0]]
Explanation: 0's at (0,0), (0,3), (1,2), (1,3), (2,0) and (2,1) are at a distance
of 1 from 1's at (0,1), (0,2), (0,2), (2,3), (1,0) and (1,1) respectively.Example 2
Input: grid[][] = [[1, 0, 1],
[1, 1, 0],
[1, 0, 0]]
Output: [[0, 1, 0],
[0, 0, 1],
[0, 1, 2]]
Explanation: 0's at (0,1), (1,2), (2,1) and (2,2) are at a distance of 1, 1, 1
and 2 from 1's at (0,0), (0,2), (2,0) and (1,1) respectively.🔒 Constraints
$1 \le \text{grid.size()} \le 200$
$1 \le \text{grid[0].size()} \le 200$
✅ My Approach
The optimal approach uses Multi-Source BFS to efficiently compute distances from all cells containing 1 simultaneously:
Multi-Source BFS
Initialize Distance Matrix:
Create a distance matrix initialized with -1 (unvisited marker).
Use a queue to store coordinates of cells.
Mark All Source Cells:
Traverse the entire grid to find all cells with value 1.
Set their distance to 0 and add them to the queue.
These act as multiple sources for BFS.
BFS Traversal:
Process each cell from the queue in level-order fashion.
Explore all 4 adjacent directions (up, down, left, right).
For each unvisited neighbor, calculate distance as current cell's distance + 1.
Mark the neighbor as visited and add to queue.
Simultaneous Propagation:
All cells with 1 propagate distances simultaneously.
This ensures each cell gets the minimum distance to any nearest 1.
Return Result:
The distance matrix contains minimum distances for all cells.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n × m), where n is the number of rows and m is the number of columns. Each cell is visited exactly once during BFS traversal, and for each cell, we check at most 4 neighbors.
Expected Auxiliary Space Complexity: O(n × m), as we use a queue that can hold all cells in the worst case, and a distance matrix of the same size as the input grid.
🧑💻 Code (C++)
class Solution {
public:
vector<vector<int>> nearest(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> dist(n, vector<int>(m, -1));
queue<pair<int, int>> q;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (grid[i][j] == 1) {
dist[i][j] = 0;
q.push({i, j});
}
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
}
return dist;
}
};☕ Code (Java)
class Solution {
public ArrayList<ArrayList<Integer>> nearest(int[][] grid) {
int n = grid.length, m = grid[0].length;
ArrayList<ArrayList<Integer>> dist = new ArrayList<>();
Queue<int[]> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
dist.add(new ArrayList<>());
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1) {
dist.get(i).add(0);
q.offer(new int[]{i, j});
} else dist.get(i).add(-1);
}
}
int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
while (!q.isEmpty()) {
int[] cur = q.poll();
int x = cur[0], y = cur[1];
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist.get(nx).get(ny) == -1) {
dist.get(nx).set(ny, dist.get(x).get(y) + 1);
q.offer(new int[]{nx, ny});
}
}
}
return dist;
}
}🐍 Code (Python)
class Solution:
def nearest(self, grid):
n, m = len(grid), len(grid[0])
dist = [[-1] * m for _ in range(n)]
q = []
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
dist[i][j] = 0
q.append((i, j))
dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
idx = 0
while idx < len(q):
x, y = q[idx]
idx += 1
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < m and dist[nx][ny] == -1:
dist[nx][ny] = dist[x][y] + 1
q.append((nx, ny))
return dist🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated