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.
This approach simulates how each guard covers the surrounding cells using a Breadth-First Search (BFS). Each guard's visibility direction (up, down, left, right) is explored until a wall or another guard is encountered. This is efficiently managed by marking cells on the grid as guarded when checked.
This Python solution initializes a grid where non-zero values denote walls and guards (-1 for walls, -2 for guards). Each guard initiates a BFS to mark accessible cells as 'guarded' (1). After setting up all guards, we count unguarded cells (still marked as 0).
Python
JavaScript
C++
Java
Time Complexity: O(m * n + g + w), where g is the number of guards and w is the number of walls due to establishing the grid. Each BFS operation per guard affects linear paths on the grid. Space Complexity: O(m * n), due to the grid storage.
This method involves scanning the grid twice. The first pass evaluates each row and column to determine guard ocular coverage, interrupted by other guards or walls. The second pass counts cells still unmarked (unkempt).
This Python code initially fills the grid with walls and guards. Each line is scanned for unbroken visibility, updating guard effects directly, followed by a transpose to achieve column effects, before computing free cells.
Python
JavaScript
Time Complexity: O(m * n), primarily from traversals of separated lines. Space Complexity: O(m * n), the redundancy of either process like transpose or count verification.
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.
Then, we traverse all guards and walls, and set the value of g[i][j] to 2, indicating that these positions cannot be accessed.
Next, we traverse all guard positions, simulate in four directions from that position until we encounter a wall or guard, or go out of bounds. During the simulation, we set the value of the encountered cell to 1, indicating that the cell is guarded.
Finally, we traverse g and count the number of cells with a value of 0, which is the answer.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns in the grid, respectively.
Python
Java
C++
Go
TypeScript
JavaScript
Rust
C#
| Approach | Complexity |
|---|---|
| Approach 1: Breadth-First Search (BFS) for Guarding | Time Complexity: O(m * n + g + w), where g is the number of guards and w is the number of walls due to establishing the grid. Each BFS operation per guard affects linear paths on the grid. Space Complexity: O(m * n), due to the grid storage. |
| Approach 2: Two-Pass Grid Sweep | Time Complexity: O(m * n), primarily from traversals of separated lines. Space Complexity: O(m * n), the redundancy of either process like transpose or count verification. |
| Simulation | — |
| 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 |
Count Unguarded Cells in the Grid | Simple Explanation | Leetcode 2257 | codestorywithMIK • codestorywithMIK • 11,376 views views
Watch 9 more video solutions →Practice Count Unguarded Cells in the Grid with our built-in code editor and test cases.
Practice on FleetCode