Coding interview problems › Graphs & Grids

🗺️ Graphs & Grids Medium

01 Matrix (Distance to the Nearest Zero)

01 Matrix explained: run one multi-source BFS from every 0 to get each cell's distance to the nearest zero. Tested Python code, pitfalls and a live grid visual.

Also searched as: distance of nearest 0 for every cell · multi-source BFS from all zeros

🏝️

Try it live Free

Number of Islands & Grid BFS

Watch the Grid BFS lab flood outward in distance rings from S; here the flood starts from every 0 at the same moment.

Also useful: Graph Search: BFS vs DFS

Open the playground →

The problem

Given a grid of 0s and 1s, return a grid of the same size where each cell holds the distance (number of up, down, left, right steps) to the nearest 0.

Inputmat = [[0,0,0],[0,1,0],[1,1,1]]
Output[[0,0,0],[0,1,0],[1,2,1]]

The key insight

Running a BFS from every 1 to find its nearest 0 repeats a lot of work. Flip the direction: start one BFS from all the 0s at once (multi-source BFS). The first time the flood reaches a cell is its shortest distance to any zero, and every cell is settled exactly once.

Brute force first: A separate BFS from each 1 until it meets a 0 is correct but O((m·n)²) in the worst case.

Step-by-step approach

  1. Create dist with 0 for every zero cell and None (unvisited) for every one.
  2. Push all zero cells onto the queue.
  3. Pop a cell; for each in-bounds neighbour that is still unvisited, set its distance to the current distance plus 1 and push it.
  4. When the queue is empty, every cell holds its distance to the nearest 0.

Python solution

PYTHON 3tested
from collections import deque


def update_matrix(mat):
    rows, cols = len(mat), len(mat[0])
    dist = [[None] * cols for _ in range(rows)]
    q = deque()
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                dist[r][c] = 0
                q.append((r, c))       # all zeros are sources
    while q:
        r, c = q.popleft()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] is None:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

Complexity

TimeO(m·n)
SpaceO(m·n)

Each cell gets its distance and enters the queue exactly once. The distance grid and the queue are both O(m·n).

Common mistakes

Frequently asked questions

What is the time and space complexity of the 01 Matrix solution?

O(m·n) time since each cell is enqueued once, and O(m·n) space for the distance grid and queue.

Is there a non-BFS solution?

Yes, a two-pass dynamic programming approach: one pass from top-left taking min of up and left plus 1, then one from bottom-right taking min of down and right plus 1. It is also O(m·n).

Why does multi-source BFS give the nearest zero?

BFS expands in order of distance. Seeding it with all zeros at distance 0 means the first wave to touch a cell came from its closest zero.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Graphs & Grids Graph Search: BFS vs DFS lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.