How to Solve Walls and Gates
Walls and Gates Introduction
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
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
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)1from collections import deque
2
3def wallsAndGates(rooms):
4 if not rooms:
5 return
6
7 rows, cols = len(rooms), len(rooms[0])
8 queue = deque()
9
10 # Enqueue all the gate cells
11 for i in range(rows):
12 for j in range(cols):
13 if rooms[i][j] == 0:
14 queue.append((i, j))
15
16 # Define the possible directions: up, down, left, right
17 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
18
19 while queue:
20 row, col = queue.popleft()
21
22 # Explore the neighboring cells
23 for drow, dcol in directions:
24 new_row, new_col = row + drow, col + dcol
25
26 # Check if the new cell is a valid empty room
27 if 0 <= new_row < rows and 0 <= new_col < cols and rooms[new_row][new_col] == float('inf'):
28 # Update the distance and enqueue the new cell
29 rooms[new_row][new_col] = rooms[row][col] + 1
30 queue.append((new_row, new_col))
31
32# Driver code
33rooms = [
34 [float('inf'), -1, 0, float('inf')],
35 [float('inf'), float('inf'), float('inf'), -1],
36 [float('inf'), -1, float('inf'), -1],
37 [0, -1, float('inf'), float('inf')]
38]
39
40wallsAndGates(rooms)
41
42# Print the result
43for row in rooms:
44 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).
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
