Count Unguarded Cells in the Grid

main.md

Question

Approach

I build a 2D grid representation where I mark walls and guards, then for each guard I scan outward in the four cardinal directions until I hit a wall or another guard, marking every empty cell I pass as guarded. Finally I count grid cells that are still empty and unguarded. This works because the product m * n ≤ 1e5, so an explicit grid and linear scans are efficient.

Implementation

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        grid = [[0] * n for _ in range(m)]
        
        for r, c in walls:
            grid[r][c] = -1
        for r, c in guards:
            grid[r][c] = 1
        
        dirs = [(0,1),(0,-1),(1,0),(-1,0)]
        for gr, gc in guards:
            for dr, dc in dirs:
                r, c = gr + dr, gc + dc
                while 0 <= r < m and 0 <= c < n:
                    if grid[r][c] == -1 or grid[r][c] == 1:
                        break
                    grid[r][c] = 2
                    r += dr
                    c += dc
        
        cnt = 0
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 0:
                    cnt += 1
        return cnt

Complexities

• Time: O(m×n)
• Space: O(m×n)