Walls and Gates

Share

Given a 2D grid with INF (empty room), -1 (wall), 0 (gate), fill each empty room with the distance to its nearest gate. If impossible, leave as INF.

Example 1
Input: [[INF,-1,0,INF],[INF,INF,INF,-1],[INF,-1,INF,-1],[0,-1,INF,INF]] → Fill distances from gates

Solution Approach

Multi-source BFS starting from all gates (0-valued cells) simultaneously. Each BFS level adds 1 to the distance.

  • Add all gate positions (value==0) to BFS queue.
  • BFS outward: for each current cell, try 4 neighbors.
  • If neighbor is INF (unvisited room): set dist = current+1, add to queue.
  • Walls (-1) are skipped.
Java
import java.util.*;

class Solution {
    public void wallsAndGates(int[][] rooms) {
        int m = rooms.length, n = rooms[0].length;
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (rooms[i][j] == 0) q.offer(new int[]{i,j});
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] d : dirs) {
                int r = cur[0]+d[0], c = cur[1]+d[1];
                if (r>=0 && r<m && c>=0 && c<n && rooms[r][c] == Integer.MAX_VALUE) {
                    rooms[r][c] = rooms[cur[0]][cur[1]] + 1;
                    q.offer(new int[]{r,c});
                }
            }
        }
    }
}
  • Time Complexity: O(M*N)
  • Space Complexity: O(M*N)