Is Count Unguarded Cells in the Grid easy or hard?

The problem is rated Medium on LeetCode with an acceptance rate around 69%. The challenge comes from efficiently simulating guard visibility while avoiding redundant scans across the grid.

Count Unguarded Cells in the Grid Python/Java solution

Python, Java, C++, and JavaScript implementations typically represent the board as a matrix and mark guards, walls, and guarded cells. The BFS solution expands from each guard using loops or a queue, while the sweep solution iterates through rows and columns to propagate guard visibility efficiently.

How to solve Count Unguarded Cells in the Grid in O(m*n)?

Use a directional grid sweep. Traverse rows left-to-right and right-to-left while tracking the last guard seen unless a wall resets the state. Repeat the same process vertically (top-to-bottom and bottom-to-top). Mark cells guarded during these sweeps, then count cells that remain empty and unguarded.

What is the best approach for Count Unguarded Cells in the Grid?

The two-pass grid sweep is the most efficient and interview-friendly approach. It scans the grid horizontally and vertically while tracking whether a guard is active in the current direction. This avoids expanding from each guard individually and processes every cell a constant number of times, giving O(m*n) time with O(1) extra space.

Is Count Unguarded Cells in the Grid asked at Google/Amazon/Meta?

Grid simulation and visibility problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. They test matrix traversal, simulation logic, and optimization of repeated scans across a grid.

What data structure is used in Count Unguarded Cells in the Grid?

The problem primarily uses a 2D grid (matrix). BFS-based solutions use queues for directional expansion, while the optimized approach relies on simple array or matrix sweeps with directional state tracking.

What is the time complexity of Count Unguarded Cells in the Grid?

The optimal solution runs in O(m*n) time where m and n are the grid dimensions. Each cell is visited during directional sweeps or guard expansions only a constant number of times. Space complexity ranges from O(1) for the sweep approach to O(m*n) if BFS simulation uses additional visited structures.

Description Hints 2 Solution Video 17:14

2257. Count Unguarded Cells in the Grid

Medium69.0% acceptance6 companies

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] = [row_i, col_i] and walls[j] = [row_j, col_j] represent the positions of the i^th guard and j^th 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: