01 Matrix

Given a matrix of 0s and 1s, replace every cell with its distance to the nearest 0, where a step is one move up, down, left or right (LeetCode 542).

• Input: [[0,0,0],[0,1,0],[1,1,1]]. Output: [[0,0,0],[0,1,0],[1,2,1]].
• A 0 is its own nearest zero, so it stays 0.
• LeetCode guarantees at least one 0, so every cell has an answer.

The obvious reading — for each 1, search for the closest 0 — is a BFS per cell, which is O((R × C)²) and too slow. Turning the question round is what makes it linear.

Search from the zeroes instead of towards them.

1. Queue every zero. They are all at distance 0, so they all start in the queue together — multi-source BFS again.
2. Mark the rest -1. One value says "no zero has reached this cell yet", so the matrix being returned is also the visited set. Nothing extra is allocated.
3. Flood outwards. Dequeue a cell and look at its four neighbours. One that is still -1 is being reached for the first time, so its distance is this cell's plus one, and it joins the queue.
4. Nothing is revisited. A cell already holding a number was reached by an equally close or closer zero, so it is skipped.

Why the first zero to arrive is the nearest one. BFS dequeues cells in order of distance, so when a cell is reached for the first time no shorter route to any zero can exist — which is why a distance is written once and never improved.

The opening scan is stepped through, because it is the whole trick: every zero joins the queue together and every one becomes -1. A cell shows exactly what the matrix holds at that moment — 0, -1, or the distance it was given — so the figure and the matrix being returned are the same object. Watch the frontier: it is always one distance, or two neighbouring ones.