DSA interview question

Distance of the Nearest Cell Having 1

Medium · Data structures · Topics: graph, bfs, matrix

The problem

A city grid marks hospitals with 1 and ordinary blocks with 0. For planning ambulance coverage, every block needs its distance to the nearest hospital, moving up, down, left or right. Running a BFS from every block is O((R·C)²). Reverse the viewpoint instead: start a single BFS from all hospitals at once (multi-source). The first time the BFS reaches a block is its distance to the nearest hospital.

Example: [[0,1,1,0], [1,1,0,0], [0,0,1,1]] → [[1,0,0,1], [0,0,1,1], [1,1,0,0]].

Function signature

vector<vector<int>> nearest(const vector<vector<int>>& grid);  // at least one 1 exists

Test cases

Input	Output	Explanation
`[[0,1,1,0],[1,1,0,0],[0,0,1,1]]`	`[[1,0,0,1],[0,0,1,1],[1,1,0,0]]`
`[[1,0,1],[1,1,0],[1,0,0]]`	`[[0,1,0],[0,0,1],[0,1,2]]`
`[[0,0],[0,1]]`	`[[2,1],[1,0]]`
`[[1,0,0,0]]`	`[[0,1,2,3]]`
`[[1]]`	`[[0]]`

(Confirm: distance is the number of 4-directional steps; the grid has at least one 1.)

How interviewers phrase it

"Given a binary grid, find the distance of the nearest 1 for each cell" (GeeksforGeeks "Distance of nearest cell having 1"; LeetCode 542 "01 Matrix" asks for the nearest 0 instead).

Clarifying questions to ask

4-directional moves? (Yes.)
Is there always at least one 1? (Yes.)
Can cells be blocked? (No, all cells are passable.)

Follow-ups to expect

"Why start from all 1s?"
"Why can't DFS do this?"
"Without obstacles, isn't it just the Manhattan distance?"
"Where else is multi-source BFS used?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview