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.

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:

1. First, we identify all gate locations as starting points since we need to find the minimum distance from these gates to each room.

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

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

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

5. 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:

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

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

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

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

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:

1INF  -1  0
2INF INF INF
3INF  -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:

1INF  -1  0
2INF INF  1
3INF  -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:

1INF  -1  0
2 2  INF  1
3INF  -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:

1INF  -1  0
2 3    2    1
3INF  -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

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.