Skip to content
BASA DSA

Walls And Gates

MediumGraphs

Mutate each empty room to its shortest orthogonal distance to any gate. Walls are -1, gates 0, and empty rooms 2147483647. Unreachable rooms retain that sentinel. Return nothing.

Example 1

0,0∞
0,1-1
0,20
1,0∞
1,1∞
1,2∞
−1 = wall; 0 = gate; ∞ = empty room (2147483647). Movement is horizontal or vertical.
Input
rooms = [[2147483647,-1,0],[2147483647,2147483647,2147483647]]
Output
[[4,-1,0],[3,2,1]]

Explanation

The wall forces a detour below it; gate distances along the route are 1,2,3,4.

Example 2

0,0∞
0,1-1
0,20
−1 = wall; 0 = gate; ∞ = empty room (2147483647). Movement is horizontal or vertical.
Input
rooms = [[2147483647,-1,0]]
Output
[[2147483647,-1,0]]

Explanation

The wall disconnects the room from the gate, leaving its infinity sentinel.

Example 3

0,00
−1 = wall; 0 = gate; ∞ = empty room (2147483647). Movement is horizontal or vertical.
Input
rooms = [[0]]
Output
[[0]]

Explanation

A gate's distance is already zero.

Constraints

  • 1 <= rows, columns <= 250
  • Cells initially are -1, 0 or 2147483647

Function contractwalls_and_gatesArguments: json
Loading draft…
SolutionRuns on your device