_286. Walls and Gates.md

286. Walls and Gates

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 15, 2024

Last updated : June 15, 2024

---

Related Topics : Array, Breadth-First Search, Matrix

Acceptance Rate : 62.25 %

---

Solutions

• m286 v1 Recurse and Replace.py
• m286 v2 iterative queue.py

Python

m286 v1 Recurse and Replace.py

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        
        def helper(startRow: int, startCol: int, count: int) -> None :
            if startRow < 0 \
                or startCol < 0 \
                or startRow >= len(rooms) \
                or startCol >= len(rooms[0]) :
                return

            if rooms[startRow][startCol] <= count or rooms[startRow][startCol] == -1 :
                return

            if rooms[startRow][startCol] == 0 :
                return

            rooms[startRow][startCol] = min(count, rooms[startRow][startCol])
            count += 1
            helper(startRow + 1, startCol, count)
            helper(startRow - 1, startCol, count)
            helper(startRow, startCol + 1, count)
            helper(startRow, startCol - 1, count)


        for i in range(len(rooms)) :
            for j in range(len(rooms[0])) :
                if rooms[i][j] == 0 :
                    helper(i + 1, j, 1)
                    helper(i - 1, j, 1)
                    helper(i, j + 1, 1)
                    helper(i, j - 1, 1)

m286 v2 iterative queue.py

''' This should in theory be faster than V1 since we don't have to overwrite previous
    calculations. 
    
    In the other version, we try each gate, and the spreading will occur until it reaches
    a point where it's no longer shorter, meaning each will be around the mid-point of it 
    and its nearest alternative gate.
    
    In this case, since we're iterate outwards from each gate at the same time, the moment
    visits a spot that's been visited, we know that that spot has been reached by a path
    either shorter or equal, so we can end there immediately.
'''

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        
        toVisit = deque()       # (row, col, stepsSoFar)
        visited = set()

        # Gate locations
        for i in range(len(rooms)) :
            for j in range(len(rooms[0])) :
                if not rooms[i][j] :
                    visited.add((i, j))             # Add gates so we don't overwrite
                    toVisit.append((i + 1, j, 1))
                    toVisit.append((i - 1, j, 1))
                    toVisit.append((i, j + 1, 1))
                    toVisit.append((i, j - 1, 1))

        while toVisit :
            row, col, stepsSoFar = toVisit.popleft()

            if not (0 <= row < len(rooms)) or not (0 <= col < len(rooms[0])) :
                continue
            
            if rooms[row][col] == -1 :
                continue

            # In theory, we should be going in increasing 
            # step order so we don't have to compare the 
            # values with the current value
            if (row, col) in visited :
                continue
            visited.add((row, col))

            rooms[row][col] = stepsSoFar
            stepsSoFar += 1

            toVisit.append((row + 1, col, stepsSoFar))
            toVisit.append((row - 1, col, stepsSoFar))
            toVisit.append((row, col + 1, stepsSoFar))
            toVisit.append((row, col - 1, stepsSoFar))