LeetCode Solutions Blog

Count Unguarded Cells in the Grid

Number: 2343

Difficulty: Medium

Paid? No

Problem Description

Given an m x n grid, some cells are occupied by guards and walls. A guard “sees” (or defends) every cell in the four cardinal directions (north, east, south, west) from their position until their view is blocked by a wall or another guard. The task is to count how many cells remain that are unoccupied (i.e. not a wall or guard) and unguarded (i.e. not seen by any guard).

Key Insights

Represent the grid as a 2D array. Since m * n is bounded by 10^5, it is efficient to use a grid even if m or n individually may be large.
Mark positions occupied by walls and guards with distinct markers.
For each guard, simulate the four directions. Continue marking cells as guarded until a wall or another guard is encountered.
Count the cells that remain unmarked (thus, unoccupied by walls/guards and unguarded).

Space and Time Complexity

Time Complexity: O(m * n + g * (direction length)), where g is the number of guards. In worst-case, it is O(m * n) since m * n ≤ 10^5. Space Complexity: O(m * n) for storing the grid.

Solution

We solve the problem by first initializing a grid with default values. We mark walls and guards in the grid. Then, for every guard, we simulate spreading in all four cardinal directions (up, down, left, right). In each direction, we continue marking cells as “guarded” until we hit a wall or another guard. Finally, we iterate over the grid to count cells that are not occupied (by a guard or wall) and not marked guarded. This approach leverages simple grid simulation with careful bounds checking.

Code Solutions

# Python solution for counting unguarded cells in the grid

def countUnguarded(m, n, guards, walls):
    # Create a grid and initialize all cells to 0 (unguarded & empty)
    grid = [[0] * n for _ in range(m)]
    
    # Mark walls in the grid with -1
    for row, col in walls:
        grid[row][col] = -1
    
    # Mark guards in the grid with -2
    for row, col in guards:
        grid[row][col] = -2

    # Define the four cardinal directions: up, right, down, left
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    
    # Process each guard and mark cells seen by the guard as 1 (guarded)
    for guard_row, guard_col in guards:
        for d_row, d_col in directions:
            r, c = guard_row + d_row, guard_col + d_col
            # Continue in the direction until boundary or an obstacle is encountered
            while 0 <= r < m and 0 <= c < n and grid[r][c] != -1 and grid[r][c] != -2:
                # Mark the cell as guarded. If already marked, it remains guarded.
                grid[r][c] = 1
                r += d_row
                c += d_col

    # Count cells that are not occupied by a guard or wall, and that are not guarded.
    count = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 0:
                count += 1
    return count

# Example usage:
m = 4
n = 6
guards = [[0,0],[1,1],[2,3]]
walls = [[0,1],[2,2],[1,4]]
print(countUnguarded(m, n, guards, walls))  # Expected output: 7