Count Unguarded Cells in the Grid

Medium
1568.

Count Unguarded Cells in the Grid

Count Unguarded Cells in the Grid is a medium coding problem on arrays, matrix and simulation, asked in Amazon and Google interviews.

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^5
  • 2 <= m * n <= 10^5
  • 1 <= guards.length, walls.length <= 5 * 10^4
  • 2 <= guards.length + walls.length <= m * n
  • guards[i].length == walls[j].length == 2
  • 0 <= row < m, 0 <= col < n
  • all positions in guards and walls are unique
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} m
 * @param {number} n
 * @param {number[][]} guards
 * @param {number[][]} walls
 * @return {number}
 */
var countUnguarded = function(m, n, guards, walls) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 2 <= m * n <= 10^5
  • 1 <= guards.length, walls.length <= 5 * 10^4
  • 2 <= guards.length + walls.length <= m * n
  • guards[i].length == walls[j].length == 2
  • 0 <= row < m, 0 <= col < n
  • all positions in guards and walls are unique

Hints for Count Unguarded Cells in the Grid

  1. Hint 1

    Mark guards and walls on an m x n board first.

  2. Hint 2

    From each guard, walk in each direction until you hit a wall, a guard or the edge, marking the cells you pass.

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

  1. Build the board: 1 for a guard, 2 for a wall, 0 for empty.
  2. 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.
  3. Do the same down and up every column.
  4. 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