Scale Engineer

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
ArrayMatrix
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] = [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 <= 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

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.

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

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.

Solutions

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

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 →

Next problem