286. Walls and Gates

Problem Description

In this problem, we are presented with a grid representing a series of rooms, each of which could be an empty room, a gate, or a blocked wall. The value -1 identifies a wall or obstacle, which means the room cannot be passed through. A value of 0 indicates a gate, serving as a possible destination for other rooms. Any room with a value of INF, which stands for infinity and is given the numerical value of 2147483647, represents an empty room needing the distance filled to its nearest gate.

The task is to update the grid so that all empty rooms have their values changed from INF to the shortest distance to a gate. If there's no way to get to a gate, the value of INF should remain unchanged. The update should be done in place, meaning no additional grid should be constructed but instead, the rooms grid itself should be modified.

Flowchart Walkthrough

Let's analyze Leetcode 286. Walls and Gates using the algorithm flowchart provided at the Flowchart. Here's a detailed breakdown of the steps:

Is it a graph?

Yes: The grid can be viewed as a graph, where each cell is a node and walls do not have edges connecting to other cells, whereas gates and empty rooms are normally connected.

Is it a tree?

No: The structure contains multiple entries (gates) and does not follow a hierarchical single-root system typical in a tree.

Is the problem related to directed acyclic graphs (DAGs)?

No: This problem is more about exploring from multiple sources (gates) and determining shortest paths to them from every room. It does not involve topological concerns typical of DAGs.

Is the problem related to shortest paths?

Yes: The core requirement is to find the shortest distance to the nearest gate for each empty room.

Is the graph weighted?

No: All valid movements from one room to an adjacent room have uniform 'cost' (one step), so there is no weighting in distances.

Conclusion: The flowchart culminates in using Breadth-First Search (BFS) for this unweighted shortest path problem starting from each gate to propagate the minimal distances to all reachable rooms.

Intuition

The solution applies the Breadth-First Search (BFS) algorithm, a common approach for exploring all possible paths in level-order from a starting point in a graph or grid.

The intuition for this problem is as follows:

First, we identify all gate locations as starting points since we need to find the minimum distance from these gates to each room.
We put all these gate coordinates in a queue for BFS processing. Since BFS processes elements level-by-level, it's perfect for measuring increasing distances from a starting point (in this case, the gates).
We pop coordinates from the queue and explore its neighbors (rooms to the left, right, up, and down). If we find an empty room (with INF), it's apparent that this is the first time we reach this room (as the queue ensures the shortest paths are explored first), so we update the room's value to the current distance.
Since gates serve as the origin, distances increase as we move away from them. Each level deeper in the search increases the distance by one.
Neighbors that are walls or already visited with a smaller distance are skipped, as we are looking for the shortest path to a gate. We continue this process until there are no more rooms to explore.

This approach ensures that each empty room is attributed the shortest distance to the nearest gate by leveraging the level-order traversal characteristic of the BFS, which naturally finds the shortest path in an unweighted grid.

Learn more about Breadth-First Search patterns.

Solution Approach

The solution leverages the Breadth-First Search (BFS) algorithm, utilizing a queue to process each gate and its surrounding rooms iteratively. The queue data structure is chosen for its ability to handle FIFO (First-In-First-Out) operations, which is essential for BFS.

Here is a step-by-step breakdown of the implementation:

Initialization: The rooms grid is scanned for all gates (0 value rooms). Their coordinates are added to a deque, a double-ended queue. This is done because gates are our BFS starting points.
BFS Implementation:
- A while loop commences, indicating that we continue to process until the queue of gates and accessible rooms is empty.
- A nested for loop enables us to process rooms level-by-level. It iterates through the number of elements in the queue at the start of each level, to separate distances incrementally.
- Each room's coordinates are popped from the deque, and for each room, we check its four adjacent rooms (top, bottom, left, right).
Neighbor Checks: For every neighboring room, if the neighbor coordinates are within the bounds of the grid and the neighbor is an empty room (INF value), it means we've found the shortest path to that room from a gate. Therefore:
- The empty room is updated with the distance d, representing the number of levels from the gates we've traversed.
- This room's coordinates are then added to the queue for subsequent exploration of its neighbors.
Distance Increment: Once we've explored all rooms from the current level, we increment d by 1 to reflect the increased distance for the next level of rooms.

The algorithm concludes when there are no more rooms to explore (the queue is empty), ensuring all reachable empty rooms have been filled with the shortest distance to a gate, and non-reachable rooms are left as INF.

By using this approach, the solution efficiently updates the rooms with their minimum distances to the nearest gate in place, avoiding the creation of additional data structures and ensuring optimal space complexity.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a simple 3x3 grid example where -1 represents a wall, 0 represents a gate, and INF (represented as 2147483647 for the purpose of example) represents an empty room that needs its distance filled to the nearest gate.

Consider the following grid:

INF  -1  0
INF INF INF
INF  -1 INF

Here's how the Breadth-First Search (BFS) algorithm would update this grid:

Initialization:

We identify the gate at grid[0][2] and add its coordinates to the queue.

BFS Implementation:

Start with the gate in the queue: (0, 2).

Neighbor Checks:

The gate at (0, 2) has three neighbors: (0, 1), (0, 3), and (1, 2).
- However, (0, 1) is a wall and (0, 3) is out of bounds, so we only consider (1, 2).
Since (1, 2) is INF, we update it to the distance 1 (the current level), and add (1, 2) to the queue.

The grid now looks like this:

INF  -1  0
INF INF  1
INF  -1 INF

Distance Increment:

Increment d to 2 for the next level of rooms.

Continue BFS:

Now, (1, 2) is the only room in the queue. Its neighbors are (1, 1), (1, 3), (0, 2), and (2, 2).
- (1, 1) is updatable and becomes 2.
- (1, 3) is out of bounds.
- (0, 2) is a gate and already has the shortest distance.
- (2, 2) is updatable and becomes 2.

Add (1, 1) and (2, 2) to the queue.

The grid now looks like this:

INF  -1  0
 2  INF  1
INF  -1  2

Distance Increment:

Increment d to 3.

Next BFS level:

For (1, 1), neighbors are (1, 0), (1, 2), (0, 1), and (2, 1).
- (1, 0) is updatable and becomes 3.
- (2, 1) is updatable and becomes 3.

For (2, 2), the only neighbor not already checked or out of bounds is (2, 1), but it's already been updated this level.

Final updated grid:

INF  -1  0
 3    2    1
INF  -1  2

Notice that the top left room remains INF, as it is inaccessible. All other rooms have been updated to show the shortest path to the nearest gate.

Solution Implementation

1from collections import deque
2
3class Solution:
4    def wallsAndGates(self, rooms):
5        """
6        This method modifies the 'rooms' matrix in-place by filling each empty room with the distance to its nearest gate.
7      
8        An empty room is represented by the integer 2**31 - 1, a gate is represented by 0, and a wall is represented by -1.
9      
10        :type rooms: List[List[int]]
11        """
12      
13        # Dimensions of the rooms matrix
14        num_rows, num_cols = len(rooms), len(rooms[0])
15      
16        # Define the representation of an infinite distance (empty room)
17        INF = 2**31 - 1
18      
19        # Initialize a queue and populate it with the coordinates of all gates
20        queue = deque([(row, col) for row in range(num_rows) for col in range(num_cols) if rooms[row][col] == 0])
21      
22        # Initialize distance from gates
23        distance = 0
24      
25        # Perform a breadth-first search (BFS) from the gates
26        while queue:
27            # Increase the distance with each level of BFS
28            distance += 1
29          
30            # Process nodes in the current level
31            for _ in range(len(queue)):
32                i, j = queue.popleft()
33              
34                # Explore the four possible directions from the current cell
35                for delta_row, delta_col in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
36                    new_row, new_col = i + delta_row, j + delta_col
37                  
38                    # Check if the new position is within bounds and is an empty room
39                    if 0 <= new_row < num_rows and 0 <= new_col < num_cols and rooms[new_row][new_col] == INF:
40                        # Update the distance for the room
41                        rooms[new_row][new_col] = distance
42                      
43                        # Add the new position to the queue to process its neighbors
44                        queue.append((new_row, new_col))
45

1class Solution {
2    public void wallsAndGates(int[][] rooms) {
3        // get the number of rows and columns in the rooms grid
4        int numRows = rooms.length;
5        int numCols = rooms[0].length;
6      
7        // create a queue to hold the gate positions
8        Deque<int[]> queue = new LinkedList<>();
9      
10        // find all gates (represented by 0) and add their positions to the queue
11        for (int i = 0; i < numRows; ++i) {
12            for (int j = 0; j < numCols; ++j) {
13                if (rooms[i][j] == 0) {
14                    queue.offer(new int[] {i, j});
15                }
16            }
17        }
18      
19        // distance from the gate
20        int distance = 0;
21        // array to facilitate exploration in 4 directions: up, right, down, left
22        int[] directions = {-1, 0, 1, 0, -1};
23      
24        // perform BFS starting from each gate
25        while (!queue.isEmpty()) {
26            ++distance;
27            for (int i = queue.size(); i > 0; --i) {
28                // get and remove the position from the front of the queue
29                int[] position = queue.poll();
30                for (int j = 0; j < 4; ++j) { // explore all 4 directions
31                    int newRow = position[0] + directions[j];
32                    int newCol = position[1] + directions[j + 1];
33                    // if the new position is within bounds and is an empty room
34                    // (denoted by Integer.MAX_VALUE), then update the distance
35                    // and add the new position to the queue for further BFS
36                    if (newRow >= 0 && newRow < numRows && newCol >= 0 && newCol < numCols && rooms[newRow][newCol] == Integer.MAX_VALUE) {
37                        rooms[newRow][newCol] = distance;
38                        queue.offer(new int[] {newRow, newCol});
39                    }
40                }
41            }
42        }
43    }
44}
45

1class Solution {
2public:
3    void wallsAndGates(vector<vector<int>>& rooms) {
4        int rows = rooms.size(); // number of rows in the grid
5        int cols = rooms[0].size(); // number of columns in the grid
6        queue<pair<int, int>> toVisit; // queue to maintain BFS traversal from gates
7        vector<int> directions = {-1, 0, 1, 0, -1}; // directions for exploring adjacent rooms
8      
9        // Find all gates and enqueue their positions
10        for (int row = 0; row < rows; ++row) {
11            for (int col = 0; col < cols; ++col) {
12                if (rooms[row][col] == 0) {
13                    toVisit.emplace(row, col);
14                }
15            }
16        }
17      
18        // Distance from gate(s)
19        int distance = 0;
20
21        // Use BFS to traverse the grid
22        while (!toVisit.empty()) {
23            ++distance;
24            size_t levelSize = toVisit.size();
25            for (size_t i = 0; i < levelSize; ++i) {
26                auto position = toVisit.front(); // get the front element of the queue
27                toVisit.pop(); // remove it from the queue
28
29                for (int j = 0; j < 4; ++j) { // explore all 4 adjacent rooms
30                    int newRow = position.first + directions[j];
31                    int newCol = position.second + directions[j + 1];
32                  
33                    // Check for valid position and if the room has not been visited or is not a wall
34                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && rooms[newRow][newCol] == INT_MAX) {
35                        rooms[newRow][newCol] = distance; // set distance from nearest gate
36                        toVisit.emplace(newRow, newCol); // enqueue the valid position
37                    }
38                }
39            }
40        }
41    }
42};
43

1function wallsAndGates(rooms: number[][]): void {
2    const rows = rooms.length; // number of rows in the grid
3    const cols = rooms[0].length; // number of columns in the grid
4    const toVisit: Array<[number, number]> = []; // queue to maintain BFS traversal from gates
5    const directions: number[] = [-1, 0, 1, 0, -1]; // directions for exploring adjacent rooms
6
7    // Find all gates and enqueue their positions
8    for (let row = 0; row < rows; row++) {
9        for (let col = 0; col < cols; col++) {
10            if (rooms[row][col] === 0) {
11                toVisit.push([row, col]);
12            }
13        }
14    }
15  
16    // Distance from gate(s)
17    let distance = 0;
18
19    // Use BFS to traverse the grid
20    while (toVisit.length > 0) {
21        const levelSize = toVisit.length;
22        distance++;
23        for (let i = 0; i < levelSize; i++) {
24            const position = toVisit.shift(); // get the front element of the queue
25            if (position) {
26                const [currentRow, currentCol] = position;
27
28                // Explore all 4 adjacent rooms
29                for (let j = 0; j < 4; j++) {
30                    const newRow = currentRow + directions[j];
31                    const newCol = currentCol + directions[j + 1];
32                  
33                    // Check for valid position and if the room has not been visited or is not a wall
34                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && rooms[newRow][newCol] === Number.MAX_SAFE_INTEGER) {
35                        rooms[newRow][newCol] = distance; // set the distance from the nearest gate
36                        toVisit.push([newRow, newCol]); // enqueue the valid position
37                    }
38                }
39            }
40        }
41    }
42}
43

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(m * n), where m represents the number of rows and n the number of columns in the rooms matrix. This is because in the worst case, the code must visit each cell in the matrix once. Starting from each gate (where the value is 0), the algorithm performs a breadth-first search (BFS), updating distances to each room that is initially set to inf. Every room is pushed to and popped from the queue at most once. The BFS ensures that each room is visited only when we can potentially write a smaller distance. Hence, the time complexity is linear in the size of the input matrix.

Space Complexity

The space complexity of the given code is also O(m * n), since in the worst case, we could have a queue that contains all the cells (in the case where all rooms are reachable and no walls are present to block the spread). This queue is the dominant factor in the space complexity of the algorithm, as it could potentially hold a number of elements equal to the total number of rooms at once. The additional space used by the BFS for coordinates and related computations is negligible compared to the size of the queue.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don’t know