Distance of Nearest Cell Having 1 in a Binary Grid

Problem Statement❯

Given a binary grid of size N x M, where each cell contains either a 0 or a 1, compute a matrix where each cell contains the distance to the nearest cell that has a value of 1.

Distance is measured in terms of the number of steps required to move from one cell to another in the four cardinal directions (up, down, left, right).

Examples❯

Input Grid	Output Grid	Description
[[0,0,0],[0,1,0],[0,0,0]]	[[2,1,2],[1,0,1],[2,1,2]]	Center 1 propagates distance outwards
[[1,0,0],[0,0,0],[0,0,0]]	[[0,1,2],[1,2,3],[2,3,4]]	Only top-left is 1, all others compute from it
[[0,0],[0,0]]	[[Infinity,Infinity],[Infinity,Infinity]]	No 1 present; can't compute distance
[[1,1],[1,1]]	[[0,0],[0,0]]	All cells are already 1
[[0]]	[[Infinity]]	Single cell 0, no 1 exists
[[1]]	[[0]]	Single cell 1, distance is 0

Visualization Player

Solution❯

Understanding the Problem

You are given a binary grid — a 2D matrix where each cell is either 0 or 1. Your task is to find, for every cell, the distance to the nearest cell that contains a 1. The distance is measured in number of steps to adjacent cells (up, down, left, right only — not diagonally).

This means that if you're standing on a 0, you want to know how far away the nearest 1 is, moving only in four directions. The output should be a new grid of the same size where each cell contains this distance value.

Step-by-Step Solution with Example

Step 1: Think in terms of distance spread

We can treat all cells with a 1 as starting points and spread outward using Breadth-First Search (BFS). This way, we fill in the nearest distance for each 0 based on how many steps it takes to reach the closest 1.

Step 2: Initialize the result and queue

Create a result matrix of the same size initialized with -1 or Infinity to indicate that we haven't found a distance yet. Also, create a queue and push all cells that already contain a 1 into it — these are our BFS starting points. Mark their distance as 0 in the result.

Step 3: Perform BFS from all 1s

Now we perform multi-source BFS. From each 1-cell in the queue, we explore its neighbors (up, down, left, right). If a neighboring cell hasn’t been visited yet, we set its distance to current distance + 1 and push it to the queue.

Step 4: Continue until all cells are processed

Repeat this process until the queue is empty. Each cell is guaranteed to be visited only once, and the first time it’s visited will be from the nearest 1. This ensures optimality (shortest path).

Step 5: Final result grid

The final result grid contains, for each cell, the minimum number of steps to the nearest 1.

Example:

Input Grid:
[
  [0, 0, 1],
  [0, 1, 0],
  [1, 0, 0]
]

Output Distance Grid:
[
  [2, 1, 0],
  [1, 0, 1],
  [0, 1, 2]
]

In this example, the 1s act as sources. The zeros take increasing values as we move away from the nearest 1. The cell [0,0] is 2 steps away from the nearest 1 — it could go down to [1,0] then right to [1,1].

Edge Cases

Case 1: All cells are 1

If every cell is a 1, then each cell is already at distance 0. The output will be a grid filled with zeros.

Case 2: No cell contains 1

If there are no 1s in the grid, we cannot compute distances. The output may remain as -1 or some sentinel value like Infinity, or depending on the problem constraints, return an empty grid or an error.

Case 3: Grid contains only one 1

If there is only one 1, the BFS will spread from that single point, and all other distances will be based on how far they are from that cell.

Case 4: Grid size is 1x1

With a single cell, either the output is 0 (if it is a 1) or it depends on whether any 1 exists — if not, it remains unresolvable.

Finally

This problem teaches an important application of Breadth-First Search from multiple sources. The key idea is to treat all 1s as starting points and let BFS naturally expand to fill in the shortest distance for each 0. This approach ensures both correctness and efficiency, making it ideal for large grids as well.

Algorithm Steps❯

Initialize a distance matrix with large values.
Create a queue and enqueue all cells with 1 (distance = 0).
While the queue is not empty:

Dequeue the front cell (i, j).
For each neighbor in 4 directions:

If neighbor is within bounds and has not been visited (or a shorter path is found),
Update its distance as distance[i][j] + 1 and enqueue it.

Return the final distance matrix.

Code

JavaScript

function nearest1Distance(grid) {
  const rows = grid.length, cols = grid[0].length;
  const distance = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
  const queue = [];
  const directions = [[1,0], [-1,0], [0,1], [0,-1]];

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 1) {
        distance[i][j] = 0;
        queue.push([i, j]);
      }
    }
  }

  while (queue.length > 0) {
    const [x, y] = queue.shift();
    for (const [dx, dy] of directions) {
      const nx = x + dx, ny = y + dy;
      if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && distance[nx][ny] > distance[x][y] + 1) {
        distance[nx][ny] = distance[x][y] + 1;
        queue.push([nx, ny]);
      }
    }
  }

  return distance;
}

const grid = [
  [0, 0, 0],
  [0, 1, 0],
  [0, 0, 0]
];

console.log("Distance of nearest 1 for each cell:", nearest1Distance(grid));

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(m × n)	Even in the best case where all cells are 1, we still traverse all cells to build the output matrix.
Average Case	O(m × n)	Each cell is visited at most once during the BFS, and every cell is processed to compute its minimum distance.
Worst Case	O(m × n)	In the worst case, we must traverse every cell and explore its neighbors, which is linear with respect to the number of cells in the grid.

Space Complexity❯

O(m × n)

Explanation: We use a queue for BFS and a distance matrix of the same size as the grid, leading to linear space usage.

⬅ Previous TopicDetect Cycle in an Undirected Graph using BFS

Next Topic ⮕Surrounded Regions in Matrix using Graph Traversal

Comments

Loading comments...