LeetCode 2257: Count Unguarded Cells in the Grid Solution

Master LeetCode problem 2257 (Count Unguarded Cells in the Grid), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2257. Count Unguarded Cells in the Grid

Medium

Array Matrix Simulation

Problem Explanation

Explanation:

To solve this problem, we need to determine the unguarded cells in the grid by considering the positions of guards and walls. We can achieve this by simulating the visibility of guards in the grid and marking the cells they can see. Finally, we count the unguarded cells that are not marked by any guard.

Create a boolean grid to represent the visibility status of each cell.
Iterate through the guards and mark the cells they can see in all four cardinal directions.
Iterate through the walls and mark the cells they obstruct.
Count the unguarded cells that are not marked by any guard.

Time Complexity: O(m * n + guards.length + walls.length) Space Complexity: O(m * n)

Solution Code

class Solution {
    public int countUnguardedCells(int m, int n, int[][] guards, int[][] walls) {
        boolean[][] guarded = new boolean[m][n];
        
        for (int[] guard : guards) {
            int row = guard[0];
            int col = guard[1];
            markVisibleCells(row, col, m, n, guarded);
        }
        
        for (int[] wall : walls) {
            int row = wall[0];
            int col = wall[1];
            guarded[row][col] = true;
        }
        
        int unguardedCount = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!guarded[i][j]) {
                    unguardedCount++;
                }
            }
        }
        
        return unguardedCount;
    }
    
    private void markVisibleCells(int row, int col, int m, int n, boolean[][] guarded) {
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (int[] dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            while (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                guarded[newRow][newCol] = true;
                newRow += dir[0];
                newCol += dir[1];
            }
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2257 (Count Unguarded Cells in the Grid)?

This page provides optimized solutions for LeetCode problem 2257 (Count Unguarded Cells in the Grid) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2257 (Count Unguarded Cells in the Grid)?

The time complexity for LeetCode 2257 (Count Unguarded Cells in the Grid) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2257 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2257 in Java, C++, or Python.

Back to LeetCode Solutions