Walls and Gates

Walls and Gates is a classic coding interview problem involving a 2D grid where you calculate distances from empty rooms to the nearest gates using BFS. It's commonly tagged with Array, BFS, and Matrix, and frequently appears in Meta (Facebook) interviews.[1][7]

Problem Statement

You are given an m x n 2D grid with these values:

• -1 represents a wall or obstacle.
• 0 represents a gate.
• INF (2^31 - 1 = 2147483647) represents an empty room.

Fill each empty room (INF) with the distance to its nearest gate, moving only up, down, left, or right. If unreachable, keep it as INF.[7][1]

Constraints

• 1 ≤ m, n ≤ 100 (grid dimensions).
• Distance to any gate is less than INF, so no overflow issues.
• Grid contains only -1, 0, or INF values.[1]

Example 1

Input: INF -1 0 INF INF INF INF 0 INF INF INF INF INF -1 INF INF

Output: 3 -1 0 1 2 2 1 0 1 2 2 1 1 -1 2 2 Distances fill from gates outward via multi-source BFS.[1]

Example 2

Input: 0 INF INF 0 INF INF INF INF INF 0 INF INF INF INF INF INF

Output: 0 1 2 0 1 2 3 1 1 0 1 2 2 1 2 3 All rooms reachable; unreachable ones stay INF (not shown here).[7]

Solution Approach

Use multi-source BFS: queue all gates (distance 0) initially, then expand layer-by-layer to empty rooms, updating distances only if improved. This ensures shortest paths in O(m*n) time.[2][1]