Distance of Nearest Cell Having 1 | 0/1 Matrix (BFS)

This chapter covers the algorithmic approach to finding the shortest distance from every cell in a binary grid to the nearest cell containing a value of $1$. This problem is commonly known as 01 Matrix on LeetCode or Distance of nearest cell having 1 on GeeksforGeeks.

1. Problem Statement & Grid Definition

Given an $N \times M$ binary grid (containing only 0s and 1s), the objective is to find the minimum distance from each cell to the nearest cell containing a 1.

• Distance Metric: The distance between two cells $(r_1, c_1)$ and $(r_2, c_2)$ is calculated using the Manhattan Distance formula (absolute row difference plus absolute column difference):

(Note: Diagonal movements are not permitted).

Example Input Grid

1  0  1
1  1  0
1  0  0

Corresponding Output Distance Matrix

0  1  0
0  0  1
0  1  2

• Explanation for Output:
  • Cells containing 1 naturally have a distance of 0 to themselves.
  • The 0 at position (0, 1) has a nearest 1 at (0, 0) or (0, 2) with a distance of $\vert 0-0\vert + \vert 1-0\vert = 1$.
  • The bottom-right 0 at position (2, 2) requires moving up twice or left then up, resulting in a minimum distance of 2 to the nearest 1 located at (1, 0) or (2, 0).

2. Core Mental Model & Why BFS?

When dealing with unweighted grid traversal where we need to find "minimum steps" or "shortest distance" from multiple potential starting points, Breadth-First Search (BFS) is the ideal choice.

Real-Life Analogy: The Expanding Fire Waves

Imagine every cell containing a 1 is a fire hydrant simultaneously spraying water in all four directions (up, down, left, right) at the exact same speed.

• At Step 0, the water is right on top of the initial 1 cells (distance = 0).
• At Step 1, the water wavefront hits all adjacent neighboring cells, wetting them for the first time (distance = 1).
• At Step 2, the wavefront expands further outward to touch the next set of unvisited cells (distance = 2).

Why DFS Fails Here

If you attempt to use Depth-First Search (DFS), you would travel down a single deep path completely, which cannot guarantee that the first time you touch a cell, it is via the absolute shortest path. BFS explores level-by-level, ensuring that when a cell is reached for the first time, it is guaranteed to be via the minimum possible steps.

3. Multi-Source BFS Strategy

Because there can be multiple 1s in the grid, starting a separate BFS for each 1 would result in a terrible time complexity. Instead, we use a Multi-Source BFS:

1. Push all initial sources (1s) into the BFS queue simultaneously at step 0.
2. Mark all sources as visited in a separate visited matrix to prevent reprocessing.
3. Expand level-by-level: Pop an element from the queue, check its 4-directional neighbors, and if an unvisited neighbor is found, record its distance as current_steps + 1, mark it visited, and push it into the queue.

4. Data Structures & Initial Setup Rules

To maintain clean code and avoid mutating the original problem input, we maintain two parallel support structures alongside the original grid:

• visited Matrix: An $N \times M$ matrix initialized to 0 (or false), tracking which cells have already been processed.
• dist Matrix: An $N \times M$ matrix initialized to 0, which will eventually store our final computed answer.
• Queue (q): Stores tuples consisting of (row, col, steps).

5. Step-by-Step Execution Walkthrough

Let's trace how the queue and distance matrix evolve:

1. Initialization:

   • Locate all 1s in the grid: (0,0), (0,2), (1,0), (1,1), (2,0).
   • Push these coordinates into the queue with step 0: Queue = [((0,0), 0), ((0,2), 0), ((1,0), 0), ((1,1), 0), ((2,0), 0)]
   • Mark all corresponding cells in the visited matrix as 1.

2. Processing Queue Elements:

   • Pop (0,0) with step 0. Look at neighbors (0,1) and (1,0).
     • (1,0) is already visited.
     • (0,1) is unvisited (0). Mark visited[0][1] = 1, set dist[0][1] = 0 + 1 = 1, and push ((0,1), 1) into the queue.
   • Continue this process level by level across all directions for every node in the queue.

6. Direction Vectors (Delta Arrays)

To cleanly check all 4 neighbors (Up, Right, Down, Left) of any cell (r, c) without writing 4 separate conditional blocks, we use Delta Arrays:

// Delta arrays for moving Up, Right, Down, Left
int delRow[] = {-1, 0, +1, 0};
int delCol[] = {0, +1, 0, -1};

// Neighbor coordinates calculation inside the loop:
int nRow = row + delRow[i];
int nCol = col + delCol[i];

7. Complete C++ Implementation

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        
        // Visited matrix and Distance matrix
        vector<vector<int>> vis(n, vector<int>(m, 0));
        vector<vector<int>> dist(n, vector<int>(m, 0));
        
        // Queue stores: { {row, col}, steps }
        queue<pair<pair<int, int>, int>> q;
        
        // Step 1: Initialize queue with all '1' sources
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == 1) {
                    q.push({{i, j}, 0});
                    vis[i][j] = 1;
                } else {
                    vis[i][j] = 0;
                }
            }
        }
        
        // Delta arrays for 4-directional movement (Up, Right, Down, Left)
        int delRow[] = {-1, 0, +1, 0};
        int delCol[] = {0, +1, 0, -1};
        
        // Step 2: Multi-source BFS traversal
        while(!q.empty()) {
            int row = q.front().first.first;
            int col = q.front().first.second;
            int steps = q.front().second;
            q.pop();
            
            // Record distance
            dist[row][col] = steps;
            
            // Traverse all 4 neighbors
            for(int i = 0; i < 4; i++) {
                int nRow = row + delRow[i];
                int nCol = col + delCol[i];
                
                // Check boundary validity and whether the neighbor is unvisited
                if(nRow >= 0 && nRow < n && nCol >= 0 && nCol < m && !vis[nRow][nCol]) {
                    vis[nRow][nCol] = 1;
                    q.push({{nRow, nCol}, steps + 1});
                }
            }
        }
        
        return dist;
    }
};

8. Complexity Analysis

9. Summary and Key Takeaways

• Problem Classification: This is a classic Multi-Source Shortest Path in an Unweighted Grid problem solved using BFS.
• Avoid Altering Input: It is best practice to never modify the input grid directly; instead, maintain separate visited and distance tracking matrices.
• Why Multi-Source?: Inserting all starting points (1s) into the queue simultaneously allows all wavefronts to expand concurrently, achieving optimal $O(N \times M)$ time complexity.
• Manhattan Distance: Because diagonal movement is forbidden, row and column differences dictate the exact step count.
• Delta Arrays: Using delRow and delCol arrays provides a clean, scalable pattern for exploring adjacent grid cells without repetitive conditional statements.
• Level-Order Guarantee: BFS naturally guarantees that the first time an unvisited cell is reached, the distance recorded is the absolute minimum possible.