Distance of Nearest Cell Having 1 - Grid BFS

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).

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.

1. Initialize a distance matrix with large values.
2. Create a queue and enqueue all cells with 1 (distance = 0).
3. While the queue is not empty:
1. Dequeue the front cell (i, j).
2. For each neighbor in 4 directions:
1. If neighbor is within bounds and has not been visited (or a shorter path is found),
2. Update its distance as distance[i][j] + 1 and enqueue it.
4. Return the final distance matrix.

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

int queue[MAX * MAX][2], front = 0, rear = 0;

void enqueue(int x, int y) {
    queue[rear][0] = x;
    queue[rear][1] = y;
    rear++;
}

void dequeue(int* x, int* y) {
    *x = queue[front][0];
    *y = queue[front][1];
    front++;
}

int isEmpty() {
    return front == rear;
}

int main() {
    int grid[3][3] = {
        {0, 0, 0},
        {0, 1, 0},
        {0, 0, 0}
    };
    int dist[3][3];
    int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (grid[i][j] == 1) {
                dist[i][j] = 0;
                enqueue(i, j);
            } else {
                dist[i][j] = 9999;
            }
        }
    }

    while (!isEmpty()) {
        int x, y;
        dequeue(&x, &y);
        for (int d = 0; d < 4; d++) {
            int nx = x + dirs[d][0];
            int ny = y + dirs[d][1];
            if (nx >= 0 && ny >= 0 && nx < 3 && ny < 3 && dist[nx][ny] > dist[x][y] + 1) {
                dist[nx][ny] = dist[x][y] + 1;
                enqueue(nx, ny);
            }
        }
    }

    printf("Distance matrix:\n");
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", dist[i][j]);
        }
        printf("\n");
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    vector<vector<int>> grid = {
        {0, 0, 0},
        {0, 1, 0},
        {0, 0, 0}
    };

    int rows = grid.size(), cols = grid[0].size();
    vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX));
    queue<pair<int, int>> q;
    int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == 1) {
                dist[i][j] = 0;
                q.push({i, j});
            }
        }
    }

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (auto& d : dirs) {
            int nx = x + d[0], ny = y + d[1];
            if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && dist[nx][ny] > dist[x][y] + 1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }

    cout << "Distance matrix:" << endl;
    for (const auto& row : dist) {
        for (int d : row) cout << d << " ";
        cout << endl;
    }
    return 0;
}

from collections import deque

def nearest_1_distance(grid):
    rows, cols = len(grid), len(grid[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    q = deque()

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                dist[i][j] = 0
                q.append((i, j))

    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    while q:
        x, y = q.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and dist[nx][ny] > dist[x][y] + 1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))

    return dist

grid = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
]

result = nearest_1_distance(grid)
print("Distance matrix:")
for row in result:
    print(row)

import java.util.*;

public class NearestOneDistance {
    public static void main(String[] args) {
        int[][] grid = {
            {0, 0, 0},
            {0, 1, 0},
            {0, 0, 0}
        };
        int rows = grid.length, cols = grid[0].length;
        int[][] dist = new int[rows][cols];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        Queue<int[]> queue = new LinkedList<>();
        int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                    queue.offer(new int[]{i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int nx = cell[0] + d[0], ny = cell[1] + d[1];
                if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && dist[nx][ny] > dist[cell[0]][cell[1]] + 1) {
                    dist[nx][ny] = dist[cell[0]][cell[1]] + 1;
                    queue.offer(new int[]{nx, ny});
                }
            }
        }

        System.out.println("Distance matrix:");
        for (int[] row : dist) {
            for (int d : row) System.out.print(d + " ");
            System.out.println();
        }
    }
}

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));

package main

import (
	"fmt"
)

type Point struct {
	x, y int
}

func nearestOneDistance(grid [][]int) [][]int {
	rows := len(grid)
	cols := len(grid[0])
	dist := make([][]int, rows)
	for i := range dist {
		dist[i] = make([]int, cols)
		for j := range dist[i] {
			dist[i][j] = 1e9
		}
	}
	dirs := []Point{{1,0},{-1,0},{0,1},{0,-1}}
	queue := []Point{}

	for i := range grid {
		for j := range grid[i] {
			if grid[i][j] == 1 {
				dist[i][j] = 0
				queue = append(queue, Point{i,j})
			}
		}
	}

	for len(queue) > 0 {
		p := queue[0]
		queue = queue[1:]
		for _, d := range dirs {
			nx, ny := p.x + d.x, p.y + d.y
			if nx >= 0 && ny >= 0 && nx < rows && ny < cols && dist[nx][ny] > dist[p.x][p.y]+1 {
				dist[nx][ny] = dist[p.x][p.y] + 1
				queue = append(queue, Point{nx, ny})
			}
		}
	}

	return dist
}

func main() {
	grid := [][]int{
		{0, 0, 0},
		{0, 1, 0},
		{0, 0, 0},
	}
	result := nearestOneDistance(grid)
	for _, row := range result {
		fmt.Println(row)
	}
}

use std::collections::VecDeque;

fn main() {
    let grid = vec![
        vec![0, 0, 0],
        vec![0, 1, 0],
        vec![0, 0, 0],
    ];
    let rows = grid.len();
    let cols = grid[0].len();
    let mut dist = vec![vec![i32::MAX; cols]; rows];
    let mut queue = VecDeque::new();

    for i in 0..rows {
        for j in 0..cols {
            if grid[i][j] == 1 {
                dist[i][j] = 0;
                queue.push_back((i, j));
            }
        }
    }

    let directions = vec![(1,0), (-1,0), (0,1), (0,-1)];
    while let Some((x, y)) = queue.pop_front() {
        for (dx, dy) in &directions {
            let nx = x as isize + dx;
            let ny = y as isize + dy;
            if nx >= 0 && ny >= 0 && nx < rows as isize && ny < cols as isize {
                let (nx, ny) = (nx as usize, ny as usize);
                if dist[nx][ny] > dist[x][y] + 1 {
                    dist[nx][ny] = dist[x][y] + 1;
                    queue.push_back((nx, ny));
                }
            }
        }
    }

    for row in dist {
        println!("{:?}", row);
    }
}

fun main() {
    val grid = arrayOf(
        intArrayOf(0, 0, 0),
        intArrayOf(0, 1, 0),
        intArrayOf(0, 0, 0)
    )
    val rows = grid.size
    val cols = grid[0].size
    val dist = Array(rows) { IntArray(cols) { Int.MAX_VALUE } }
    val queue = ArrayDeque<Pair<Int, Int>>()
    val directions = arrayOf(Pair(1,0), Pair(-1,0), Pair(0,1), Pair(0,-1))

    for (i in 0 until rows) {
        for (j in 0 until cols) {
            if (grid[i][j] == 1) {
                dist[i][j] = 0
                queue.add(Pair(i, j))
            }
        }
    }

    while (queue.isNotEmpty()) {
        val (x, y) = queue.removeFirst()
        for ((dx, dy) in directions) {
            val nx = x + dx
            val ny = y + dy
            if (nx in 0 until rows && ny in 0 until cols && dist[nx][ny] > dist[x][y] + 1) {
                dist[nx][ny] = dist[x][y] + 1
                queue.add(Pair(nx, ny))
            }
        }
    }

    println("Distance matrix:")
    dist.forEach { println(it.joinToString(" ")) }
}

import Foundation

func nearestOneDistance(_ grid: [[Int]]) -> [[Int]] {
    let rows = grid.count, cols = grid[0].count
    var dist = Array(repeating: Array(repeating: Int.max, count: cols), count: rows)
    var queue = [(Int, Int)]()
    let directions = [(1,0), (-1,0), (0,1), (0,-1)]

    for i in 0..<rows {
        for j in 0..<cols {
            if grid[i][j] == 1 {
                dist[i][j] = 0
                queue.append((i, j))
            }
        }
    }

    var index = 0
    while index < queue.count {
        let (x, y) = queue[index]
        index += 1
        for (dx, dy) in directions {
            let nx = x + dx, ny = y + dy
            if nx >= 0 && ny >= 0 && nx < rows && ny < cols && dist[nx][ny] > dist[x][y] + 1 {
                dist[nx][ny] = dist[x][y] + 1
                queue.append((nx, ny))
            }
        }
    }

    return dist
}

let grid = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
]

let result = nearestOneDistance(grid)
print("Distance matrix:")
for row in result {
    print(row)
}

function nearest1Distance(grid: number[][]): number[][] {
  const rows = grid.length, cols = grid[0].length;
  const distance = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
  const queue: [number, number][] = [];
  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: number[][] = [
  [0, 0, 0],
  [0, 1, 0],
  [0, 0, 0]
];

console.log("Distance matrix:", nearest1Distance(grid));

Time complexity

Space complexity

O(m × n)

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