LeetCode 2257 - Count Unguarded Cells in the Grid

LeetCode Problem 2257

Difficulty: 🟡 Medium
Topics: Array, Matrix, Simulation

Solution

Problem Understanding

This problem gives us an m x n grid containing three types of cells:

1. Guard cells
2. Wall cells
3. Empty cells

Each guard can observe cells in the four cardinal directions:

• Up
• Down
• Left
• Right

A guard continues seeing cells in a direction until the view is blocked by either:

• A wall
• Another guard

The task is to count how many empty cells are:

• Not occupied by a guard
• Not occupied by a wall
• Not visible to any guard

The grid is 0-indexed, meaning the top-left cell is (0, 0).

For example, if a guard is at (2, 3), then the guard can scan:

• Upward through (1, 3), (0, 3)
• Downward through (3, 3), etc.
• Leftward
• Rightward

The scan stops immediately once a wall or another guard is encountered.

The constraints are extremely important:

• m * n <= 10^5

This tells us the total number of cells is at most 100,000, which is manageable for linear or near-linear algorithms.

However:

• guards.length and walls.length can each be as large as 5 * 10^4

This means we cannot afford extremely expensive per-guard scanning approaches that repeatedly revisit many cells unnecessarily.

A naive implementation could become too slow if every guard scans almost the entire grid independently.

Some important edge cases include:

• Guards adjacent to walls
• Guards blocking each other
• Single row or single column grids
• Grids where almost every cell is occupied
• Cells visible from multiple guards
• Empty regions completely enclosed by walls

The problem guarantees that all guard and wall positions are unique, so we never need to handle overlaps between guards and walls.

Approaches

Brute Force Approach

A straightforward approach is to process every empty cell individually.

For each empty cell:

1. Look upward until:

• A wall is found
• A guard is found
• The boundary is reached

2. Repeat for:

• Downward
• Leftward
• Rightward

If any direction encounters a guard before a blocking object, then the cell is guarded.

Otherwise, the cell is unguarded.

This approach is correct because it directly follows the definition of visibility in the problem statement.

However, the performance is poor.

Suppose the grid contains m * n cells, and for every empty cell we potentially scan an entire row and column. In the worst case, each lookup costs O(m + n).

That leads to:

• O(m * n * (m + n))

With up to 10^5 cells, this can become far too slow.

Optimal Approach

The key observation is that visibility propagates in straight lines.

Instead of asking:

"Is this cell visible from a guard?"

for every empty cell independently, we reverse the process:

"Starting from each guard, mark every visible cell."

This avoids repeated directional scans for the same cells.

We build a grid representation where:

• 0 = empty
• 1 = guarded
• 2 = guard
• 3 = wall

Then, for every guard, we scan outward in four directions until we hit:

• A wall
• Another guard

Every traversed empty cell becomes guarded.

Finally, we count cells that remain empty.

Because each directional traversal only touches cells until blocked, and total grid size is at most 10^5, this approach is efficient enough.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n * (m + n))	O(m * n)	Rechecks visibility for every empty cell
Optimal	O(m * n)	O(m * n)	Marks guarded cells directly from guards

Algorithm Walkthrough

1. Create a grid of size m x n initialized with 0.

We use numeric states to efficiently track the type of each cell.

• 0 = empty
• 1 = guarded
• 2 = guard
• 3 = wall

2. Place all guards into the grid.

For every position in guards, set:

grid[row][col] = 2

3. Place all walls into the grid.

For every position in walls, set:

grid[row][col] = 3

4. Define the four movement directions.

These are:

• Up (-1, 0)
• Down (1, 0)
• Left (0, -1)
• Right (0, 1)

5. For every guard, scan in all four directions.

Starting from the guard's adjacent cell:

• Continue moving while inside the grid

• Stop immediately if:

• Another guard is encountered

• A wall is encountered

• Otherwise mark the cell as guarded

6. Mark guarded cells.

If a traversed cell is empty (0), change it to guarded (1).

We still continue scanning beyond already-guarded cells because visibility extends through them. 7. Count remaining empty cells.

After all guards finish scanning, every unguarded empty cell still contains 0.

Count these cells and return the result.

Why it works

The algorithm works because guard visibility is directional and uninterrupted until a blocking object appears.

By scanning outward from every guard exactly according to the problem rules, every visible cell is marked guarded. Since walls and guards stop scanning immediately, no invalid cells are marked.

After all guards are processed:

• Every guarded empty cell has value 1
• Every truly unguarded empty cell remains 0

Therefore, counting remaining 0 cells gives the correct answer.

Python Solution

from typing import List

class Solution:
    def countUnguarded(
        self,
        m: int,
        n: int,
        guards: List[List[int]],
        walls: List[List[int]]
    ) -> int:

        EMPTY = 0
        GUARDED = 1
        GUARD = 2
        WALL = 3

        grid = [[EMPTY] * n for _ in range(m)]

        # Place guards
        for row, col in guards:
            grid[row][col] = GUARD

        # Place walls
        for row, col in walls:
            grid[row][col] = WALL

        directions = [
            (-1, 0),  # up
            (1, 0),   # down
            (0, -1),  # left
            (0, 1)    # right
        ]

        # Spread visibility from each guard
        for row, col in guards:

            for dr, dc in directions:

                r = row + dr
                c = col + dc

                while 0 <= r < m and 0 <= c < n:

                    # Stop if blocked
                    if grid[r][c] == GUARD or grid[r][c] == WALL:
                        break

                    # Mark as guarded
                    if grid[r][c] == EMPTY:
                        grid[r][c] = GUARDED

                    r += dr
                    c += dc

        # Count unguarded empty cells
        unguarded = 0

        for row in range(m):
            for col in range(n):
                if grid[row][col] == EMPTY:
                    unguarded += 1

        return unguarded

The implementation begins by constructing a matrix representation of the grid. Numeric constants are used instead of strings because integer comparisons are faster and clearer for state management.

The guards and walls are inserted first so the scanning phase can immediately recognize blocking cells.

The directions array centralizes movement logic. This avoids duplicated code for up, down, left, and right traversal.

For every guard, the algorithm performs directional scans. Each scan continues until either:

• The grid boundary is reached
• A wall is encountered
• Another guard is encountered

Empty cells encountered during traversal are marked as guarded.

Finally, the grid is traversed one last time to count cells that remain empty.

Go Solution

func countUnguarded(m int, n int, guards [][]int, walls [][]int) int {
	const (
		EMPTY   = 0
		GUARDED = 1
		GUARD   = 2
		WALL    = 3
	)

	grid := make([][]int, m)

	for i := 0; i < m; i++ {
		grid[i] = make([]int, n)
	}

	// Place guards
	for _, g := range guards {
		row, col := g[0], g[1]
		grid[row][col] = GUARD
	}

	// Place walls
	for _, w := range walls {
		row, col := w[0], w[1]
		grid[row][col] = WALL
	}

	directions := [][]int{
		{-1, 0}, // up
		{1, 0},  // down
		{0, -1}, // left
		{0, 1},  // right
	}

	// Spread visibility
	for _, g := range guards {
		row, col := g[0], g[1]

		for _, d := range directions {
			dr, dc := d[0], d[1]

			r := row + dr
			c := col + dc

			for r >= 0 && r < m && c >= 0 && c < n {

				if grid[r][c] == GUARD || grid[r][c] == WALL {
					break
				}

				if grid[r][c] == EMPTY {
					grid[r][c] = GUARDED
				}

				r += dr
				c += dc
			}
		}
	}

	// Count unguarded cells
	unguarded := 0

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == EMPTY {
				unguarded++
			}
		}
	}

	return unguarded
}

The Go implementation follows the exact same algorithmic structure as the Python version.

A 2D slice is used for the grid representation. Constants improve readability and eliminate magic numbers throughout the code.

Go does not require special handling for integer overflow here because all counts remain well within the standard int range.

Unlike Python, Go uses explicit index-based loops and slice initialization.

Worked Examples

Example 1

m = 4
n = 6

guards = [[0,0],[1,1],[2,3]]
walls = [[0,1],[2,2],[1,4]]

Initial Grid

Cell Type	Value
Empty	0
Guard	2
Wall	3

Grid state:

Row\Col	0	1	2	3	4	5
0	G	W	.	.	.	.
1	.	G	.	.	W	.
2	.	.	W	G	.	.
3	.	.	.	.	.	.

Process Guard (0,0)

Directions:

• Right stops immediately at wall (0,1)

• Down marks:

• (1,0)

• (2,0)

• (3,0)

Grid:

Row\Col	0	1	2	3	4	5
0	G	W	.	.	.	.
1	X	G	.	.	W	.
2	X	.	W	G	.	.
3	X	.	.	.	.	.

X means guarded.

Process Guard (1,1)

Scans:

• Left hits guarded (1,0)

• Right marks:

• (1,2)

• (1,3)

• Down marks:

• (2,1)

• (3,1)

• Up stops at wall (0,1)

Process Guard (2,3)

Scans:

• Left stops at wall (2,2)

• Right marks:

• (2,4)

• (2,5)

• Up marks:

• (1,3) already guarded

• (0,3)

• Down marks:

• (3,3)

Final Unguarded Cells

Remaining empty cells:

(0,2)
(0,4)
(0,5)
(1,5)
(3,2)
(3,4)
(3,5)

Answer:

7

Example 2

m = 3
n = 3

guards = [[1,1]]
walls = [[0,1],[1,0],[2,1],[1,2]]

Initial Grid

Row\Col	0	1	2
0	.	W	.
1	W	G	W
2	.	W	.

The guard is completely surrounded by walls.

No directional scan can proceed even one step.

Thus, the four corner cells remain unguarded.

Answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n)	Each cell is processed a limited number of times
Space	O(m * n)	The grid representation stores all cells

The total grid size is at most 100000, so storing the grid is efficient.

Although guards perform directional scans, every scan progresses linearly through rows or columns. Because the total number of cells is bounded, the overall runtime remains effectively linear relative to the grid size.

Test Cases

from typing import List

class Solution:
    def countUnguarded(
        self,
        m: int,
        n: int,
        guards: List[List[int]],
        walls: List[List[int]]
    ) -> int:

        EMPTY = 0
        GUARDED = 1
        GUARD = 2
        WALL = 3

        grid = [[EMPTY] * n for _ in range(m)]

        for r, c in guards:
            grid[r][c] = GUARD

        for r, c in walls:
            grid[r][c] = WALL

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        for r, c in guards:

            for dr, dc in directions:

                nr = r + dr
                nc = c + dc

                while 0 <= nr < m and 0 <= nc < n:

                    if grid[nr][nc] == GUARD or grid[nr][nc] == WALL:
                        break

                    if grid[nr][nc] == EMPTY:
                        grid[nr][nc] = GUARDED

                    nr += dr
                    nc += dc

        return sum(
            grid[r][c] == EMPTY
            for r in range(m)
            for c in range(n)
        )

sol = Solution()

assert sol.countUnguarded(
    4,
    6,
    [[0, 0], [1, 1], [2, 3]],
    [[0, 1], [2, 2], [1, 4]]
) == 7  # official example 1

assert sol.countUnguarded(
    3,
    3,
    [[1, 1]],
    [[0, 1], [1, 0], [2, 1], [1, 2]]
) == 4  # official example 2

assert sol.countUnguarded(
    1,
    2,
    [[0, 0]],
    []
) == 0  # single row, guard sees remaining cell

assert sol.countUnguarded(
    2,
    2,
    [[0, 0]],
    [[0, 1], [1, 0]]
) == 1  # walls block all visibility

assert sol.countUnguarded(
    3,
    3,
    [[0, 0], [0, 2]],
    []
) == 3  # guards block each other horizontally

assert sol.countUnguarded(
    5,
    5,
    [[2, 2]],
    []
) == 16  # central guard covers row and column only

assert sol.countUnguarded(
    1,
    5,
    [[0, 0], [0, 4]],
    [[0, 2]]
) == 0  # wall splits visibility correctly

assert sol.countUnguarded(
    3,
    4,
    [[0, 1]],
    []
) == 6  # guard visibility across row and column

Test	Why
Official example 1	Validates general multi-guard behavior
Official example 2	Validates complete wall blocking
Single row grid	Tests horizontal traversal
Walls near guard	Tests immediate blocking
Multiple guards	Tests guards stopping visibility
Center guard	Tests directional coverage
Wall between guards	Tests segmented visibility
Sparse grid	Tests ordinary propagation

Edge Cases

Guards Immediately Adjacent to Walls

A common bug occurs when implementations incorrectly allow guards to see through walls.

For example:

G W .

The guard should not see the final cell.

The implementation handles this correctly because scanning stops immediately once a wall cell is encountered.

Guards Blocking Other Guards

Another subtle case occurs when guards appear in the same row or column.

For example:

G . . G

The left guard should not see beyond the right guard.

The algorithm explicitly stops scanning when another guard is encountered, preventing incorrect propagation.

Single Row or Single Column Grids

Directional traversal logic often breaks in degenerate grids such as:

1 x n

or

m x 1

The implementation handles this safely because every movement checks boundaries before accessing the grid.

Multiple Guards Seeing the Same Cell

A cell may be visible from several guards simultaneously.

A buggy implementation might repeatedly process or overwrite cells incorrectly.

This implementation simply marks cells as GUARDED once. Additional scans passing through already-guarded cells continue normally without affecting correctness.