☕ DSA Java Articles

Topics › Graphs › Problems on BFS/DFS

Distance of nearest cell having one

Medium TUF ID 530 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an n × m grid containing only 0s and 1s. For every cell, find the distance to the nearest cell that contains a 1, where the distance between (i1, j1) and (i2, j2) is |i1 - i2| + |j1 - j2|. A cell that holds a 1 has distance 0. Return the grid of distances.

The GfG statement guarantees at least one 1. The code here also handles the degenerate grid with no 1 by returning -1 in every cell, so you can see how each method behaves.

Constraints: 1 ≤ n, m ≤ 500.

Example 1

grid = 0 1 1 0        answer = 1 0 0 1
       1 1 0 0                 0 0 1 1
       0 0 1 1                 1 1 0 0

Every 0 in this grid is next to some 1, so each one gets distance 1.

Example 2

grid = 1 0 1          answer = 0 1 0
       1 1 0                   0 0 1
       1 0 0                   0 1 2

The bottom-right cell is two steps from both (1, 1) and (0, 2).

The key observation: the grid has no walls, so the Manhattan distance between two cells is exactly the number of up, down, left and right steps on a shortest walk between them. That turns the problem into shortest paths in an unweighted grid graph, and shortest paths in unweighted graphs are what BFS computes. LeetCode’s “01 Matrix” is the same problem with the roles of 0 and 1 swapped.

Approach 1: Brute force

Intuition. Follow the definition. For each cell, look at every cell of the grid, and among those that hold a 1, keep the smallest Manhattan distance.

Algorithm.

  1. For each cell (i, j), set best = ∞.
  2. For each cell (r, c) with grid[r][c] == 1, update best = min(best, |i - r| + |j - c|).
  3. Store best (or -1 if no 1 exists).
static int[][] bruteForce(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    int[][] dist = new int[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int best = Integer.MAX_VALUE;
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < m; c++) {
                    if (grid[r][c] == 1) best = Math.min(best, Math.abs(i - r) + Math.abs(j - c));
                }
            }
            dist[i][j] = best == Integer.MAX_VALUE ? -1 : best;
        }
    }
    return dist;
}

Complexity. Time O((n·m)^2): every cell scans every cell. Space O(1) beyond the output.

For a 500 × 500 grid that is 6.25 × 10^10 operations. Running a separate BFS from every 0 would be no better. We need every cell’s answer from one pass.

Approach 2: Optimal, multi-source BFS

Intuition. Turn the question around. Instead of each cell searching outward for its nearest 1, let all the 1s spread outward at the same time, one step per round, like ripples from many stones dropped into a pond together. The first ripple to reach a cell comes from the nearest 1, and the round number when it arrives is the distance.

BFS does exactly this if we put every 1 into the queue at the start, all at distance 0. It helps to imagine an invisible extra vertex connected to every 1; a normal single-source BFS from it would put all the 1s in the first layer. BFS processes cells in order of non-decreasing distance, so the first time a cell is discovered, it is discovered along a shortest path from the closest source. That is why each cell is assigned exactly once and never corrected later.

The dist array does double duty: -1 means “not reached yet”, so it is also the visited marker.

Algorithm.

  1. Set dist = 0 and enqueue every cell holding 1; set dist = -1 everywhere else.
  2. Pop a cell; for each of its four neighbours inside the grid with dist == -1, set dist = dist[cell] + 1 and enqueue it.
  3. When the queue is empty, dist is the answer. Cells still at -1 were unreachable, which only happens when the grid has no 1.
static int[][] optimal(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    int[][] dist = new int[n][m];
    Deque<int[]> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) {
                dist[i][j] = 0;
                q.offer(new int[]{i, j});            // every 1 is a source at distance 0
            } else {
                dist[i][j] = -1;                     // -1 = not reached yet
            }
        }
    }
    int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
    while (!q.isEmpty()) {
        int[] cell = q.poll();
        for (int k = 0; k < 4; k++) {
            int r = cell[0] + dr[k], c = cell[1] + dc[k];
            if (r >= 0 && r < n && c >= 0 && c < m && dist[r][c] == -1) {
                dist[r][c] = dist[cell[0]][cell[1]] + 1;
                q.offer(new int[]{r, c});
            }
        }
    }
    return dist;
}

Dry run on Example 2, layer by layer:

layer cells assigned in this layer value
0 (0,0), (0,2), (1,0), (1,1), (2,0) 0
1 (0,1) from (0,0), (1,2) from (0,2), (2,1) from (1,1) 1
2 (2,2) from (1,2) 2

Cell (0,1) is also next to (1,1) and (0,2), but it was already assigned by (0,0) with the same value 1, so nothing changes.

Complexity. Time O(n·m): every cell enters the queue once and looks at four neighbours. Space O(n·m) for the queue in the worst case, for example when half the grid is 1.

Approach 3: Two dynamic-programming sweeps

Intuition. A different way to get linear time without a queue. A shortest walk from a cell to its nearest 1 never needs to go both up and down, or both left and right. So the nearest 1 sits in one of four quadrants, and the walk to it uses only two directions.

Why does that cover a 1 in the up-right quadrant? Say the 1 is at (r, c) with r < i and c > j. The cell (i, c) is directly below it, so the first pass already gave d[i][c] ≤ i - r. The second pass carries that value leftwards along row i, adding 1 per step, so d[i][j] ≤ (i - r) + (c - j). The down-left quadrant works the same way through the cell (r, j).

INF = n + m is larger than any real distance (n + m - 2 at most) and small enough that INF + 1 cannot overflow.

static int[][] twoPassDp(int[][] grid) {
    int n = grid.length, m = grid[0].length, INF = n + m;   // larger than any real distance
    int[][] d = new int[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) { d[i][j] = 0; continue; }
            d[i][j] = INF;
            if (i > 0) d[i][j] = Math.min(d[i][j], d[i - 1][j] + 1);      // best 1 reached from above
            if (j > 0) d[i][j] = Math.min(d[i][j], d[i][j - 1] + 1);      // best 1 reached from the left
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (i < n - 1) d[i][j] = Math.min(d[i][j], d[i + 1][j] + 1);  // from below
            if (j < m - 1) d[i][j] = Math.min(d[i][j], d[i][j + 1] + 1);  // from the right
        }
    }
    for (int[] row : d) {
        for (int j = 0; j < m; j++) if (row[j] >= INF) row[j] = -1;     // no 1 anywhere
    }
    return d;
}

Complexity. Time O(n·m) for two passes. Space O(1) besides the output grid, which makes this the leanest method; BFS is still the one to reach for when the grid has obstacles, because the quadrant argument breaks once walls force detours.

Edge cases and pitfalls