Distance of Nearest Cell Having 1

Given an R × C grid of 0s and 1s, for every cell compute the distance (number of 4-directional steps) to the nearest cell containing a 1. A cell that already holds a 1 has distance 0. Return the grid of distances. (If the grid has no 1 at all, every distance is -1.)

Hints

· Stuck? Reveal one nudge at a time.

Don't BFS from every cell — seed one BFS from all the 1s at once.

Every 1-cell starts at distance 0.

The first time BFS reaches a cell, that's its distance to the nearest 1.

Common doubts

BFS settles cells in nondecreasing distance order, so a cell is first reached by the wave from its closest source.

All 1-cells share the initial queue at distance 0, so every cell measures to whichever source is nearest.

No sources means no distances — every cell stays -1.

Interview follow-ups

· What an interviewer asks next.

Seed from all 0-cells instead — it's the same algorithm (LeetCode 542).

Yes — two sweeps (top-left then bottom-right) propagate the nearest distance in O(R·C) without a queue.

Fun facts

This is the mirror of LeetCode 542 (0-1 matrix): sources are the 1s instead of the 0s.
Multi-source BFS is the grid version of adding a virtual super-source connected to all sources.

Asked at

AmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: grid = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[2,1,2],[1,0,1],[2,1,2]]
Distances radiate outward from the single 1.

Example 2

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: [[0,1,0],[1,2,1],[0,1,0]]
Each cell takes the closest of the four corner 1s.

Constraints

- 1 <= R, C <= 500 - grid[i][j] is 0 or 1

For each cell you want the shortest hop-count to any 1. Running a separate BFS from every cell is wasteful; instead run one multi-source BFS seeded from all the 1s at once. Every 1 starts at distance 0, and the BFS assigns each other cell the minute (i.e. hop-count) it's first reached — which is exactly its distance to the nearest 1.

Multi-source BFS is the key idea: because all sources expand together, the first time a cell is reached is via its closest source. O(R·C) — each cell is settled once.

Prerequisites

Before you start

· Concepts used directly in the solution.

Multi-source BFS. seed all 1-cells at distance 0.

First-reach = shortest. BFS settles each cell via its nearest source.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Distance to nearest 1 or nearest 0?”

Nearest 1 here (a 1-cell is distance 0).

“Movement?”

4-directional steps.

The ideal opening — say it like this

I seed a BFS with every 1-cell at distance 0 and spread outward, so each cell's first-reach distance is its answer.

One pass settles every cell — O(R·C) — instead of a BFS per cell.

Understand the problem

Worked example — grid = [[0,0,0],[0,1,0],[0,0,0]]

center is a source (0)
ring 1: its 4 neighbours -> 1
corners -> 2
result = [[2,1,2],[1,0,1],[2,1,2]]

Key observations

1Aha

One BFS, many sources

Seed every 1-cell; don't BFS per cell.

2Aha

First reach is the nearest source

BFS's distance order guarantees minimal distance.

3Aha

O(R·C)

Each cell is finalized exactly once.

Brute force vs optimal

	Per-cell distance	Multi-source BFS
Idea	For each cell, scan/BFS to the nearest 1	One BFS from all 1s
Time	O((R·C)²)	O(R·C)
Space	O(R·C)	O(R·C)

Both give the same distances; multi-source BFS does it in one linear pass. Full code is in the Approaches selector below.

Summary

Key takeaway

Seed a BFS with every 1-cell at distance 0; each cell's first-reach distance is its answer. O(R·C).

queue = all 1-cells (dist 0)
BFS: unvisited neighbour gets dist+1