Crack the Backend

Problem Statement

You are given an m×n grid rooms: -1 is a wall, 0 is a gate, and Integer.MAX_VALUE (or a large number) represents an empty room. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, leave the room as INF. Modify the grid in place. Distance is the number of steps (4-directional) through empty rooms.

Multi-source BFS: Start from all gates (value 0) at distance 0. When we first reach an empty room (INF), that is the shortest distance from any gate — set rooms[nr][nc] = d+1 and enqueue. Walls (-1) are never enqueued.

Key Observations

Enqueue all (r, c) where rooms[r][c] == 0 with distance 0. BFS: for each dequeued (r, c, d), check 4 neighbors; if rooms[nr][nc] == Integer.MAX_VALUE, set rooms[nr][nc] = d + 1 and enqueue (nr, nc, d+1). This way each room is updated the first time we reach it (shortest path from any gate).

Approach

High-level: Queue all cells (r,c) with rooms[r][c]==0 (dist 0). BFS: for each (r,c,d), for each 4-neighbor with rooms[nr][nc]==Integer.MAX_VALUE set rooms[nr][nc]=d+1 and enqueue (nr,nc,d+1).

Implementation

Java

public void wallsAndGates(int[][] rooms) {
    Queue<int[]> q = new ArrayDeque<>();

    for (int i = 0; i < rooms.length; i++)
    for (int j = 0; j < rooms[0].length; j++)
    if (rooms[i][j] == 0) {
        q.offer(new int[]{i, j, 0});
    }

    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};

    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int r=cur[0], c=cur[1], d=cur[2];

        for (int[] dir : dirs) {
            int nr=r+dir[0], nc=c+dir[1];

            if (nr>=0&&nr<rooms.length&&nc>=0&&nc<rooms[0].length&&rooms[nr][nc]==Integer.MAX_VALUE) {
                rooms[nr][nc] = d + 1;
                q.offer(new int[]{nr, nc, d + 1});
            }
        }
    }
}

Test Cases

Standard

Input

rooms with INF, 0, -1

Expected

INF replaced with distances

Explanation

Each room gets min distance to gate.

Complexity Analysis

Time: O(m*n).
Space: O(m*n).

Follow-ups

Multiple gate types; obstacles.