Walls and Gates

Interview Problem Advanced Medium Island Traversal Multi-source BFS Matrix / Grid

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.wallsAndGates(rooms). -1 is a wall, 0 a gate, and 2147483647 an empty room. Fill each empty room with its shortest four-directional distance to a gate and return rooms.

Starter code

class Solution:
    def wallsAndGates(self, rooms):
        pass

Test cases

two-gates

{
  "args": [
    [
      [
        2147483647,
        -1,
        0,
        2147483647
      ],
      [
        2147483647,
        2147483647,
        2147483647,
        -1
      ],
      [
        2147483647,
        -1,
        2147483647,
        -1
      ],
      [
        0,
        -1,
        2147483647,
        2147483647
      ]
    ]
  ]
}

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

Wizard outline

Step 1: Initialize Solution.wallsAndGates
Replace the empty starter with the first real state owned by Solution.wallsAndGates. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Unreachable case
Complete the readable core algorithm for one representative Interview case. Seed BFS with all gates so the first visit to a room gives its globally shortest distance.
Step 4: Harden the Two Gates boundary
Repair the reviewed boundary and pass the complete submission contract. Multi-source BFS explores cells in nondecreasing distance from the nearest gate. Thus the first assignment to an empty room is its shortest distance; walls and previously assigned rooms are never crossed again.

Footguns and prerequisites

Running independent BFS from each room repeats work; multi-source traversal expands all gates together.
trees and graphs

Reviewed references

LeetCode 286 — Walls and Gates

Practice prerequisites

Expand a Multi-Source Frontier(opens in a new tab)
Expand a Multi-Source Frontier isolates every queued cell already has its minimum distance, because frontiers leave the queue in nondecreasing distance order. That focused state discipline is required when implementing walls and gates as a complete Interview Problem.

Recommended approach and implementation

Enqueue all gates. Pop a cell and assign each still-INF neighbor current+1 before enqueueing it.

Why it works: Multi-source BFS explores cells in nondecreasing distance from the nearest gate. Thus the first assignment to an empty room is its shortest distance; walls and previously assigned rooms are never crossed again.

class Solution:
    def wallsAndGates(self, rooms):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        if not rooms: return rooms
        from collections import deque
        rows, columns = len(rooms), len(rooms[0])
        queue = deque((r,c) for r in range(rows) for c in range(columns) if rooms[r][c] == 0)
        while queue:
            row, column = queue.popleft()
            for nr,nc in ((row+1,column),(row-1,column),(row,column+1),(row,column-1)):
                if 0 <= nr < rows and 0 <= nc < columns and rooms[nr][nc] == 2147483647:
                    rooms[nr][nc] = rooms[row][column] + 1
                    queue.append((nr,nc))
        return rooms

Similar exercises

Rotting Oranges(opens in a new tab)