# Count Unguarded Cells in the Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-unguarded-cells-in-the-grid)
Canonical: https://scaleengineer.com/dsa/problems/count-unguarded-cells-in-the-grid
**Data structures:** Array, Matrix
**Companies:** [Poshmark](https://scaleengineer.com/companies/poshmark)
---
## Problem
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:**

![](https://assets.glich.co/dsa/count-unguarded-cells-in-the-grid/image0.png) 

**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:**

![](https://assets.glich.co/dsa/count-unguarded-cells-in-the-grid/image1.png) 

**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 <= 105`
* `2 <= m * n <= 105`
* `1 <= guards.length, walls.length <= 5 * 104`
* `2 <= guards.length + walls.length <= m * n`
* `guards[i].length == walls[j].length == 2`
* `0 <= rowi, rowj < m`
* `0 <= coli, colj < n`
* All the positions in `guards` and `walls` are **unique**.

# Approaches
## Naive Simulation from Each Guard
This approach directly simulates the process described in the problem. We use a 2D grid to represent the area, with different integer values denoting whether a cell is empty, contains a wall, a guard, or is guarded. For each guard, we trace its line of sight in the four cardinal directions, marking empty cells as guarded until an obstruction (a wall, another guard) or the edge of the grid is reached.
**Time:** O(G * (m + n) + m * n), where `G` is the number of guards. The `m*n` term is for grid initialization and final counting. The main cost is from simulating each guard's sight across rows and columns. This can be slow if `G`, `m`, or `n` are large. · **Space:** O(m * n) to store the state of each cell in the grid.
**Pros:** The logic is straightforward and easy to implement as it directly follows the problem's description.; It's a good starting point for understanding the problem dynamics.
**Cons:** Can be inefficient and may result in a 'Time Limit Exceeded' error for certain test cases, especially those with a large grid dimension (`m` or `n`) and many guards.; Involves redundant computations as the same cell might be checked multiple times by different guards.
### Explanation
We begin by setting up an `m x n` integer matrix, let's call it `grid`, initialized to all zeros. A `0` signifies an empty, currently unguarded cell.

Next, we populate this grid with the given walls and guards. We can use a simple convention: `1` for a guard and `2` for a wall. These values are placed at their respective coordinates in the `grid`.

The core of this method is to iterate through each guard. For each guard at `(r, c)`, we perform four simulations, one for each direction:
- **Eastward:** We loop from column `c + 1` to `n - 1` in the same row `r`. 
- **Westward:** We loop from `c - 1` down to `0` in row `r`.
- **Southward:** We loop from row `r + 1` to `m - 1` in the same column `c`.
- **Northward:** We loop from `r - 1` down to `0` in column `c`.

During each of these traversals, we check the state of the cell. If we encounter a cell that is already a guard (`1`) or a wall (`2`), the line of sight is blocked, so we stop the traversal in that direction (`break`). If we find an empty cell (`0`), we update its state to `3` to mark it as guarded.

After completing this process for all guards, the `grid` accurately reflects the state of every cell. The final step is to count the number of cells that remain `0`. This count gives us the total number of unoccupied and unguarded cells.

```java
class Solution {
    public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
        // 0: empty, 1: guard, 2: wall, 3: guarded
        int[][] grid = new int[m][n];
        
        for (int[] wall : walls) {
            grid[wall[0]][wall[1]] = 2;
        }
        for (int[] guard : guards) {
            grid[guard[0]][guard[1]] = 1;
        }
        
        for (int[] guard : guards) {
            int r = guard[0];
            int c = guard[1];
            
            // Look right
            for (int j = c + 1; j < n; j++) {
                if (grid[r][j] == 1 || grid[r][j] == 2) break;
                if (grid[r][j] == 0) grid[r][j] = 3;
            }
            
            // Look left
            for (int j = c - 1; j >= 0; j--) {
                if (grid[r][j] == 1 || grid[r][j] == 2) break;
                if (grid[r][j] == 0) grid[r][j] = 3;
            }
            
            // Look down
            for (int i = r + 1; i < m; i++) {
                if (grid[i][c] == 1 || grid[i][c] == 2) break;
                if (grid[i][c] == 0) grid[i][c] = 3;
            }
            
            // Look up
            for (int i = r - 1; i >= 0; i--) {
                if (grid[i][c] == 1 || grid[i][c] == 2) break;
                if (grid[i][c] == 0) grid[i][c] = 3;
            }
        }
        
        int unguardedCount = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    unguardedCount++;
                }
            }
        }
        
        return unguardedCount;
    }
}
```
### Algorithm
- Create an `m x n` grid and initialize all cells to `0` (representing empty).
- Mark the positions of walls with `2` and guards with `1`.
- Iterate through each guard's position `(gr, gc)`.
- For each guard, simulate its line of sight in all four cardinal directions (north, east, south, west).
- Trace a path from the guard's position outwards. If a cell is empty (`0`), mark it as guarded (`3`).
- Stop tracing in a direction if a wall (`2`), another guard (`1`), or the grid boundary is encountered.
- After simulating for all guards, iterate through the entire grid and count the number of cells that are still `0`.
- This count is the number of unguarded, unoccupied cells.

## Optimized Grid Scan
This optimized approach avoids the redundant work of the naive simulation. Instead of simulating from each guard individually, we perform four 'sweep-line' passes over the entire grid: left-to-right, right-to-left, top-to-bottom, and bottom-to-top. During each pass, we maintain a state to indicate whether we are in a 'guarded' zone. This allows us to mark all guarded cells in a single directional pass, ensuring that each cell is visited only a constant number of times.
**Time:** O(m * n). The algorithm involves a few passes over the grid (initialization, four scan directions, final count), each taking O(m * n) time. This is the most efficient approach possible given the constraints. · **Space:** O(m * n) for storing the grid. This is optimal in terms of space if a grid representation is used.
**Pros:** Highly efficient, with a time complexity linear to the size of the grid.; Avoids redundant computations by processing each cell a constant number of times.; Guaranteed to pass within the given constraints.
**Cons:** Requires O(m * n) space, which is acceptable for this problem's constraints but might be a limitation for problems with much larger grids.
### Explanation
This method enhances efficiency by changing the perspective from a guard-centric simulation to a grid-wide scan. We still use an `m x n` grid with the same state convention: `0` (empty), `1` (guard), `2` (wall), and `3` (guarded).

After initializing the grid with guards and walls, the core logic involves four distinct passes:

1.  **Row-wise Scan (Left to Right):** We iterate through each row `i` from `0` to `m-1`. For each row, we iterate through columns `j` from `0` to `n-1`. A boolean flag, `guarded`, tracks the line of sight. If we see a guard (`grid[i][j] == 1`), we set `guarded = true`. If we see a wall (`grid[i][j] == 2`), the sight is blocked, so we set `guarded = false`. If the cell is empty (`grid[i][j] == 0`) and `guarded` is true, we mark the cell as guarded (`3`).

2.  **Row-wise Scan (Right to Left):** We repeat the same logic, but this time we iterate from `j = n-1` down to `0` for each row. This captures sight lines extending to the left of guards.

3.  **Column-wise Scan (Top to Bottom):** We now scan column by column. For each column `j`, we iterate through rows `i` from `0` to `m-1`, applying the same state logic to handle downward sight.

4.  **Column-wise Scan (Bottom to Top):** Finally, we scan each column from `i = m-1` down to `0` to handle upward sight.

A guard also acts as an obstacle. The `if-else if` structure of the logic correctly handles this: when a guard is encountered, the `guarded` flag is set to `true`, effectively starting a new line of sight and blocking any previous one from that direction.

After these four passes, all cells visible to any guard are marked as `3`. The final answer is the count of cells that remain `0`.

```java
class Solution {
    public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
        // 0: empty, 1: guard, 2: wall, 3: guarded
        int[][] grid = new int[m][n];
        
        for (int[] wall : walls) {
            grid[wall[0]][wall[1]] = 2;
        }
        for (int[] guard : guards) {
            grid[guard[0]][guard[1]] = 1;
        }
        
        // Scan rows
        for (int i = 0; i < m; i++) {
            boolean guarded = false;
            // Left to right
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) guarded = true;
                else if (grid[i][j] == 2) guarded = false;
                else if (grid[i][j] == 0 && guarded) grid[i][j] = 3;
            }
            guarded = false;
            // Right to left
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j] == 1) guarded = true;
                else if (grid[i][j] == 2) guarded = false;
                else if (grid[i][j] == 0 && guarded) grid[i][j] = 3;
            }
        }
        
        // Scan columns
        for (int j = 0; j < n; j++) {
            boolean guarded = false;
            // Top to bottom
            for (int i = 0; i < m; i++) {
                if (grid[i][j] == 1) guarded = true;
                else if (grid[i][j] == 2) guarded = false;
                else if (grid[i][j] == 0 && guarded) grid[i][j] = 3;
            }
            guarded = false;
            // Bottom to top
            for (int i = m - 1; i >= 0; i--) {
                if (grid[i][j] == 1) guarded = true;
                else if (grid[i][j] == 2) guarded = false;
                else if (grid[i][j] == 0 && guarded) grid[i][j] = 3;
            }
        }
        
        int unguardedCount = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    unguardedCount++;
                }
            }
        }
        
        return unguardedCount;
    }
}
```
### Algorithm
- Create an `m x n` grid and initialize all cells to `0` (empty).
- Mark the positions of walls with `2` and guards with `1`.
- **Row Scans:**
  - For each row, scan from left to right. Use a flag to track if the current segment is guarded. A guard starts a guarded segment, and a wall ends it. Mark empty cells in a guarded segment as `3`.
  - For each row, perform another scan from right to left with a fresh flag to handle sight in the opposite direction.
- **Column Scans:**
  - Similarly, for each column, scan from top to bottom, marking guarded cells.
  - Then, for each column, scan from bottom to top.
- After all four scan passes, count the number of cells that are still `0`.

# Solutions
### Java

```java
class Solution {
public
  int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
    int[][] g = new int[m][n];
    for (var e : guards) {
      g[e[0]][e[1]] = 2;
    }
    for (var e : walls) {
      g[e[0]][e[1]] = 2;
    }
    int[] dirs = {-1, 0, 1, 0, -1};
    for (var e : guards) {
      for (int k = 0; k < 4; ++k) {
        int x = e[0], y = e[1];
        int a = dirs[k], b = dirs[k + 1];
        while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n &&
               g[x + a][y + b] < 2) {
          x += a;
          y += b;
          g[x][y] = 1;
        }
      }
    }
    int ans = 0;
    for (var row : g) {
      for (int v : row) {
        if (v == 0) {
          ++ans;
        }
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
function countUnguarded ( m , n , guards , walls ) { const g = Array . from ({ length : m }, () => Array . from ({ length : n }, () => 0 )); for ( const [ i , j ] of guards ) { g [ i ][ j ] = 2 ; } for ( const [ i , j ] of walls ) { g [ i ][ j ] = 2 ; } const dirs = [ - 1 , 0 , 1 , 0 , - 1 ]; for ( const [ i , j ] of guards ) { for ( let k = 0 ; k < 4 ; ++ k ) { let [ x , y ] = [ i , j ]; let [ a , b ] = [ dirs [ k ], dirs [ k + 1 ]]; while ( x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && g [ x + a ][ y + b ] < 2 ) { x += a ; y += b ; g [ x ][ y ] = 1 ; } } } let ans = 0 ; for ( const row of g ) { for ( const v of row ) { ans += v === 0 ? 1 : 0 ; } } return ans ; }
```

### CPP

```cpp
class Solution {
public:
  int countUnguarded(int m, int n, vector<vector<int>> &guards,
                     vector<vector<int>> &walls) {
    int g[m][n];
    memset(g, 0, sizeof(g));
    for (auto &e : guards) {
      g[e[0]][e[1]] = 2;
    }
    for (auto &e : walls) {
      g[e[0]][e[1]] = 2;
    }
    int dirs[5] = {-1, 0, 1, 0, -1};
    for (auto &e : guards) {
      for (int k = 0; k < 4; ++k) {
        int x = e[0], y = e[1];
        int a = dirs[k], b = dirs[k + 1];
        while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n &&
               g[x + a][y + b] < 2) {
          x += a;
          y += b;
          g[x][y] = 1;
        }
      }
    }
    int ans = 0;
    for (auto &row : g) {
      ans += count(row, row + n, 0);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int: g = [[0] * n for _ in range(m)] for i, j in guards: g[i][j] = 2 for i, j in walls: g[i][j] = 2 dirs = (- 1, 0, 1, 0, - 1) for i, j in guards: for a, b in pairwise(dirs): x, y = i, j while 0 <= x + a < m and 0 <= y + b < n and g[x + a][y + b] < 2: x, y = x + a, y + b g[x][y] = 1 return sum(v == 0 for row in g for v in row)

```