Count Unguarded Cells in the Grid — Problem & Solution
Count Unguarded Cells in the Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Unguarded Cells in the Grid is a medium coding problem on arrays, matrix and simulation, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Matrix, Simulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A building floor is an m x n grid (rows 0..m-1, columns 0..n-1). guards[i] = [r, c] places a guard and walls[j] = [r, c] places a wall; all of these positions are distinct.
A guard watches every cell in the four cardinal directions — up, down, left and right — from its position, until the view is blocked by a wall, another guard, or the edge of the grid. A cell is guarded if at least one guard watches it.
Return the number of cells that are not occupied by a guard or a wall and are not guarded.
Example 1
Input: m = 3, n = 4, guards = [[0,0]], walls = [[0,2]]
Output: 7
Explanation: The guard watches `(0,1)` (the wall stops it there) and `(1,0)`, `(2,0)` below; 12 - 2 occupied - 3 guarded = 7.
Example 2
Input: m = 2, n = 2, guards = [[0,0]], walls = [[1,1]]
Output: 0
Example 3
Input: m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
Output: 4
Explanation: The guard is boxed in by four walls; only the four corners are left, and none is watched.
Constraints
1 <= m, n <= 10^52 <= m * n <= 10^51 <= guards.length, walls.length <= 5 * 10^42 <= guards.length + walls.length <= m * nguards[i].length == walls[j].length == 20 <= row < m, 0 <= col < nall positions in guards and walls are unique
Hints for Count Unguarded Cells in the Grid
Hint 1
Mark guards and walls on an
m x nboard first.Hint 2
From each guard, walk in each direction until you hit a wall, a guard or the edge, marking the cells you pass.
Hint 3
To be strictly linear, sweep each row left-to-right and right-to-left (and each column both ways) with a flag that turns on at a guard and off at a wall.
How to solve Count Unguarded Cells in the Grid
A cell is guarded exactly when, in some direction, the nearest occupied cell is a guard — four directional sweeps with an on/off flag find that in linear time.
Approach
- Build the board: 1 for a guard, 2 for a wall, 0 for empty.
- For each row, sweep left to right keeping a flag: a guard turns it on, a wall turns it off, and an empty cell is marked guarded while the flag is on. Repeat right to left.
- Do the same down and up every column.
- Count the empty cells that were never marked.
Why it works
During a left-to-right sweep the flag is on at a cell exactly when the nearest occupied cell to its left is a guard — which is precisely when a guard watches it from the left (another guard in between would also switch the flag on, so blocking by guards changes nothing). The four sweeps cover the four directions a guard can look from.
Complexity
- Time —
O(m · n + g + w) - Space —
O(m · n)
Pitfalls
- Guards and walls themselves are never counted as unguarded cells.
- A wall blocks a guard's view; a cell behind it is not watched from that side.
- Walking from every guard until the edge (ignoring blocks) overcounts and, on long rows, is too slow.
Reference solution
Python
from typing import List
def countUnguarded(m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
g = [[0] * n for _ in range(m)]
for r, c in guards:
g[r][c] = 1
for r, c in walls:
g[r][c] = 2
seen = [[False] * n for _ in range(m)]
def sweep(cells):
on = False
for r, c in cells:
v = g[r][c]
if v == 1:
on = True
elif v == 2:
on = False
elif on:
seen[r][c] = True
for r in range(m):
sweep([(r, c) for c in range(n)])
sweep([(r, c) for c in range(n - 1, -1, -1)])
for c in range(n):
sweep([(r, c) for r in range(m)])
sweep([(r, c) for r in range(m - 1, -1, -1)])
return sum(1 for r in range(m) for c in range(n) if g[r][c] == 0 and not seen[r][c])Java
public static int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
int[] g = new int[m * n];
boolean[] seen = new boolean[m * n];
for (int[] q : guards) g[q[0] * n + q[1]] = 1;
for (int[] w : walls) g[w[0] * n + w[1]] = 2;
for (int r = 0; r < m; r++) {
boolean on = false;
for (int c = 0; c < n; c++) on = visitCell(g, seen, r * n + c, on);
on = false;
for (int c = n - 1; c >= 0; c--) on = visitCell(g, seen, r * n + c, on);
}
for (int c = 0; c < n; c++) {
boolean on = false;
for (int r = 0; r < m; r++) on = visitCell(g, seen, r * n + c, on);
on = false;
for (int r = m - 1; r >= 0; r--) on = visitCell(g, seen, r * n + c, on);
}
int free = 0;
for (int i = 0; i < m * n; i++) if (g[i] == 0 && !seen[i]) free++;
return free;
}
private static boolean visitCell(int[] g, boolean[] seen, int idx, boolean on) {
if (g[idx] == 1) return true;
if (g[idx] == 2) return false;
if (on) seen[idx] = true;
return on;
}C++
int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
vector<int> g(m * n, 0);
vector<char> seen(m * n, 0);
for (auto& q : guards) g[q[0] * n + q[1]] = 1;
for (auto& w : walls) g[w[0] * n + w[1]] = 2;
auto visit = [&](int idx, bool on) {
if (g[idx] == 1) return true;
if (g[idx] == 2) return false;
if (on) seen[idx] = 1;
return on;
};
for (int r = 0; r < m; r++) {
bool on = false;
for (int c = 0; c < n; c++) on = visit(r * n + c, on);
on = false;
for (int c = n - 1; c >= 0; c--) on = visit(r * n + c, on);
}
for (int c = 0; c < n; c++) {
bool on = false;
for (int r = 0; r < m; r++) on = visit(r * n + c, on);
on = false;
for (int r = m - 1; r >= 0; r--) on = visit(r * n + c, on);
}
int free = 0;
for (int i = 0; i < m * n; i++) if (g[i] == 0 && !seen[i]) free++;
return free;
}JavaScript
var countUnguarded = function(m, n, guards, walls) {
var g = new Array(m * n).fill(0), seen = new Array(m * n).fill(false), i;
for (i = 0; i < guards.length; i++) g[guards[i][0] * n + guards[i][1]] = 1;
for (i = 0; i < walls.length; i++) g[walls[i][0] * n + walls[i][1]] = 2;
var visit = function(idx, on) {
if (g[idx] === 1) return true;
if (g[idx] === 2) return false;
if (on) seen[idx] = true;
return on;
};
var r, c, on;
for (r = 0; r < m; r++) {
on = false;
for (c = 0; c < n; c++) on = visit(r * n + c, on);
on = false;
for (c = n - 1; c >= 0; c--) on = visit(r * n + c, on);
}
for (c = 0; c < n; c++) {
on = false;
for (r = 0; r < m; r++) on = visit(r * n + c, on);
on = false;
for (r = m - 1; r >= 0; r--) on = visit(r * n + c, on);
}
var free = 0;
for (i = 0; i < m * n; i++) if (g[i] === 0 && !seen[i]) free++;
return free;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal