Fill rooms with nearest gate distances
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
You are given an m×n integer grid representing rooms, where -1 is a wall, 0 is a gate, and INF (a large sentinel such as 2^31−
1) is an empty room. For each empty room, fill it with the minimum number of steps to the nearest gate using four-directional movement; if unreachable, leave it as INF. Implement an in-place algorithm, justify your traversal strategy (e.g., multi-source BFS), and analyze time and space complexity. Cover edge cases such as multiple gates, enclosed areas, and very large grids.
Quick Answer: This question evaluates grid-based graph traversal and algorithmic problem-solving skills, including concepts such as multi-source breadth-first search, handling sentinel values, and performing in-place updates.
Given rooms grid with -1 walls, 0 gates, and INF empty rooms, fill each reachable room with distance to nearest gate.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]],)
Expected Output: [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]
Explanation: Classic walls and gates.
Input: ([],)
Expected Output: []
Explanation: Empty grid.
Hints
- Model object-style prompts as arrays or operation streams when needed.
- Handle empty and boundary cases before the main logic.