Distance to the Nearest Charger

MediumGraphs

Problem

A robot vacuum maps a floor as a binary matrix grid: 0 marks a tile with a charging dock and 1 an ordinary tile. The robot moves one tile up, down, left or right per step.

Return a matrix of the same size where each cell holds the number of steps from that tile to the nearest charging dock. There is at least one dock.

Example 1

Input:
grid = [[0,0,0],[0,1,0],[1,1,1]]
Output:
[[0,0,0],[0,1,0],[1,2,1]]

The middle of the bottom row is two steps from every dock; its neighbours are one step from the docks above them.

Example 2

Input:
grid = [[1,1,1],[1,0,1],[1,1,1]]
Output:
[[2,1,2],[1,0,1],[2,1,2]]

Constraints

  • 1 ≤ rows, cols ≤ 10^4
  • rows · cols ≤ 10^4
  • grid[r][c] is 0 or 1
  • At least one cell is 0.

Hint

Show the first hint

Running a BFS from every ordinary tile to find its nearest dock repeats a lot of work.

Walkthrough

How to approach it

01Clarify before coding

  • Is the distance counted in 4-directional steps? Yes, Manhattan moves on the grid; there are no walls.
  • Is there always a dock? Yes, so every tile gets a finite distance.
  • Should I return a new matrix? Yes, a matrix of distances of the same shape.

02Brute force

For every tile with a 1, run a BFS until it hits the first 0 and record the distance.

Cost: O((r · c)²) in the worst case, e.g. a single dock in a corner of a 100 × 100 floor: 10^4 BFS runs of up to 10^4 cells each.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.