AceYourInterviews
Checking sign-in…

98. Walls and Gates — Nearest Gate Distance

CoreSeed all zero-distance gates before claiming each empty room once

For each empty room, find the fewest orthogonal steps needed to reach any gate without crossing a wall. Preserve gate values, wall values, and the sentinel for unreachable rooms.

You are minimizing over all gates, not choosing one fixed gate. The input grid must remain unchanged under this course's return-new-grid contract.

Example 1

Input

[[MAX,-1,0],[MAX,MAX,MAX],[0,-1,MAX]]

Output

[[2,-1,0],[1,2,1],[0,-1,2]]

Explanation: Both gates start at zero; first room discovery minimizes across either source.

Example 2

Input

[[MAX,-1,0],[-1,-1,-1],[MAX,MAX,MAX]]

Output

unchanged values in fresh rows

Explanation: Walls separate the unassigned rooms from the only gate.

Constraints

  • 0 <= rooms.length <= 105
  • 0 <= total rooms cells <= 105
  • All rows have equal length and are non-null.
  • Cells are walls (-1), gates (0) or empty rooms (2^31 - 1).
Hints
Hint 1

Could all gates act as sources at the same time?

Hint 2

Copy the source, queue every gate at zero, then expand one FIFO.

Hint 3

Assign a MAX room before enqueueing it; that first distance is minimum.

Practice on LeetCode ↗ · Premium
Code
Saved on this deviceLn 1, Col 1

All gates share the zero-distance frontier

[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
[[2,-1,0],[1,2,1],[0,-1,2]]