Watch 10 video solutions for Count Unguarded Cells in the Grid, a medium level problem involving Array, Matrix, Simulation. This walkthrough by codestorywithMIK has 11,376 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two integers m and n representing a 0-indexed m x n grid. You are also given two 2D integer arrays guards and walls where guards[i] = [rowi, coli] and walls[j] = [rowj, colj] represent the positions of the ith guard and jth wall respectively.
A guard can see every cell in the four cardinal directions (north, east, south, or west) starting from their position unless obstructed by a wall or another guard. A cell is guarded if there is at least one guard that can see it.
Return the number of unoccupied cells that are not guarded.
Example 1:
Input: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]] Output: 7 Explanation: 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 Explanation: 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 <= 1052 <= m * n <= 1051 <= guards.length, walls.length <= 5 * 1042 <= guards.length + walls.length <= m * nguards[i].length == walls[j].length == 20 <= rowi, rowj < m0 <= coli, colj < nguards and walls are unique.Problem Overview: You are given an m x n grid with guards and walls. Guards watch cells horizontally and vertically until a wall or another guard blocks the view. The task is to count how many cells remain unguarded after all guards observe their lines of sight.
Approach 1: Breadth-First Search (BFS) for Guarding (O(m*n) time, O(m*n) space)
This approach simulates guard vision using Breadth-First Search. Start by marking guards and walls in the grid. For every guard, expand in four directions using BFS or directional traversal until a wall or another guard blocks the path. Each visited cell is marked as guarded. After processing all guards, iterate through the grid and count cells that remain empty and unguarded. This method closely mirrors the problem statement and is easy to reason about, but it may use extra memory due to queues and visited tracking.
Approach 2: Two-Pass Grid Sweep (O(m*n) time, O(1) extra space)
This optimized method treats the grid like a visibility sweep problem using arrays and matrix traversal. Instead of expanding from every guard, scan the grid in four directions. Perform horizontal passes (left→right and right→left) and vertical passes (top→bottom and bottom→top). Track the most recent guard encountered in the current direction unless a wall resets the state. If a guard is active while sweeping, mark cells as guarded. After the four sweeps, count cells that are still empty and not marked guarded. This approach avoids repeated expansions and works in strict linear time over the grid.
Recommended for interviews: The Two-Pass Grid Sweep is usually preferred. It demonstrates strong reasoning about grid traversal and avoids redundant work. BFS simulation still shows solid understanding of simulation and guard propagation, but interviewers typically expect the sweep-style optimization because it achieves the same O(m*n) time with simpler memory usage.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS Guard Simulation | O(m*n) | O(m*n) | When you want a direct simulation of guard vision or an easier implementation to reason about |
| Two-Pass Grid Sweep | O(m*n) | O(1) | Best general solution for interviews and large grids due to minimal extra memory |