How to Solve Walls and Gates

Walls and Gates Introduction

The Walls and Gates problem asks us to find the distance from each empty parking spot to the nearest gate. This problem requires us to queue the locations of all the gates and then traverse the given array noting the distance from each nearest gate, updating the distance as one greater than the previous cell we came from.

Walls and Gates Problem

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.

For example, given the 2D grid:

INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF

After running your function, the 2D grid should be:

3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4

Walls and Gates Solutions

To solve this problem, we are given a grid representing a building layout with walls, gates, and empty rooms. Our objective is to calculate the distance from each empty room to the nearest gate. We will use the breadth-first search (BFS) algorithm to accomplish this.

The BFS algorithm starts by identifying all the gate cells in the grid and enqueues them in a queue data structure. Then, we perform a traversal by exploring the neighboring cells systematically. For each cell visited, we update its distance as one more than the distance of the cell we came from. This process continues until we have processed all reachable cells in the grid.

By the end of the BFS traversal, each empty room will have its distance to the nearest gate recorded. If a room is unreachable from any gate due to walls or obstacles, its distance will remain as infinity (INF). This way, we can fill each empty room in the grid with the distance to its nearest gate, considering the presence of walls and obstacles in the building layout.

from collections import deque

def wallsAndGates(rooms):
    if not rooms:
        return

rows, cols = len(rooms), len(rooms[0])
    queue = deque()

# Enqueue all the gate cells
    for i in range(rows):
        for j in range(cols):
            if rooms[i][j] == 0:
                queue.append((i, j))

# Define the possible directions: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

while queue:
        row, col = queue.popleft()

# Explore the neighboring cells
        for drow, dcol in directions:
            new_row, new_col = row + drow, col + dcol

# Check if the new cell is a valid empty room
            if 0 <= new_row < rows and 0 <= new_col < cols and rooms[new_row][new_col] == float('inf'):
                # Update the distance and enqueue the new cell
                rooms[new_row][new_col] = rooms[row][col] + 1
                queue.append((new_row, new_col))

# Driver code
rooms = [
    [float('inf'), -1, 0, float('inf')],
    [float('inf'), float('inf'), float('inf'), -1],
    [float('inf'), -1, float('inf'), -1],
    [0, -1, float('inf'), float('inf')]
]

wallsAndGates(rooms)

# Print the result
for row in rooms:
    print(row)

Time/Space Complexity Analysis

• Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid. This is because in the worst case, we may need to visit every cell in the grid once during the BFS traversal.
• Space Complexity: O(m * n), in the worst case, the queue used for BFS can store all the gate cells, which can be at most m * n in total. Additionally, we have constant extra space for storing the directions array and variables for row, col, newRow, and newCol. Therefore, the overall space complexity is still O(m * n).