Coding

Walls and Gates

Asked at

Amazon

BitGo

Blinkit

Spotify

UrbanCompany

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

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 231 - 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.

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]]

Input:rooms = [[-1]] Output: [[-1]] Explanation : There are No empty rooms

Input:rooms = [ [2147483647, 2147483647, 2147483647, 2147483647, 2147483647], [2147483647, -1, 2147483647, 2147483647, 2147483647], [2147483647, 2147483647, 0, 2147483647, -1], [2147483647, 2147483647, 2147483647, 2147483647, 2147483647], [2147483647, 0, 2147483647, 2147483647, 2147483647] ]

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

cpp

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        // Your code goes here
    }
};

java

class Solution {
    public void wallsAndGates(int[][] rooms) {
        // Your code goes here
    }
}

python

class Solution(object):
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: None Do not return anything, modify rooms in-place instead.
        """
        # Your code goes here

javascript

/**
 * @param {number[][]} rooms
 * @return {void} Do not return anything, modify rooms in-place instead.
 */
var wallsAndGates = function(rooms) {
    // Your code goes here
};

csharp

public class Solution
{
    public void WallsAndGates(int[][] rooms)
    {
        // Your code goes here
    }
}

func wallsAndGates(rooms [][]int) {
    //your code goes here
}

Stuck? Show a way to structure it+

01Enqueue all gates before traversal because every gate is a distance-zero source.
02Run four-direction BFS and visit only rooms whose value is INF.
03Set each newly reached room to its parent's distance plus one before enqueueing it.
04Leave walls and unreachable INF rooms unchanged.

Reference answer

This is an unweighted shortest-distance problem with multiple sources. Put every gate, whose value is 0, into one queue before BFS begins. There is no need to start a separate search from every empty room or every gate.

Pop a cell and inspect its four neighbors. Skip out-of-bounds cells, walls, gates, and rooms that no longer equal INF. For an untouched empty room, set its value to rooms[current] + 1 and enqueue it immediately. Because BFS processes positions in nondecreasing distance from the complete set of gates, the first time an empty room is reached is through a nearest gate. Writing the distance also doubles as the visited marker.

Rooms blocked from every gate are never enqueued and remain INF, as required. Walls remain -1. The algorithm visits each cell at most once, so time is O(mn) and worst-case queue space is O(mn). The key insight is initializing all gates together; sequential BFS runs can overwrite work or cost O(number of gates * mn).

Then expect these follow-ups

Why does the first visit to a room guarantee its nearest-gate distance?
Tests: BFS correctness
What algorithm would you use if moving between rooms had different costs?
Tests: algorithm selection

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question