LeetCode 286: Walls and Gates Solution in Python – A Step-by-Step Guide

What Is LeetCode 286: Walls and Gates?

In LeetCode 286: Walls and Gates, you’re given a 2D grid rooms where each cell is one of three things: a gate (0), a wall (-1), or an empty room (INF, representing infinity). Your goal is to update every empty room with its shortest distance to any gate, moving only up, down, left, or right through empty rooms or gates—walls block your path. For example, a grid like [[INF, -1, 0], [INF, INF, INF], [0, -1, INF]] becomes [[2, -1, 0], [1, 2, 1], [0, -1, 2]]. This problem tests your ability to search grids efficiently, sharing vibes with classics like LeetCode 994: Rotting Oranges.

Problem Statement

• Input: A 2D integer array rooms with values: 0 (gate), -1 (wall), INF (empty room).
• Output: The array rooms, modified in-place with distances to the nearest gate.
• Rules: Move in four directions; walls are impassable; use shortest distance; modify in-place.

Constraints

• Grid size: m x n, where m, n ≤ 250.
• Values: -1, 0, or 2³¹ - 1 (INF).

Examples

• Input: rooms = [[INF, -1, 0, INF], [INF, INF, INF, -1], [INF, -1, INF, -1], [0, -1, INF, INF]]
• Output: [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]
• Input: rooms = [[0, INF]]
• Output: [[0, 1]]
• Input: rooms = [[INF]]
• Output: [[INF]] (no gate, stays INF)

Understanding the Problem: Mapping the Distances

To solve LeetCode 286: Walls and Gates in Python, we need to fill each INF cell in rooms with the shortest distance to a gate, moving through gates or empty rooms but not walls. A brute-force approach—searching from each room to find a gate—would be slow. Instead, we’ll flip it: start from gates and spread distances outward. We’ll use: 1. Best Solution (BFS from Gates): O(mn) time, O(mn) space—optimal and clear. 2. Alternative Solution (DFS): O(mn) time, O(mn) space—recursive but less efficient in practice.

Let’s dive into the BFS solution with a beginner-friendly explanation.

Best Solution: BFS from Gates

Why This Is the Best Solution

The BFS approach is the star for LeetCode 286 because it’s perfectly suited for finding shortest paths—running in O(mn) time—and uses O(mn) space for the queue, which is reasonable given the grid size. Starting from all gates at once ensures every room gets its minimum distance in one pass, layer by layer. For beginners, it’s like sending out ripples from each gate—the closest ripple to hit a room sets its distance!

How It Works

Picture this as a flood starting at the gates: water flows out in all four directions, marking each room with how many steps it took to get there, stopping at walls. We use a queue to process cells level-by-level:

• Step 1: Queue All Gates:
• Scan the grid, adding every gate (0) to a queue with its coordinates.
• Step 2: BFS Spread:
• Pop a cell from the queue (start with gates at distance 0).
• For each neighbor (up, down, left, right):
• If it’s an empty room (INF) and unvisited (or farther), update its distance and add it to the queue.
• Step 3: Why It Works:
• BFS ensures we visit cells in order of increasing distance (0, 1, 2...).
• Starting from gates guarantees the first distance set is the shortest.
• In-place updates meet the problem’s requirement.
• Step 4: Result:
• Grid shows shortest distances from each room to a gate.

It’s like a wave spreading out—closest gate wins!

Step-by-Step Example

Example: rooms = [[INF, -1, 0], [INF, INF, INF], [0, -1, INF]]

• Initial: [[INF, -1, 0], [INF, INF, INF], [0, -1, INF]].
• Queue Gates: [(0, 2, 0), (2, 0, 0)] (row, col, distance).
• BFS:
• (0, 2, 0): Right of gate—(0, 3) out of bounds; down—(1, 2, 1): INF → 1, queue.
• (2, 0, 0): Up—(1, 0, 1): INF → 1, queue; left—out; right—(2, 1) is -1.
• (1, 2, 1): Up—(0, 2) is 0; right—out; down—(2, 2, 2): INF → 2, queue; left—(1, 1, 2): INF → 2, queue.
• (1, 0, 1): Up—(0, 0, 2): INF → 2, queue; down—(2, 0) is 0; left—out; right—(1, 1) updated later.
• (2, 2, 2): All neighbors done or walls.
• (1, 1, 2): Already 2, no update.
• (0, 0, 2): Done.
• Result: [[2, -1, 0], [1, 2, 1], [0, -1, 2]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained simply:

Copy codefrom collections import deque

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        if not rooms or not rooms[0]:
            return

        # Step 1: Constants and setup
        INF = 2**31 - 1
        rows, cols = len(rooms), len(rooms[0])
        queue = deque()

        # Step 2: Add all gates to queue
        for r in range(rows):
            for c in range(cols):
                if rooms[r][c] == 0:
                    queue.append((r, c, 0))

        # Step 3: BFS to spread distances
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # Up, down, left, right
        while queue:
            row, col, dist = queue.popleft()
            for dr, dc in directions:
                new_r, new_c = row + dr, col + dc
                # Check bounds and if it’s an empty room
                if (0 <= new_r < rows and 0 <= new_c < cols and 
                    rooms[new_r][new_c] == INF):
                    rooms[new_r][new_c] = dist + 1
                    queue.append((new_r, new_c, dist + 1))

• Line 6-8: Handle empty grid case.
• Line 10-14: Define INF; get grid size; queue for BFS; find gates and add them with distance 0.
• Line 16-25: BFS loop:
• Pop current cell with its distance.
• Check all four neighbors.
• If in bounds and INF, update with dist+1 and queue it.
• No return: Modifies rooms in-place.

• Time Complexity: O(m*n)—each cell visited once.
• Space Complexity: O(m*n)—queue may hold many cells.

This solution is like a flood of distances—smooth and precise!

Alternative Solution: DFS

Why an Alternative Approach?

DFS explores paths from each gate recursively, updating distances as it goes—O(mn) time but potentially O(mn) space due to recursion. It’s less optimal than BFS for shortest paths (since DFS goes deep first), but it’s a fun way to see the problem differently, like exploring tunnels from each gate.

How It Works

Imagine starting at a gate and digging through the grid, marking distances as you go, backtracking when you hit walls:

• Step 1: Find gates and launch DFS from each.
• Step 2: Recursively explore neighbors, updating INF cells if the new distance is shorter.
• Step 3: Stop at walls or already-visited smaller distances.

It’s like a deep dive from each gate!

Step-by-Step Example

Example: rooms = [[INF, -1, 0], [INF, INF, INF]]

• Initial: [[INF, -1, 0], [INF, INF, INF]].
• DFS from (0, 2, 0):
• Down: (1, 2, 1) → INF to 1.
• Left: (1, 1, 2) → INF to 2.
• Left: (1, 0, 3) → INF to 3.
• Up: (0, 0, 4) → INF to 4.
• Result: [[4, -1, 0], [3, 2, 1]].

Code for DFS Approach

Copy codeclass Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        if not rooms or not rooms[0]:
            return

        INF = 2**31 - 1
        rows, cols = len(rooms), len(rooms[0])

        def dfs(r: int, c: int, dist: int):
            if (r < 0 or r >= rows or c < 0 or c >= cols or 
                rooms[r][c] < dist):  # Wall or shorter path found
                return
            rooms[r][c] = dist
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                dfs(r + dr, c + dc, dist + 1)

        for r in range(rows):
            for c in range(cols):
                if rooms[r][c] == 0:
                    dfs(r, c, 0)

• Time Complexity: O(m*n)—visits each cell.
• Space Complexity: O(m*n)—recursion stack.

It’s a recursive adventure, but BFS is faster for shortest paths.

Comparing the Two Solutions

• BFS (Best):
• Pros: O(m*n) time, guarantees shortest path, intuitive.
• Cons: O(m*n) queue space.
• DFS (Alternative):
• Pros: O(m*n) time, recursive clarity.
• Cons: O(m*n) stack space, less efficient for shortest paths.

BFS wins for this problem.

Additional Examples and Edge Cases

• All Walls: [[-1]] → [[-1]].
• Single Gate: [[0]] → [[0]].
• No Gates: [[INF, -1]] → [[INF, -1]].

Both handle these fine.

Complexity Breakdown

• BFS: Time O(m*n), Space O(m*n).
• DFS: Time O(m*n), Space O(m*n).

BFS is the practical choice.

Key Takeaways

• BFS: Spread from gates—shortest paths!
• DFS: Dive deep—recursive fun!
• Grids: Queues and recursion rock.
• Python Tip: Loops and grids shine—see [Python Basics](/python/basics).

Final Thoughts: Gate Your Way Out

LeetCode 286: Walls and Gates in Python is a cool grid challenge. BFS maps distances perfectly, while DFS offers a recursive twist. Want more? Try LeetCode 994: Rotting Oranges or LeetCode 542: 01 Matrix. Ready to navigate? Head to Solve LeetCode 286 on LeetCode and measure those distances today!