Problem statement

https://leetcode.com/problems/walls-and-gates/

Solution

Just perform classical bfs, where at the beginning we put all gates to our queue. Then on each iteration extract node from queue, check neighbours and if they are not visited, add them to queue.

Complexity

Time complexity is $O(mn)$, space is $O(mn)$ as well, because potentially queue can have this size.

Code

class Solution:
    def wallsAndGates(self, rooms):
        m, n = len(rooms), len(rooms[0])
        queue = deque()
        
        for i, j in product(range(m), range(n)):
            if rooms[i][j] == 0:
                queue.append((0, i, j))
                    
        while queue:
            dist, x, y = queue.popleft()
            for dx, dy in [(x, y+1), (x, y-1), (x-1, y), (x+1, y)]:
                if 0 <= dx < m and 0 <= dy < n and rooms[dx][dy] == 2**31 - 1:
                    rooms[dx][dy] = dist + 1
                    queue.append((dist + 1, dx, dy))