286.Walls_and_Gates(Medium).md

286. Walls and Gates (Medium)

Date and Time: Sep 26, 2024, 15:15 (EST)

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

Question:

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 2^31 - 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.

Example 1:

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

Example 2:

Input: rooms = [[-1]]

Output: [[-1]]

Constraints:

• m == rooms.length

• n == rooms[i].length

• 1 <= m, n <= 250

• rooms[i][j] is -1, 0, or 2^31 - 1.

Walk-through:

Loop over rooms to find all gates(0) and add their (pos, steps) into deque[], then we start traversing BFS from these gates in four directions and if there is an empty room, we update rooms[r][c] = steps + 1. Next, we append the new traversed rooms into deque.

Python Solution:

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        deque = collections.deque()  # [pos, steps]
        rows, cols = len(rooms), len(rooms[0])
        for r in range(rows):
            for c in range(cols):
                if rooms[r][c] == 0:
                    deque.append(([r, c], 0))

        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        while deque:
            pos, steps = deque.popleft()
            row, col = pos
            for dr, dc in directions:
                r, c = row + dr, col + dc
                if r in range(rows) and c in range(cols) and rooms[r][c] == 2147483647:
                    rooms[r][c] = steps + 1
                    deque.append(([r, c], steps + 1))

Time Complexity: $O(m * n)$, m * n is the size of rooms, we only traverse the whole rooms in the worst case.
Space Complexity: $O(m * n)$