Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each guard sees along four straight rays until a wall, another guard, or the boundary blocks it. Guarded cells do not block sight, so occupied obstacles and already-seen cells must be tracked separately.

Approach

Put walls and guards into an obstacle set and also into a seen set of cells that cannot be counted as unguarded. Queue four directed rays from each guard. Advance a ray one cell at a time, stopping only out of bounds or at an obstacle; otherwise mark the cell seen and continue in the same direction. Let rays cross already-seen cells because visibility may extend farther. Return the grid area minus the number of seen cells, excluding both occupied and guarded positions.

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)] # n,s,e,w
        obstacles = set()
        seen = set()

        for r, c in walls:
            seen.add((r, c))
            obstacles.add((r, c))

        q = deque()
        for r, c in guards:
            seen.add((r, c))
            obstacles.add((r, c))
            for d in range(4):
                q.append((r, c, d))

        while q:
            r, c, d = q.popleft()
            dr, dc = dirs[d]
            nr = r + dr
            nc = c + dc
            if nr < 0 or nr >= m or nc < 0 or nc >= n or (nr, nc) in obstacles:
                continue
            q.append((nr, nc, d))
            seen.add((nr, nc))

        return (n * m) - len(seen)

Complexity analysis

For an m by n grid with g guards and w walls, time is O(mn + g + w) = O(mn) with expected constant-time hash operations. Although rays cross seen cells, any cell is visited at most once from each direction: the nearest guard blocks rays from farther guards on that line. Boundary/obstacle stops add O(g) work. The sets store O(mn) cells and the queue holds at most four active rays per guard, so auxiliary space is O(mn). Python deque and the JavaScript linked queue both remove their heads in O(1) time.