Similar Problems
Similar Problems not available
Walls And Gates  Leetcode Solution
LeetCode: Walls And Gates Leetcode Solution
Difficulty: Medium
Topics: matrix array breadthfirstsearch
Problem statement:
You are given a m x n 2D grid initialized with these three possible values.
 1  A wall or an obstacle.
 0  A gate.
 INF  Infinity means an empty room. We use the value 231  1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
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]]
Solution:
The problem is asking us to find the minimum distance from each empty room (INF) to the nearest gate (0). We can solve this problem by using a variation of Breadthfirst search (BFS). Here’s how we can do it:

First, we need to find all the gates (0s) in the grid. We can do this by iterating through the entire grid and adding the gates to a queue.

Next, we will perform a BFS on each gate in the queue until we have visited every empty room (INF) in the grid. We can use a distance variable to keep track of the minimum distance from the gates to other rooms.

We start by processing the first gate in the queue. We will create a new row and column variable that is used to keep track of the neighboring cells. We will check the four neighbor cells (up, down, left, right) of the current cell to see if they are empty and have not been visited yet.

If a neighbor cell is empty and has not been visited, we can update its value to be the current distance + 1. We then add this neighbor cell to the queue.

We repeat steps 34 for every other cell in the queue until all the empty cells have been visited.

We can then return the updated grid.
Here’s the implementation of the above algorithm in Python:
from collections import deque
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) > None:
"""
Do not return anything, modify rooms inplace instead.
"""
#helper function to check if the cell is empty
def is_empty(row, col):
return 0 <= row < m and 0 <= col < n and rooms[row][col] == INF
#the directions to move
dirs = [[1,0], [1,0], [0,1], [0,1]]
#constants
INF = 2 ** 31  1
GATE = 0
#get the dimensions of the input matrix
m = len(rooms)
n = len(rooms[0])
#initialize a double ended queue
queue = deque()
#add all gates to the queue
for i in range(m):
for j in range(n):
if rooms[i][j] == GATE:
queue.append((i,j))
#start processing gates until we have visited all the empty rooms
while queue:
row, col = queue.popleft()
distance = rooms[row][col] + 1
for i, j in dirs:
new_row = row + i
new_col = col + j
if is_empty(new_row, new_col):
rooms[new_row][new_col] = distance
queue.append((new_row, new_col))
The time complexity of the above algorithm is O(mn) where m and n are the dimensions of the input matrix. The space complexity is O(mn) as well since we are storing the gates in a doubleended queue.
Walls And Gates Solution Code
1