Walls and Gates

Walls and Gates

What is this problem about?

The Walls and Gates coding problem is a classic grid-based challenge. You are given an m x n grid initialized with three possible values: -1 representing a wall or an obstacle, 0 representing a gate, and INF (a large integer) representing an empty room. The task is to fill each empty room with the distance to its nearest gate. If it's impossible to reach a gate, the room should remain INF. This problem simulates finding the shortest path in a labyrinth or a building layout.

Why is this asked in interviews?

Companies like Uber, Amazon, and Google frequently use this Walls and Gates interview question to evaluate a candidate's understanding of graph traversal. It specifically tests your ability to perform a Breadth-First Search (BFS) from multiple sources simultaneously. Handling multi-source BFS efficiently is a key skill for optimizing spatial queries and pathfinding algorithms in real-world applications like maps or logistics.

Algorithmic pattern used

The most efficient approach for this problem is the Breadth-First Search (BFS) interview pattern, specifically multi-source BFS. Instead of starting a BFS from every empty room (which would be highly inefficient), you start by adding all gate coordinates to a queue. Then, you traverse outward from all gates at once. This ensures that when you first reach an empty room, you have found the shortest possible distance to any gate.

Example explanation

Imagine a 3x3 grid: INF -1 0 INF INF INF 0 -1 INF

1. Start BFS from gates at (0,2) and (2,0).
2. Level 1: (0,2) reaches (1,2) with distance 1. (2,0) reaches (1,0) with distance 1.
3. Level 2: (1,2) reaches (1,1) with distance 2. (1,0) also reaches (1,1), but since it already has a distance, we don't update it. (1,2) reaches (2,2) with distance 2. Final grid: 3 -1 0 2 2 1 0 -1 2

Common mistakes candidates make

A common error is using Depth-First Search (DFS) instead of BFS. While DFS can eventually find a path, it doesn't naturally find the shortest path without significant extra work, often leading to a Time Limit Exceeded (TLE) error. Another mistake is performing a separate BFS for every single empty room, which results in O(k * m * n) complexity (where k is the number of rooms), whereas multi-source BFS is O(m * n).

Interview preparation tip

Whenever you need to find the shortest distance from multiple targets in a grid, think of Multi-Source BFS. Practice implementing it by initializing your queue with all starting points. This pattern is widely applicable to many "distance to nearest X" problems.