⚡Flashcard Drill➔
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

  1. Use a separate status grid so the original grid stays intact: 0 unguarded, 1 guarded, 2 guard, 3 wall.
  2. Copy the guards and walls into the status grid.
  3. For each guard, walk in all four directions, marking every empty cell as guarded and stopping at a wall.
  4. Count the remaining zeros.
  5. 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, not 0).

💻 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 n when m * n <= 10^5 but 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems