Count Unguarded Cells in the Grid

Med

#2055Time: 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.1 company

Data structures

Array Matrix

Companies

Poshmark

Prompt

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] = [row_i, col_i] and walls[j] = [row_j, col_j] represent the positions of the i^th guard and j^th 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 <= 10⁵
2 <= m * n <= 10⁵
1 <= guards.length, walls.length <= 5 * 10⁴
2 <= guards.length + walls.length <= m * n
guards[i].length == walls[j].length == 2
0 <= row_i, row_j < m
0 <= col_i, col_j < n
All the positions in guards and walls are unique.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {3        // 0: empty, 1: guard, 2: wall, 3: guarded4        int[][] grid = new int[m][n];5        6        for (int[] wall : walls) {7            grid[wall[0]][wall[1]] = 2;8        }9        for (int[] guard : guards) {10            grid[guard[0]][guard[1]] = 1;11        }12        13        for (int[] guard : guards) {14            int r = guard[0];15            int c = guard[1];16            17            // Look right18            for (int j = c + 1; j < n; j++) {19                if (grid[r][j] == 1 || grid[r][j] == 2) break;20                if (grid[r][j] == 0) grid[r][j] = 3;21            }22            23            // Look left24            for (int j = c - 1; j >= 0; j--) {25                if (grid[r][j] == 1 || grid[r][j] == 2) break;26                if (grid[r][j] == 0) grid[r][j] = 3;27            }28            29            // Look down30            for (int i = r + 1; i < m; i++) {31                if (grid[i][c] == 1 || grid[i][c] == 2) break;32                if (grid[i][c] == 0) grid[i][c] = 3;33            }34            35            // Look up36            for (int i = r - 1; i >= 0; i--) {37                if (grid[i][c] == 1 || grid[i][c] == 2) break;38                if (grid[i][c] == 0) grid[i][c] = 3;39            }40        }41        42        int unguardedCount = 0;43        for (int i = 0; i < m; i++) {44            for (int j = 0; j < n; j++) {45                if (grid[i][j] == 0) {46                    unguardedCount++;47                }48            }49        }50        51        return unguardedCount;52    }53}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

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).
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.
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.
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.

1class Solution {2    public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {3        // 0: empty, 1: guard, 2: wall, 3: guarded4        int[][] grid = new int[m][n];5        6        for (int[] wall : walls) {7            grid[wall[0]][wall[1]] = 2;8        }9        for (int[] guard : guards) {10            grid[guard[0]][guard[1]] = 1;11        }12        13        // Scan rows14        for (int i = 0; i < m; i++) {15            boolean guarded = false;16            // Left to right17            for (int j = 0; j < n; j++) {18                if (grid[i][j] == 1) guarded = true;19                else if (grid[i][j] == 2) guarded = false;20                else if (grid[i][j] == 0 && guarded) grid[i][j] = 3;21            }22            guarded = false;23            // Right to left24            for (int j = n - 1; j >= 0; j--) {25                if (grid[i][j] == 1) guarded = true;26                else if (grid[i][j] == 2) guarded = false;27                else if (grid[i][j] == 0 && guarded) grid[i][j] = 3;28            }29        }30        31        // Scan columns32        for (int j = 0; j < n; j++) {33            boolean guarded = false;34            // Top to bottom35            for (int i = 0; i < m; i++) {36                if (grid[i][j] == 1) guarded = true;37                else if (grid[i][j] == 2) guarded = false;38                else if (grid[i][j] == 0 && guarded) grid[i][j] = 3;39            }40            guarded = false;41            // Bottom to top42            for (int i = m - 1; i >= 0; i--) {43                if (grid[i][j] == 1) guarded = true;44                else if (grid[i][j] == 2) guarded = false;45                else if (grid[i][j] == 0 && guarded) grid[i][j] = 3;46            }47        }48        49        int unguardedCount = 0;50        for (int i = 0; i < m; i++) {51            for (int j = 0; j < n; j++) {52                if (grid[i][j] == 0) {53                    unguardedCount++;54                }55            }56        }57        58        return unguardedCount;59    }60}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int countUnguarded(int m, int n, int[][] guards, int[][] walls) {4    int[][] g = new int[m][n];5    for (var e : guards) {6      g[e[0]][e[1]] = 2;7    }8    for (var e : walls) {9      g[e[0]][e[1]] = 2;10    }11    int[] dirs = {-1, 0, 1, 0, -1};12    for (var e : guards) {13      for (int k = 0; k < 4; ++k) {14        int x = e[0], y = e[1];15        int a = dirs[k], b = dirs[k + 1];16        while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n &&17               g[x + a][y + b] < 2) {18          x += a;19          y += b;20          g[x][y] = 1;21        }22      }23    }24    int ans = 0;25    for (var row : g) {26      for (int v : row) {27        if (v == 0) {28          ++ans;29        }30      }31    }32    return ans;33  }34}

1function 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 ; }

1class Solution {2public:3  int countUnguarded(int m, int n, vector<vector<int>> &guards,4                     vector<vector<int>> &walls) {5    int g[m][n];6    memset(g, 0, sizeof(g));7    for (auto &e : guards) {8      g[e[0]][e[1]] = 2;9    }10    for (auto &e : walls) {11      g[e[0]][e[1]] = 2;12    }13    int dirs[5] = {-1, 0, 1, 0, -1};14    for (auto &e : guards) {15      for (int k = 0; k < 4; ++k) {16        int x = e[0], y = e[1];17        int a = dirs[k], b = dirs[k + 1];18        while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n &&19               g[x + a][y + b] < 2) {20          x += a;21          y += b;22          g[x][y] = 1;23        }24      }25    }26    int ans = 0;27    for (auto &row : g) {28      ans += count(row, row + n, 0);29    }30    return ans;31  }32};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem