Walls And Gates - Leetcode Solution

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 Breadth-first search (BFS). Here’s how we can do it:

1. 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.

2. 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.

3. 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.

4. 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.

5. We repeat steps 3-4 for every other cell in the queue until all the empty cells have been visited.

6. 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 in-place 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 double-ended queue.

1