What is the brute force approach and complexity for Walls and Gates?

Run a separate BFS from each gate and keep the smallest distance for each room with time complexity O(G · R · C) and space complexity O(R · C).

What is the optimal approach and complexity for Walls and Gates?

Start with every gate in the queue; each empty room is filled the first time the wave reaches it with optimal time complexity O(R · C) and space complexity O(R · C).

How do you identify the pattern for Walls and Gates?

Look for key signals in the prompt: "the distance to the nearest gate" indicates Many starting points at once, and each room wants the closest one. Multi-source BFS gives this in one pass.; "walls cannot be passed" indicates Walls are simply never pushed. The search skips them, the same way it skips any cell it may not enter.; "INF for a room that no gate can reach" indicates A room the wave never reaches keeps its starting value, so no special check is needed at the end..

Walls and Gates

Medium·LeetCode #286 Premium Pro OnlySlight Variation

LeetCode

Problem Statement

You get a grid of rooms. Each cell is one of three things:

a wall (-1): nothing can pass through it,
a gate (0): a door out of the building,
an empty room (INF, which is 2147483647): it has not been filled yet.

Fill every empty room with the number of steps to its nearest gate. A step moves up, down, left or right to a neighbouring cell, and a path cannot go through a wall. If no gate can be reached from a room, it stays INF.

Change the grid in place. Walls and gates stay as they are.

Input

rooms, an m × n grid. Each cell is -1 (wall), 0 (gate) or INF (empty room).

Output

The same grid, changed in place: each empty room holds its distance to the nearest gate, or INF if no gate can be reached.

Example 1

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

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

The top row is filled from the top-left gate: 1, 2, 3. The room at (0,4) is 2 steps from the bottom-right gate, going up the open right-hand column. It is 4 steps from the top-left gate, so the shorter distance is the one kept.

Example 2

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

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

The wall in the middle forces paths to go round it. The room at (0,2) is 4 steps from the gate at (2,0): along the bottom row, then up past the wall.

Constraints

• m == rooms.length and n == rooms[i].length
• Each cell is -1, 0 or 2147483647 (INF) at the start.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“the distance to the nearest gate”

→ Many starting points at once, and each room wants the closest one. Multi-source BFS gives this in one pass.

“walls cannot be passed”

→ Walls are simply never pushed. The search skips them, the same way it skips any cell it may not enter.

“INF for a room that no gate can reach”

→ A room the wave never reaches keeps its starting value, so no special check is needed at the end.

Approach Complexity Ladder

Brute Force — a BFS from every gate, keep the smallestO(G · R · C)O(R · C)

Run a separate BFS from each gate and keep the smallest distance for each room

Optimal — all gates in the queue at onceO(R · C)O(R · C)

Start with every gate in the queue; each empty room is filled the first time the wave reaches it

Brute Force Intuition

For each gate, run a BFS over the rooms that starts from that gate alone. Write each reached room's distance into a second grid, keeping the smallest value seen so far. When every gate has been searched, that second grid is the answer. Each gate costs a full BFS, so most rooms are measured again from every gate.

Recognition rule for this sub-pattern:

Many starting points spread at the same time — push all of them into the queue first.

Remember this · Graph BFS / DFS

Trigger

Grid of cells, islands, regions, "minimum steps", transformations between states, connected components.

Think

What is a node, what is an edge, and do I need the shortest path or just reachability?

Key question

How do I mark visited so I never process a node twice?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Food Delivery System (Zomato / DoorDash)

Geospatial indexing and shortest dispatch routing for delivery partners.

Explore Track

C++ Internals

Virtual Method Table (vtable) & Dynamic Dispatch

Polymorphic graph nodes and state machine execution overhead.

Explore Track

01 Matrix Map of Highest Peak