Count Unguarded Cells in the Grid - Practice Coding Problems

Count Unguarded Cells in the Grid - Problem

You are given two integers m and n representing a 0-indexed m × n grid. You are also given two 2D integer arrays guards and walls where:

guards[i] = [row_i, col_i] represents the position of the i-th guard
walls[j] = [row_j, col_j] represents the position of the j-th wall

A guard can see every cell in the four cardinal directions (north, east, south, 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.

Input & Output

Example 1 — Basic Grid

$ Input: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]

› Output: 7

💡 Note: Guards at (0,0), (1,1), and (2,3) can see in 4 directions until blocked by walls. After marking all guarded cells, 7 cells remain unguarded.

Example 2 — Small Grid

$ Input: m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,2],[2,1]]

› Output: 4

💡 Note: Single guard at center (1,1) is surrounded by walls, can only see 4 adjacent cells. The 4 corner cells remain unguarded.

Example 3 — No Walls

$ Input: m = 2, n = 2, guards = [[0,0]], walls = []

› Output: 0

💡 Note: Guard at (0,0) can see all other cells in the 2×2 grid since there are no walls blocking the view.

Constraints

1 ≤ m, n ≤ 10⁵
2 ≤ m × n ≤ 10⁵
1 ≤ guards.length, walls.length ≤ 5 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Grid with guards (G) and walls (W) placed

Guard Vision

Guards see in 4 directions until blocked

Count Result

Count cells that no guard can see

Key Takeaway

🎯 Key Insight: Guards cast vision rays in cardinal directions, stopped only by walls or other guards

Asked in

G Google 8 a Amazon 5 M Microsoft 4

The key insight is to simulate guard vision by casting rays in 4 directions until hitting obstacles. Best approach is Grid Marking Simulation which marks all guarded cells first, then counts unmarked ones. Time: O(m×n×g), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Grid Marking Simulation	O(m×n×g)	O(m×n)	Mark all guarded cells by simulating guard vision, then count unmarked cells
Check Each Cell Individually	O(m²×n²×g)	O(1)	For each cell, check if any guard can see it by tracing lines of sight

Grid Marking Simulation — Algorithm Steps

Step 1: Initialize grid and mark guards/walls
Step 2: For each guard, cast vision rays in 4 directions
Step 3: Mark all cells visible to guards
Step 4: Count unmarked cells

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup Grid

Place guards (G) and walls (W) on grid

Cast Rays

Each guard shoots vision rays in 4 directions

Mark Guarded

Mark all cells visible to guards, count unmarked

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int m, int n, int guards[][2], int guardCount, int walls[][2], int wallCount) {
    // 0 = empty, 1 = guard, 2 = wall, 3 = guarded
    int** grid = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        grid[i] = (int*)calloc(n, sizeof(int));
    }
    
    // Place guards and walls
    for (int i = 0; i < guardCount; i++) {
        grid[guards[i][0]][guards[i][1]] = 1;
    }
    for (int i = 0; i < wallCount; i++) {
        grid[walls[i][0]][walls[i][1]] = 2;
    }
    
    // Directions: north, east, south, west
    int directions[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
    // For each guard, mark visible cells
    for (int i = 0; i < guardCount; i++) {
        int gr = guards[i][0], gc = guards[i][1];
        for (int d = 0; d < 4; d++) {
            int dr = directions[d][0], dc = directions[d][1];
            int r = gr + dr, c = gc + dc;
            
            // Cast ray until hitting boundary, wall, or another guard
            while (r >= 0 && r < m && c >= 0 && c < n) {
                if (grid[r][c] == 2 || grid[r][c] == 1) { // Wall or guard blocks
                    break;
                }
                if (grid[r][c] == 0) { // Empty cell becomes guarded
                    grid[r][c] = 3;
                }
                r += dr;
                c += dc;
            }
        }
    }
    
    // Count unguarded cells (still 0)
    int unguarded = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 0) {
                unguarded++;
            }
        }
    }
    
    // Free memory
    for (int i = 0; i < m; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return unguarded;
}

int main() {
    int m, n;
    scanf("%d", &m);
    scanf("%d", &n);
    
    // Simplified parsing - would need full JSON parser for real implementation
    int guards[100][2], walls[100][2];
    int guardCount = 0, wallCount = 0;
    
    int result = solution(m, n, guards, guardCount, walls, wallCount);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n×g)

Each guard casts rays in 4 directions, maximum O(m+n) cells per direction

✓ Linear Growth

Space Complexity

O(m×n)

Grid array to store cell states (guard/wall/guarded/empty)

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Grid Marking Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler