Is Walls and Gates easy or hard?

Walls and Gates is generally considered a medium difficulty problem. The grid traversal itself is straightforward, but the key insight is reversing the search and running BFS from all gates instead of each empty room.

Walls and Gates Python/Java solution

Most solutions implement multi-source BFS using a queue. Gates are first pushed into the queue, then neighbors are explored in four directions while updating distances. This approach works the same across Python, Java, C++, and Go with O(mn) time complexity.

How to solve Walls and Gates in O(n)?

Treat all gates as starting nodes and perform a multi-source BFS. Insert every gate into a queue with distance 0, then expand level by level updating adjacent empty rooms with distance +1. Because each cell is processed once, the runtime becomes O(mn), which is linear in the number of grid cells.

What is the best approach for Walls and Gates?

The best approach is multi-source Breadth-First Search (BFS). Instead of running BFS from every empty room, push all gates into the queue first and expand outward. BFS guarantees the first time a room is reached is the shortest distance to a gate. This reduces the complexity to O(mn).

Is Walls and Gates asked at Google/Amazon/Meta?

Walls and Gates is a common grid BFS interview problem and has appeared in interviews at companies like Google, Amazon, and Meta. It tests understanding of shortest path traversal, BFS layering, and matrix traversal patterns frequently used in system and graph problems.

What data structure is used in Walls and Gates?

The core data structure is a queue used for Breadth-First Search. The grid itself acts as the state storage where distances are updated in-place. BFS ensures level-by-level expansion so each room gets the minimum distance to a gate.

What is the time complexity of Walls and Gates?

The optimal solution runs in O(mn) time where m and n are the grid dimensions. Each cell is visited at most once during the BFS traversal. Every step processes up to four neighbors, making the algorithm linear with respect to the number of cells.

286. Walls and Gates - Practice Online

You are given an m x n grid rooms initialized with these three possible values.

-1 A wall or an obstacle.
0 A gate.
INF Infinity means an empty room. We use the value 2³¹ - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Example 1:

Input: rooms = [[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]]

Example 2:

Input: rooms = [[-1]]
Output: [[-1]]

Constraints:

m == rooms.length
n == rooms[i].length
1 <= m, n <= 250
rooms[i][j] is -1, 0, or 2³¹ - 1.