#2257

Medium

LeetCode Problem Workspace

Count Unguarded Cells in the Grid

Solve Count Unguarded Cells in the Grid by marking guard sight lines across a blocked matrix and counting untouched empty cells.

array matrix simulation

Problem Statement

You have an m by n grid with some cells occupied by guards and some occupied by walls. Each guard watches horizontally and vertically from its own position, and that line of sight continues cell by cell until it hits a wall or another guard.

Your job is to count cells that are neither occupied nor visible to any guard. The key detail is that visibility is directional and blocked, so this is not a distance problem or a flood fill. You must model row and column sight lines carefully and avoid marking through obstacles.

Examples

Example 1

Input: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]

Output: 7

The guarded and unguarded cells are shown in red and green respectively in the above diagram. There are a total of 7 unguarded cells, so we return 7.

Example 2

Input: m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]

Output: 4

The unguarded cells are shown in green in the above diagram. There are a total of 4 unguarded cells, so we return 4.

Constraints

1 <= m, n <= 105
2 <= m * n <= 105
1 <= guards.length, walls.length <= 5 * 104
2 <= guards.length + walls.length <= m * n
guards[i].length == walls[j].length == 2
0 <= rowi, rowj < m
0 <= coli, colj < n
All the positions in guards and walls are unique.

Solution Approach

Build a state grid for guards, walls, and watched cells

Create a 2D array for the grid and mark each guard cell and wall cell first. This is the core Array plus Matrix setup for problem 2257 because every later step depends on fast cell-state checks while scanning sight lines.

Simulate four directional rays from every guard

For each guard, walk up, down, left, and right one cell at a time. Stop when you leave the grid or hit a wall or another guard. Mark only empty cells as watched. The main failure mode here is scanning past blockers, which incorrectly guards cells that should remain hidden.

Count cells that stayed empty and unseen

After all guards finish their scans, iterate through the matrix and count cells that are still plain empty cells. Do not count walls, guard positions, or watched cells. This final pass keeps the logic simple and matches the required return value exactly.

Complexity Analysis

Metric	Value
Time	O(m \times n)
Space	O(m \times n)

The standard matrix simulation runs in O(m × n) time and uses O(m × n) space for the grid representation. Even though each guard scans in four directions, the problem constraints allow this direct marking approach, and the explicit grid makes blocker handling much less error-prone than trying to infer visibility from separate row and column structures.

What Interviewers Usually Probe

The interviewer mentions creating a 2D grid and marking visible tiles, which points directly to matrix simulation.
They emphasize that guards stop at walls or other guards, which means blocker checks matter more than path length.
They ask for unoccupied and unguarded cells specifically, which suggests separating cell states before counting.

Common Pitfalls or Variants

Common pitfalls

Marking through another guard or wall instead of stopping the scan immediately.
Counting watched cells incorrectly because guard and wall cells were never given distinct states.
Trying to use generic BFS or DFS even though this problem is about straight-line row and column visibility.

Follow-up variants

Return the list of unguarded coordinates instead of just the count.
Allow diagonal vision, which changes the simulation from four directions to eight.
Process online updates where guards or walls are added after the initial grid is built.

FAQ

What is the best pattern for Count Unguarded Cells in the Grid?

The best pattern is Array plus Matrix simulation. Build the grid, mark guards and walls, then simulate each guard's straight-line visibility until a blocker appears.

Why not use BFS or DFS here?

BFS and DFS are not a natural fit because guards do not spread through all reachable cells. They only see in four straight directions, and each line stops at the first blocker.

What blocks a guard in problem 2257?

A wall blocks vision, and another guard also blocks vision. Once either appears in a direction, cells beyond it must not be marked as guarded.

How do I avoid double counting guarded cells?

Use explicit cell states in the matrix, such as empty, wall, guard, and watched. Then the final count only includes cells that remained empty for the whole simulation.

Can this be solved without storing the whole matrix?

You can design more specialized row and column tracking, but for this problem the full matrix is usually the clearest and safest solution. The grid state makes obstacle handling and final counting much easier to get right.

terminal

Solution

Solution 1: Simulation

We create a two-dimensional array $g$ of size $m \times n$, where $g[i][j]$ represents the cell in row $i$ and column $j$. Initially, the value of $g[i][j]$ is $0$, indicating that the cell is not guarded.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def countUnguarded(
        self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]
    ) -> int:
        g = [[0] * n for _ in range(m)]
        for i, j in guards:
            g[i][j] = 2
        for i, j in walls:
            g[i][j] = 2
        dirs = (-1, 0, 1, 0, -1)
        for i, j in guards:
            for a, b in pairwise(dirs):
                x, y = i, j
                while 0 <= x + a < m and 0 <= y + b < n and g[x + a][y + b] < 2:
                    x, y = x + a, y + b
                    g[x][y] = 1
        return sum(v == 0 for row in g for v in row)

Continue Practicing

#2326 spiral matrix iv #2352 equal row and column pairs #2482 difference between ones and zeros in row and column