Solution: Walls and Gates

Grokking 75: Top Coding Interview Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Walls and Gates

Table of Contents

Contents are not accessible

Problem Statement

You are given a grid of size m x n filled with three possible values:

-1 representing a wall or an obstacle.
0 representing a gate.
2147483647 (INF) representing an empty room.

Fill each empty room with the distance to its nearest gate. If an empty room cannot reach any gate, it should remain 2147483647.

Examples

Example 1

Input:

[[2147483647, -1, 0],
 [2147483647, 2147483647, 2147483647],
 [2147483647, -1, 2147483647]]

Expected Output:
```
[[4, -1, 0],
 [3, 2, 1],
 [4, -1, 2]]
```
Justification:
- Starting from the gates, calculate the minimum distance for each empty room. Each room contains the minimum steps to the nearest gate.

Example 2

Input:

[[0, 2147483647, 2147483647, 0],
 [2147483647, -1, 2147483647, 2147483647],
 [2147483647, -1, -1, 2147483647],
 [0, 2147483647, 2147483647, 0]]

Expected Output:

[[0, 1, 1, 0],
 [1, -1, 2, 1],
 [1, -1, -1, 1],
 [0, 1, 1, 0]]

Justification:
- The gates at the corners spread their distances to the empty rooms.

Example 3

Input:

[[2147483647, -1, 0, 2147483647],
 [-1, 2147483647, 2147483647, -1],
 [0, -1, 2147483647, 2147483647],
 [2147483647, -1, 2147483647, -1]]

Expected Output:

[[2147483647, -1, 0, 1],
 [-1, 2, 1, -1],
 [0, -1, 2, 3],
 [1, -1, 3, -1]]

Justification:
- The gates in the middle of the grid spread their distances, and the walls prevent certain paths.

Constraints:

m == rooms.length
n == rooms[i].length
1 <= m, n <= 250
rooms[i][j] is -1, 0, or 2<sup>31</sup> - 1.

Solution

To solve this problem, we need to use a breadth-first search (BFS) approach starting from each gate (0) and moving outward to calculate the shortest distance to each empty room (2147483647). BFS is suitable here because it explores all possible steps from the source nodes (gates) level by level, ensuring that we find the shortest path to each room.

The BFS approach ensures that we fill each empty room with the minimum distance to any gate. By processing all gates simultaneously, we guarantee that we correctly handle the distances even when multiple gates influence the same empty room.

Step-by-step Algorithm

Initialize a Queue:
- Create an empty queue to store the coordinates of the gates.
Add Gates to Queue:
- Traverse the grid.
- For each cell, if it contains a gate (value 0), add its coordinates to the queue.
Breadth-First Search (BFS) Initialization:
- Define the directions array to explore the four possible moves (up, down, left, right).
BFS Execution:
- While the queue is not empty:
  - Dequeue a cell from the queue.
  - For each direction in the directions array:
    - Calculate the new cell coordinates by adding the direction values to the current cell coordinates.
    - Check if the new cell is within the grid boundaries and if it is an empty room (value 2147483647).
    - If valid, update the new cell's value to the current cell's value + 1.
    - Enqueue the new cell's coordinates.
End:
- Continue until the queue is empty, meaning all reachable cells have been processed.

Algorithm Walkthrough

Input:

[[2147483647, -1, 0],
 [2147483647, 2147483647, 2147483647],
 [2147483647, -1, 2147483647]]

Initialization:
- Queue: []
- Directions: [(-1, 0), (0, 1), (1, 0), (0, -1)]
Add Gates to Queue:
- Traverse the grid and find the gate at (0, 2).
- Add (0, 2) to the queue.
- Queue: [(0, 2)]
BFS Execution:
- First Level (Distance 0):
  - Dequeue (0, 2), process it.
  - Explore directions:
    - Up: (-1, 2) (out of bounds)
    - Right: (0, 3) (out of bounds)
    - Down: (1, 2)
      - Update value at (1, 2) to 1.
      - Enqueue (1, 2).
    - Left: (0, 1) (wall)
  - Grid:
```
[[2147483647, -1, 0],
 [2147483647, 2147483647, 1],
 [2147483647, -1, 2147483647]]
```
  - Queue: [(1, 2)]
- Second Level (Distance 1):
  - Dequeue (1, 2), process it.
  - Explore directions:
    - Up: (0, 2) (gate, already processed)
    - Right: (1, 3) (out of bounds)
    - Down: (2, 2)
      - Update value at (2, 2) to 2.
      - Enqueue (2, 2).
    - Left: (1, 1)
      - Update value at (1, 1) to 2.
      - Enqueue (1, 1).
  - Grid:
```
[[2147483647, -1, 0],
 [2147483647, 2, 1],
 [2147483647, -1, 2]]
```
  - Queue: [(2, 2), (1, 1)]
- Third Level (Distance 2):
  - Dequeue (2, 2), process it.
  - Explore directions:
    - Up: (1, 2) (already processed)
    - Right: (2, 3) (out of bounds)
    - Down: (3, 2) (out of bounds)
    - Left: (2, 1) (wall)
  - Dequeue (1, 1), process it.
  - Explore directions:
    - Up: (0, 1) (wall)
    - Right: (1, 2) (already processed)
    - Down: (2, 1) (wall)
    - Left: (1, 0)
      - Update value at (1, 0) to 3.
      - Enqueue (1, 0).
  - Grid:
```
[[2147483647, -1, 0],
 [3, 2, 1],
 [2147483647, -1, 2]]
```
  - Queue: [(1, 0)]
- Fourth Level (Distance 3):
  - Dequeue (1, 0), process it.
  - Explore directions:
    - Up: (0, 0)
      - Update value at (0, 0) to 4.
      - Enqueue (0, 0).
    - Right: (1, 1) (already processed)
    - Down: (2, 0)
      - Update value at (2, 0) to 4.
      - Enqueue (2, 0).
    - Left: (1, -1) (out of bounds)
  - Grid:
```
[[4, -1, 0],
 [3, 2, 1],
 [4, -1, 2]]
```
  - Queue: [(0, 0), (2, 0)]
- Fifth Level (Distance 4):
  - Dequeue (0, 0), process it.
  - Explore directions:
    - Up: (-1, 0) (out of bounds)
    - Right: (0, 1) (wall)
    - Down: (1, 0) (already processed)
    - Left: (0, -1) (out of bounds)
  - Dequeue (2, 0), process it.
  - Explore directions:
    - Up: (1, 0) (already processed)
    - Right: (2, 1) (wall)
    - Down: (3, 0) (out of bounds)
    - Left: (2, -1) (out of bounds)
  - Grid:
```
[[4, -1, 0],
 [3, 2, 1],
 [4, -1, 2]]
```
  - Queue: []
End:
- The queue is empty, the process is complete.
- Final Grid:
```
[[4, -1, 0],
 [3, 2, 1],
 [4, -1, 2]]
```

Code

Python3

. . . .

Complexity Analysis

Time Complexity:

The time complexity of the algorithm is $O(m \times n)$ , where (m) is the number of rows and (n) is the number of columns in the grid. This is because each cell is processed at most once, and there are $m \times n$ cells in total.

Space Complexity:

The space complexity is also $O(m \times n)$ , which accounts for the space used by the queue. In the worst case, all the empty rooms could be added to the queue.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible