138. Nearest-Zero Distances

Why this mechanism works

Running BFS from every one repeats work. Reverse the viewpoint: seed all zeros simultaneously and let their distance frontiers compete. The first frontier reaching a cell is necessarily from a nearest zero because all sources begin at the same distance and all edges cost one.

State and boundaries

distance is -1 for undiscovered cells and final shortest distance for discovered cells. queue begins with every zero.

Protocol

1. Allocate distance=-1.
2. Set zero cells to distance zero and enqueue them.
3. Pop cells in FIFO order.
4. Assign each undiscovered neighbor distance+1 and enqueue.
5. Return the distance matrix.

Visualization

0 1 1
1 1 0
all zeros seed layer 0
nearest-source waves fill distances 1,2,...

Python implementation

from collections import deque

def nearest_zero_distances(matrix):
    rows = len(matrix)
    cols = len(matrix[0]) if rows else 0
    distance = [[-1] * cols for _ in range(rows)]
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == 0:
                distance[r][c] = 0
                queue.append((r, c))
    while queue:
        r, c = queue.popleft()
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and distance[nr][nc] == -1:
                distance[nr][nc] = distance[r][c] + 1
                queue.append((nr, nc))
    return distance

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 nearest_zero_distances: rows = len(matrix)
matrix=[[0, 0, 0], [0, 1, 0], [1, 1, 1]]; rows=3

L5 nearest_zero_distances: cols = len(matrix[0]) if rows else 0
matrix=[[0, 0, 0], [0, 1, 0], [1, 1, 1]]; rows=3; cols=3

L6 nearest_zero_distances: distance = [[-1] * cols for _ in range(rows)]
matrix=[[0, 0, 0], [0, 1, 0], [1, 1, 1]]; rows=3; cols=3; _=0

L6 nearest_zero_distances: distance = [[-1] * cols for _ in range(rows)]
matrix=[[0, 0, 0], [0, 1, 0], [1, 1, 1]]; rows=3; cols=3; _=1

L6 nearest_zero_distances: distance = [[-1] * cols for _ in range(rows)]
matrix=[[0, 0, 0], [0, 1, 0], [1, 1, 1]]; rows=3; cols=3; _=2

L6 nearest_zero_distances: distance = [[-1] * cols for _ in range(rows)]
matrix=[[0, 0, 0], [0, 1, 0], [1, 1, 1]]; rows=3; cols=3; distance=[[-1, -1, -1], [-1, -1, -1], [-1, -1, -1]]

L7 nearest_zero_distances: queue = deque()
matrix=[[0, 0, 0], [0, 1, 0], [1, 1, 1]]; rows=3; cols=3; distance=[[-1, -1, -1], [-1, -1, -1], [-1, -1, -1]]; queue=deque([])

L8 nearest_zero_distances: for r in range(rows):
matrix=[[0, 0, 0], [0, 1, 0], [1, 1, 1]]; rows=3; cols=3; distance=[[-1, -1, -1], [-1, -1, -1], [-1, -1, -1]]; queue=deque([]); r=0

... 106 intermediate state changes omitted ...

L15 nearest_zero_distances: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
matrix=[[0, 0, 0], [0, 1, 0], [1, 1, 1]]; rows=3; cols=3; distance=[[0, 0, 0], [0, 1, 0], [1, 2, 1]]; queue=deque([]); r=2; c=1; dr=0; dc=1; nr=1; nc=1

L16 nearest_zero_distances: nr, nc = r + dr, c + dc
matrix=[[0, 0, 0], [0, 1, 0], [1, 1, 1]]; rows=3; cols=3; distance=[[0, 0, 0], [0, 1, 0], [1, 2, 1]]; queue=deque([]); r=2; c=1; dr=0; dc=1; nr=2; nc=2

L15 nearest_zero_distances: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
matrix=[[0, 0, 0], [0, 1, 0], [1, 1, 1]]; rows=3; cols=3; distance=[[0, 0, 0], [0, 1, 0], [1, 2, 1]]; queue=deque([]); r=2; c=1; dr=0; dc=-1; nr=2; nc=2

L16 nearest_zero_distances: nr, nc = r + dr, c + dc
matrix=[[0, 0, 0], [0, 1, 0], [1, 1, 1]]; rows=3; cols=3; distance=[[0, 0, 0], [0, 1, 0], [1, 2, 1]]; queue=deque([]); r=2; c=1; dr=0; dc=-1; nr=2; nc=0

L4 nearest_zero_distances: rows = len(matrix)
matrix=[[1, 1]]; rows=1

L5 nearest_zero_distances: cols = len(matrix[0]) if rows else 0
matrix=[[1, 1]]; rows=1; cols=2

L6 nearest_zero_distances: distance = [[-1] * cols for _ in range(rows)]
matrix=[[1, 1]]; rows=1; cols=2; _=0

L6 nearest_zero_distances: distance = [[-1] * cols for _ in range(rows)]
matrix=[[1, 1]]; rows=1; cols=2; distance=[[-1, -1]]

L7 nearest_zero_distances: queue = deque()
matrix=[[1, 1]]; rows=1; cols=2; distance=[[-1, -1]]; queue=deque([])

L8 nearest_zero_distances: for r in range(rows):
matrix=[[1, 1]]; rows=1; cols=2; distance=[[-1, -1]]; queue=deque([]); r=0

L9 nearest_zero_distances: for c in range(cols):
matrix=[[1, 1]]; rows=1; cols=2; distance=[[-1, -1]]; queue=deque([]); r=0; c=0

L9 nearest_zero_distances: for c in range(cols):
matrix=[[1, 1]]; rows=1; cols=2; distance=[[-1, -1]]; queue=deque([]); r=0; c=1

Why the solution is correct

Multi-source BFS is equivalent to adding a virtual source connected equally to all zeros. Its layer order makes first discovery the minimum distance from any source. Cells left at -1 have no source reachable, which occurs here only when no zero exists.

Time and space

O(R*C) time and O(R*C) distance/queue space.

Common mistakes

Initializing every distance to zero confuses unseen cells with source cells. Starting separate searches from every one can multiply the work by the grid size.

Reasoning card

Transfer exercise

Replace zeros with a supplied set of service locations and interpret the result as a nearest-facility distance map.