Problem Description

You have a grid with m rows and n columns (0-indexed). In this grid, there are guards and walls placed at specific positions.

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

A guard can see in all four cardinal directions (north, east, south, west) from their position. Their vision extends indefinitely in each direction until blocked by either a wall or another guard. Any cell that can be seen by at least one guard is considered "guarded."

The task is to count how many cells are:

1. Unoccupied (not containing a guard or wall)
2. Not guarded (cannot be seen by any guard)

For example, if a guard is at position (1, 1) in a 3×3 grid with no walls:

• The guard can see cells (0, 1), (2, 1) horizontally
• The guard can see cells (1, 0), (1, 2) vertically
• These cells would be considered "guarded"

Return the total number of unoccupied cells that are not guarded.

Intuition

The key insight is that we need to track the state of each cell in the grid. Each cell can be in one of three states:

• Contains a guard or wall (occupied)
• Can be seen by at least one guard (guarded)
• Cannot be seen by any guard (unguarded)

We can use a 2D array to represent the grid and mark different states with different values. Let's use:

• 0 for unguarded cells
• 1 for guarded cells
• 2 for cells with guards or walls

The simulation approach becomes natural when we think about how a guard's vision works. From each guard's position, we need to "shoot rays" in four cardinal directions. Each ray continues until it hits an obstacle (another guard or wall) or reaches the grid boundary.

Why simulate from each guard individually? Because each guard contributes independently to the guarded area. A cell becomes guarded if ANY guard can see it, so we need to check all guards.

The direction vectors (-1, 0, 1, 0, -1) cleverly encode the four directions when taken in pairs: up (-1, 0), right (0, 1), down (1, 0), and left (0, -1). This allows us to iterate through all four directions with a simple loop.

During the ray-casting process, we only mark cells with value less than 2 (meaning they're not occupied by guards/walls) as guarded. This ensures we stop at obstacles while marking all visible empty cells.

Finally, counting cells with value 0 gives us the unguarded, unoccupied cells - exactly what the problem asks for.

Solution Approach

We implement the simulation approach using a 2D array to track cell states.

Step 1: Initialize the Grid

Create a 2D array g of size m × n initialized with all zeros:

g = [[0] * n for _ in range(m)]

• 0 represents unguarded cells
• 1 will represent guarded cells
• 2 will represent occupied cells (guards/walls)

Step 2: Mark Occupied Positions

First, mark all guard and wall positions with value 2:

for i, j in guards:
    g[i][j] = 2
for i, j in walls:
    g[i][j] = 2

This prevents us from marking these cells as guarded and stops our vision rays at these positions.

Step 3: Simulate Guard Vision

For each guard, cast rays in four cardinal directions:

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

The pairwise(dirs) creates direction vectors: (-1, 0) for up, (0, 1) for right, (1, 0) for down, (0, -1) for left.

For each direction:

• Start from the guard's position (i, j)
• Move step by step in that direction (x + a, y + b)
• Continue while:
  • We stay within grid bounds: 0 <= x + a < m and 0 <= y + b < n
  • The next cell is not occupied: g[x + a][y + b] < 2
• Mark each visited cell as guarded: g[x][y] = 1

Step 4: Count Unguarded Cells

Count all cells that remain with value 0:

return sum(v == 0 for row in g for v in row)

This double iteration counts every cell in the grid that is neither occupied nor guarded.

Time Complexity: O(m × n × (m + n)) in the worst case, as each guard might need to check up to m + n cells.

Space Complexity: O(m × n) for the grid array.

Example Walkthrough

Let's walk through a small example with a 4×3 grid, 2 guards at positions [(1,1), (2,0)], and 1 wall at position [(0,2)].

Step 1: Initialize the Grid We create a 4×3 grid filled with zeros:

0 0 0
0 0 0
0 0 0
0 0 0

Step 2: Mark Occupied Positions Place guards (G) and wall (W) by marking them with value 2:

0 0 W(2)
0 G(2) 0
G(2) 0 0
0 0 0

Step 3: Simulate Guard Vision

For guard at (1,1):

• Up direction (-1,0): Move from (1,1) to (0,1). Mark (0,1) as guarded (1). Can't continue - reached grid boundary.
• Right direction (0,1): Move from (1,1) to (1,2). Mark (1,2) as guarded (1). Can't continue - reached grid boundary.
• Down direction (1,0): Move from (1,1) to (2,1). Mark (2,1) as guarded (1). Continue to (3,1), mark as guarded (1). Can't continue - reached grid boundary.
• Left direction (0,-1): Move from (1,1) to (1,0). Mark (1,0) as guarded (1). Can't continue - reached grid boundary.

Grid after first guard:

0 1 W(2)
1 G(2) 1
G(2) 1 0
0 1 0

For guard at (2,0):

• Up direction (-1,0): Move from (2,0) to (1,0). Cell already guarded (1), mark stays as 1. Continue to (0,0), mark as guarded (1). Can't continue - reached grid boundary.
• Right direction (0,1): Move from (2,0) to (2,1). Cell already guarded (1), mark stays as 1. Continue to (2,2), mark as guarded (1). Can't continue - reached grid boundary.
• Down direction (1,0): Move from (2,0) to (3,0). Mark (3,0) as guarded (1). Can't continue - reached grid boundary.
• Left direction (0,-1): Can't move - would go out of bounds immediately.

Final grid state:

1 1 W(2)
1 G(2) 1
G(2) 1 1
1 1 0

Step 4: Count Unguarded Cells Count cells with value 0: Only cell (3,2) has value 0.

Answer: 1 unguarded, unoccupied cell

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n × (g + w))

The algorithm consists of:

1. Grid initialization: O(m × n)
2. Marking guards: O(g) where g is the number of guards
3. Marking walls: O(w) where w is the number of walls
4. Guard vision calculation: For each guard, we check in 4 directions. In the worst case, each direction traverses the entire row or column, giving O(g × (m + n)). However, since multiple guards can traverse the same cells, the total cells visited across all guards and directions is bounded by O(m × n) for each direction, resulting in O(m × n) overall.
5. Counting unguarded cells: O(m × n)

The dominant operation is the guard vision calculation which visits each cell at most 4 times (once from each direction), giving a total time complexity of O(m × n).

Space Complexity: O(m × n)

The algorithm uses a 2D grid g of size m × n to track the state of each cell (0 for unguarded, 1 for guarded, 2 for guard/wall). No additional significant space is used, resulting in space complexity of O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Marking Guard/Wall Positions After Processing Vision

The Problem: A common mistake is to mark the guard positions as occupied (value 2) AFTER simulating their vision. This causes the guard's own position to be counted as "guarded" (value 1) when another guard looks in that direction.

Incorrect Implementation:

# Process guard vision first
for guard_row, guard_col in guards:
    for delta_row, delta_col in directions:
        # ... cast vision rays ...
      
# Then mark guards - TOO LATE!
for row, col in guards:
    grid[row][col] = 2

Why This Fails: When Guard A at position (1, 1) casts vision and then Guard B at position (1, 3) casts vision leftward, Guard B would mark Guard A's position as "guarded" instead of stopping at it. This leads to incorrect counting.

The Solution: Always mark all occupied positions (both guards and walls) BEFORE processing any guard's vision:

# Mark all occupied positions first
for row, col in guards:
    grid[row][col] = 2
for row, col in walls:
    grid[row][col] = 2

# Then process vision
for guard_row, guard_col in guards:
    # ... cast vision rays ...

Pitfall 2: Incorrect Boundary Check in While Loop

The Problem: Using the wrong boundary check can cause index out of bounds errors or miss valid cells.

Incorrect Implementation:

while (current_row + delta_row < m and 
       current_col + delta_col < n and 
       grid[current_row + delta_row][current_col + delta_col] < 2):
    # Missing check for negative indices!

Why This Fails: When moving upward (delta_row = -1) or leftward (delta_col = -1), current_row + delta_row or current_col + delta_col could become negative, causing Python to access the array from the end (negative indexing) instead of stopping.

The Solution: Include both lower and upper bound checks:

while (0 <= current_row + delta_row < m and 
       0 <= current_col + delta_col < n and 
       grid[current_row + delta_row][current_col + delta_col] < 2):

Pitfall 3: Overwriting Guard Vision Information

The Problem: If you use the same value to mark both guards/walls and guarded cells, you lose the ability to distinguish between them.

Incorrect Implementation:

# Using value 1 for both guards/walls and guarded cells
for row, col in guards:
    grid[row][col] = 1  # Same value as guarded!

Why This Fails: When a guard tries to cast vision, it won't know whether a cell with value 1 is another guard (should stop) or just a guarded cell (should continue).

The Solution: Use distinct values for different states:

• 0 = unguarded and unoccupied
• 1 = guarded (but unoccupied)
• 2 = occupied (guard or wall)