Walls and gates: distance from each room to the nearest gate

You get an m x n grid of rooms. Each cell is -1 for a wall, 0 for a gate, or INF = 2147483647 for an empty room. Fill each empty room with the number of steps to its nearest gate, moving up, down, left or right and never through a wall. A room that cannot reach any gate stays INF.

Interface

Unless you agree on a different interface with the interviewer, assume:

• walls_and_gates(rooms: list[list[int]]) -> None — modifies rooms in place.

Example

INF = 2147483647

[[INF,  -1,   0, INF],          [[3, -1, 0,  1],
 [INF, INF, INF,  -1],    ->     [2,  2, 1, -1],
 [INF,  -1, INF,  -1],           [1, -1, 2, -1],
 [  0,  -1, INF, INF]]           [0, -1, 3,  4]]

[[0, INF, -1],                  [[0, 1, -1],
 [INF, -1, INF]]          ->     [1, -1, INF]]     # the last room is cut off

Constraints

• 1 <= m, n <= 250.
• Each cell is -1, 0 or 2147483647.

Clarifying questions

• Can there be no gates at all?
• May I modify the grid in place?
• Is movement only in four directions?

What a strong answer covers

• Why a BFS from each room, or from each gate separately, is too slow: O((m * n)^2) in the worst case.
• Multi-source BFS: put every gate in the queue at distance 0, expand level by level, and set a room's distance the first time it is reached. The first visit is always the shortest.
• The grid itself works as the visited set: only rooms still equal to INF are updated.
• O(m * n) time and O(m * n) space for the queue.
• Tests: no gates, no empty rooms, rooms walled off, a single row or column, many gates.

Follow-ups

• Return the distance to the nearest gate together with which gate it is.
• Some cells cost 2 steps to cross. What algorithm do you use now?
• The grid is too large for memory and arrives row by row. Can you still compute the distances?