Distance From Every Cell to the Nearest Empty Slot
Solve this ProblemYou are given a grid of 0s and 1s containing at least one 0. For every cell, find the number of steps needed to reach the nearest cell that holds 0, moving up, down, left or right one cell at a time. Return the grid of these distances.
Measuring from each cell to every zero works but is slow. A breadth-first search that starts from all zeros simultaneously computes every distance in a single sweep.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ rows, cols ≤ 12; grid[r][c] is 0 (an empty slot) or 1 (an occupied slot); the grid contains at least one 0 - ◆
You can move between cells that share a side (up, down, left, right); every step costs 1 and every cell can be entered - ◆
For every cell, compute the number of steps to the nearest cell holding 0 (0 for the empty slots themselves) - ◆
Return the grid of distances (same size as the input)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Compare Every Cell With Every Empty Slot
BruteBecause every cell can be entered and each step costs 1, the number of steps between two cells is simply their Manhattan distance |Δrow| + |Δcol|. So for every cell, scan the whole grid for the cells holding 0 and keep the smallest such distance. It needs no graph search at all, but every one of the R·C cells scans all R·C cells: O((R·C)²) time.
O((R·C)²)O(1) extra1class Solution {
2 public int[][] nearestZero(int[][] grid) {
3 int rows = grid.length, cols = grid[0].length;
4 int[][] dist = new int[rows][cols];
5 for (int r = 0; r < rows; r++) {
6 for (int c = 0; c < cols; c++) {
7 int best = Integer.MAX_VALUE;
8 for (int zr = 0; zr < rows; zr++) {
9 for (int zc = 0; zc < cols; zc++) {
10 if (grid[zr][zc] == 0) {
11 best = Math.min(best, Math.abs(r - zr) + Math.abs(c - zc));
12 }
13 }
14 }
15 dist[r][c] = best;
16 }
17 }
18 return dist;
19 }
20}Optimal — Breadth-First Search Started From All the Zeros at Once
OptimalTurn the question around: instead of searching FROM every cell for a zero, search from all the zeros at once. Give the zero cells distance 0 and put them in a queue; every other cell starts as "unknown" (-1). Take a cell from the queue; each of its neighbours whose distance is still unknown gets that cell's distance + 1 and joins the queue. Because a breadth-first search reaches cells in order of increasing distance, the first time a cell is reached is by a shortest route from its nearest zero. Every cell is queued once: O(R·C).
O(R·C)O(R·C)1class Solution {
2 public int[][] nearestZero(int[][] grid) {
3 int rows = grid.length, cols = grid[0].length;
4 int[] dr = {1, -1, 0, 0};
5 int[] dc = {0, 0, 1, -1};
6 int[][] dist = new int[rows][cols];
7 Deque<int[]> queue = new ArrayDeque<>();
8 for (int r = 0; r < rows; r++) {
9 for (int c = 0; c < cols; c++) {
10 if (grid[r][c] == 0) {
11 dist[r][c] = 0;
12 queue.add(new int[]{r, c});
13 } else {
14 dist[r][c] = -1;
15 }
16 }
17 }
18 while (!queue.isEmpty()) {
19 int[] cell = queue.poll();
20 for (int d = 0; d < 4; d++) {
21 int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
22 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && dist[nr][nc] == -1) {
23 dist[nr][nc] = dist[cell[0]][cell[1]] + 1;
24 queue.add(new int[]{nr, nc});
25 }
26 }
27 }
28 return dist;
29 }
30}