Stacks & QueuesProblem 32 of 38
Distance of nearest cell having 1 in a binary matrix
Problem Statement
Given a binary matrix of size m x n, find the distance of the nearest cell having 1 for each cell. The distance is calculated as the number of steps needed to reach from one cell to another (only 4-directional moves are allowed). If a cell itself contains 1, the distance is 0.
Example:
Input: grid = [[0, 0, 0, 1],
[0, 0, 1, 1],
[0, 1, 1, 0]]
Output: [[3, 2, 1, 0],
[2, 1, 0, 0],
[1, 0, 0, 1]]
Approach 1: Brute Force (BFS from each cell)
Intuition
For each cell containing 0, perform a BFS to find the nearest cell containing 1. The BFS will explore cells level by level, and the first 1 encountered gives the minimum distance.
Algorithm
- For each cell in the matrix:
- If cell contains 1, distance is 0
- If cell contains 0, run BFS to find nearest 1
- BFS explores all 4 directions at each level
- First 1 found is the nearest
java
import java.util.*;
public class NearestCell {
public static int bfsFromCell(int[][] grid, int startX, int startY) {
int m = grid.length;
int n = grid[0].length;
if (grid[startX][startY] == 1) return 0;
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>(); // {x, y, distance}
queue.offer(new int[]{startX, startY, 0});
visited[startX][startY] = true;
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int x = curr[0], y = curr[1], dist = curr[2];
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
if (grid[nx][ny] == 1) {
return dist + 1;
}
visited[nx][ny] = true;
queue.offer(new int[]{nx, ny, dist + 1});
}
}
}
return -1;
}
public static int[][] nearestCellBruteForce(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] result = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
result[i][j] = bfsFromCell(grid, i, j);
}
}
return result;
}
}Complexity Analysis
- Time Complexity: O((mn)^2) - BFS for each of mn cells
- Space Complexity: O(m*n) - visited array for each BFS
Approach 2: Optimal (Multi-source BFS from all 1s)
Intuition
Instead of BFS from each 0 to find the nearest 1, do BFS from all 1s simultaneously. This is multi-source BFS where all cells with 1 start at distance 0, and we expand outward.
Algorithm
- Initialize result matrix with infinity for 0 cells, 0 for 1 cells
- Add all cells with 1 to the queue
- BFS level by level:
- For each cell, update distance of adjacent cells
- Add unvisited cells to queue
- Each cell is visited exactly once
java
import java.util.*;
public class NearestCell {
public static int[][] nearestCell(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dist = new int[m][n];
Queue<int[]> queue = new LinkedList<>();
// Initialize distances and add all 1s to queue
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
dist[i][j] = 0;
queue.offer(new int[]{i, j});
} else {
dist[i][j] = Integer.MAX_VALUE;
}
}
}
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
// Multi-source BFS
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int x = curr[0], y = curr[1];
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && nx < m && ny >= 0 && ny < n
&& dist[nx][ny] > dist[x][y] + 1) {
dist[nx][ny] = dist[x][y] + 1;
queue.offer(new int[]{nx, ny});
}
}
}
return dist;
}
public static void main(String[] args) {
int[][] grid = {{0, 0, 0, 1},
{0, 0, 1, 1},
{0, 1, 1, 0}};
System.out.println("Input:");
for (int[] row : grid) {
System.out.println(Arrays.toString(row));
}
int[][] result = nearestCell(grid);
System.out.println("\nOutput:");
for (int[] row : result) {
System.out.println(Arrays.toString(row));
}
}
}Complexity Analysis
- Time Complexity: O(m*n) - each cell visited exactly once
- Space Complexity: O(m*n) - distance matrix and queue
Approach 3: 01-BFS / Distance with 0 Cells (LeetCode 542)
Intuition
This is also known as "01 Matrix" problem. We find distance from each 0 to nearest 1, but can be reframed as distance from each 1 to nearest 0 (inverted problem).
Algorithm
For LeetCode 542 variant (distance to nearest 0):
- Initialize 0 cells with distance 0
- Initialize 1 cells with infinity
- BFS from all 0 cells
java
import java.util.*;
public class NearestCell {
// LeetCode 542: Distance to nearest 0
public static int[][] updateMatrix(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int[][] dist = new int[m][n];
Queue<int[]> queue = new LinkedList<>();
// Initialize and add all 0s to queue
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0) {
dist[i][j] = 0;
queue.offer(new int[]{i, j});
} else {
dist[i][j] = Integer.MAX_VALUE;
}
}
}
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int x = curr[0], y = curr[1];
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && nx < m && ny >= 0 && ny < n
&& dist[nx][ny] > dist[x][y] + 1) {
dist[nx][ny] = dist[x][y] + 1;
queue.offer(new int[]{nx, ny});
}
}
}
return dist;
}
}Complexity Analysis
- Time Complexity: O(m*n) - each cell processed once
- Space Complexity: O(m*n) - for distance matrix and queue
Key Takeaways
- Multi-source BFS: Start from all source cells simultaneously
- Reverse Thinking: Instead of BFS from each 0 to find 1, BFS from all 1s
- Distance Propagation: BFS guarantees shortest distance
- Similar Problems: LeetCode 542 (01 Matrix), LeetCode 994 (Rotting Oranges)
- Grid Problems: Many grid-based distance problems use multi-source BFS
- Time complexity reduction from O((mn)^2) to O(mn) is significant