NeetCode #156LC-2257MediumArrays & Hashing
← Back to All Problems#156 · #2257 · Count Unguarded Cells in the Grid(统计网格图中没有被保卫的格子数)
📌 Problem Statement & Constraints
You are given two integers
m and n and a 2D grid where 0 is an empty cell, 1 is a guard and 2 is a wall. A guard sees every cell in the four cardinal directions until blocked by a wall or another guard. Return the number of unguarded cells. Constraints: 1 <= m, n <= 10^5, 2 <= m * n <= 10^5.💡 Core Algorithmic Approaches
- Use a separate status grid so the original grid stays intact:
0unguarded,1guarded,2guard,3wall. - Copy the guards and walls into the status grid.
- For each guard, walk in all four directions, marking every empty cell as guarded and stopping at a wall.
- Count the remaining zeros.
- Note that guards themselves also block other guards' vision, which the walk handles naturally because a guard cell is not marked as guarded but does stop the loop? -- it does not stop the loop, so the guard's own cell is simply skipped when counting (it is
2, not0).
💻 Benchmark Python3 Implementation
class Solution:
def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
# 0 = unguarded, 1 = guarded, 2 = guard, 3 = wall
cell = [[0] * n for _ in range(m)]
for r, c in guards:
cell[r][c] = 2
for r, c in walls:
cell[r][c] = 3
dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
for r, c in guards:
for dr, dc in dirs:
x, y = r + dr, c + dc
while 0 <= x < m and 0 <= y < n and cell[x][y] != 3:
if cell[x][y] == 0:
cell[x][y] = 1 # mark as guarded
x += dr
y += dc
return sum(1 for r in range(m) for c in range(n) if cell[r][c] == 0)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n) in the worst case: each guard walks until a wall, and each cell is visited a constant number of times per direction.
💾 Space Complexity
O(m * n) for the status grid. Mutating the input grid instead would save this but destroys the guard positions needed for the second pass.
⚠️ Interview Pitfalls & Follow-ups
- Mutating the input grid: the guard positions are needed for the second pass, so a separate status grid is required (or the guards must be collected first).
- Stopping the walk at another guard: the loop condition is
cell[x][y] != 3, so only walls block the sweep. Guard cells carry status 2, which means they are never overwritten as guarded and are never counted as unguarded either -- both behaviours are correct. - Counting guards or walls as unguarded: only status 0 counts.
- Using a 2D list of size
m x nwhenm * n <= 10^5but one dimension can be 10^5: the product is bounded, so the allocation is safe.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.