Compute nearest-exit distances in a grid

You are given a 2D grid representing a building floor with three cell types: -1 for walls, 0 for exits, and a large sentinel value for empty rooms. Update each empty room with the Manhattan distance (4-directional moves) to its nearest exit; if unreachable, leave it as the sentinel value. Solve it efficiently and analyze time and space complexity. Follow-ups: extend to a 3D grid (multiple floors) and to weighted movement costs.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Compute Nearest-Exit Distances in a Grid (Walls and Gates)

You are given an m x n 2D grid representing a building floor. Each cell is one of three values:

• -1 — a wall or obstacle (impassable).
• 0 — an exit (gate).
• 2147483647 — an empty room (a large sentinel value meaning "infinity").

Fill each empty room with the distance (number of 4-directional moves) to its nearest exit. If it is impossible to reach an exit from a room, leave that room as the sentinel value 2147483647.

Return the grid after filling it in (the grid may also be mutated in place).

Example

Input:

[[INF, -1,  0, INF],
 [INF, INF, INF, -1],
 [INF, -1, INF, -1],
 [  0, -1, INF, INF]]

Output:

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

where INF = 2147483647.

Approach hint: Run a single multi-source breadth-first search starting simultaneously from every exit. The first time BFS reaches a room, that is its shortest distance to any exit. This is O(m·n) rather than running a separate BFS from each room.

Follow-ups discussed in the interview: extend the same multi-source BFS to a 3D grid (multiple floors, 6 neighbors) and to weighted movement costs (replace the BFS queue with a min-heap / Dijkstra).

Constraints

• 1 <= m, n <= 250 (typical interview bound)
• Each cell is -1 (wall), 0 (exit), or 2147483647 (empty room).
• The grid may contain zero exits (then every room stays 2147483647).
• Distances use 4-directional (up/down/left/right) Manhattan-style moves; you cannot pass through walls.

Hints

1. A separate BFS from every room is O((m*n)^2). Invert the problem: BFS outward from the exits instead.
2. Seed a single queue with the coordinates of ALL exits (cells equal to 0) before starting BFS — this is multi-source BFS.
3. When you pop a cell, push each neighbor that still equals the sentinel 2147483647 and set its value to current + 1. Because BFS expands in layers of increasing distance, the first time you reach a room is its shortest distance, so no revisits and no explicit visited set are required.
4. Walls (-1) and already-filled rooms are simply never enqueued because their value is not the sentinel.
5. Follow-up (3D): use 6 neighbor offsets and (floor, row, col) tuples. Follow-up (weighted moves): replace the FIFO queue with a min-heap (Dijkstra) keyed by accumulated cost.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

You are given a 2D grid representing a building floor with three cell types: -1 for walls, 0 for exits, and a large sentinel value for empty rooms. Update each empty room with the Manhattan distance (4-directional moves) to its nearest exit; if unreachable, leave it as the sentinel value. Solve it efficiently and analyze time and space complexity. Follow-ups: extend to a 3D grid (multiple floors) and to weighted movement costs.

Recommended Approach

Represent each cell as a state. Use BFS for minimum-distance propagation, DFS with memoization for longest monotonic paths, and careful boundary checks for simulation. Store obstacles or visited cells in sets when the grid is sparse.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

A full grid traversal is O(mn) time and O(mn) space in the worst case. Sparse simulation is O(number_of_commands) plus obstacle storage.

Edge Cases and Tests

Empty grid, one row/column, blocked start or target, boundaries, repeated visits, and tie-breaking among equal-distance cells.