Walls And Gates Leetcode Problem 286 [Python Solution]

In this blog post, we’re going to tackle a medium-difficulty LeetCode problem called Walls And Gates This problem falls under the category of graph problems and is often asked by companies like Amazon.

We’ll provide a Python solution to this problem and delve into the reasoning behind our approach.

Before we get started, let’s take a look at the problem statement.

Problem Overview

You are given an m x n 2D grid initialized with three possible values:

• -1 – A wall or an obstacle.
• 0 – A gate.
• INF – Infinity, which means an empty room.

We use the value 2^31 - 1 = 2147483647 to represent INF because we can assume that the distance to a gate is less than 2147483647.

The task is to fill each empty room with the distance to its nearest gate.

If it is impossible to reach a gate, that room should remain filled with INF.

Let’s break this down further with an example:

Example:

Input:

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

Output:

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

In this example, the 2D grid contains three types of cells: walls (denoted by -1), gates (denoted by 0), and empty rooms (denoted by INF).

The task is to fill each empty room with the distance to the nearest gate.

If a room cannot reach a gate, it should remain as INF.

Understanding the Constraints

Before we dive into the solution, let’s understand the problem constraints:

• The grid can have m rows and n columns.
• The values in the grid can be -1, 0, or INF.
• The distance to the nearest gate is represented by an integer.

Now, let’s move on to the solution for this problem.

Walls And Gates LeetCode Problem Solution

To solve this problem efficiently, we will use a Breadth-First Search (BFS) approach.

We will perform BFS from all the gates simultaneously to explore the distances to each empty room.

1. Bruteforce Approach:

Before we dive into the efficient solution, let’s briefly explore a naive approach:

One naive approach would be to iterate through the entire grid, and for each empty room, perform a BFS search starting from that room and stopping once we reach a gate.

This way, we can find the distance to the nearest gate for each room.

However, this approach is inefficient and would result in a time complexity of O(m * n)^2. We can do better.

2. An Efficient Approach with Python Code:

Here’s the Python solution that efficiently solves the Walls and Gates problem using BFS:

from collections import deque
from typing import List

class Solution:
    def walls_and_gates(self, rooms: List[List[int]):
        ROWS, COLS = len(rooms), len(rooms[0])
        visit = set()
        q = deque()

        def addRooms(r, c):
            if (
                min(r, c) < 0
                or r == ROWS
                or c == COLS
                or (r, c) in visit
                or rooms[r][c] == -1
            ):
                return
            visit.add((r, c))
            q.append([r, c])

        for r in range(ROWS):
            for c in range(COLS):
                if rooms[r][c] == 0:
                    q.append([r, c])
                    visit.add((r, c))

        dist = 0
        while q:
            for i in range(len(q)):
                r, c = q.popleft()
                rooms[r][c] = dist
                addRooms(r + 1, c)
                addRooms(r - 1, c)
                addRooms(r, c + 1)
                addRooms(r, c - 1)
            dist += 1

In this solution, we define a Solution class with a method walls_and_gates.

Let’s break down the key steps in this solution:

• We use a deque from the collections module to implement the BFS algorithm.
• We traverse the grid and add gates (value 0) to the queue while marking them as visited.
• We perform BFS from the gates, updating the distances to empty rooms as we go.

This efficient approach ensures that we visit each room at most once, leading to a linear time complexity, O(m * n), which is much better than the naive approach.

Time and Space Complexity

Now that we have explored the solution, let’s discuss the time and space complexity of our algorithm.

• Time Complexity: The time complexity of our solution is O(m * n), where m is the number of rows, and n is the number of columns in the grid.

We visit each room at most once, and the BFS process efficiently fills in the distances.

• Space Complexity: The space complexity is also O(m * n).

We use a deque to store positions, and the visit set ensures we don’t revisit the same room.

Reasoning Behind Our Approach

The reasoning behind our approach is to efficiently explore the grid and calculate the distances to the nearest gates.

We utilize BFS to simultaneously process multiple gates and ensure that each room is visited only once.

This approach is more efficient than the naive approach of performing a separate BFS from each empty room.

By starting the BFS from the gates and gradually expanding the search, we can accurately determine the distance from each empty room to the nearest gate.

This optimizes the time complexity, making it suitable for larger grids.

Related Interview Questions By Company:

• House Robber LeetCode
• Design Circular Queue LeetCode
• Best Time To Buy And Sell Stock With Cooldown LeetCode

Related Interview Questions By Difficulty:

• Redundant Connection LeetCode
• Shortest Path In Binary Matrix LeetCode
• Course Schedule LeetCode

Related Interview Questions By Category:

• Lowest Common Ancestor Of A Binary Search Tree LeetCode
• Move Zeroes LeetCode
• Simplify Path LeetCode

Conclusion

In this blog post, we tackled the LeetCode problem Walls And Gates We provided an efficient Python solution using a Breadth-First Search (BFS) approach to find the distances from empty rooms to the nearest gates.

This solution ensures a linear time complexity, making it suitable for practical use.

We hope this explanation and solution have been helpful to you.

If you have any questions, suggestions, or comments, please feel free to share them.

You can also explore the problem further on the LeetCode website.

We encourage you to continue learning and exploring coding challenges, and don’t forget to like and engage for more coding content.

Happy coding!