361. Bomb Enemy - Leetcode Solution

Code Implementation

class Solution:
    def maxKilledEnemies(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        m, n = len(grid), len(grid[0])
        max_kills = 0
        row_hits = 0
        col_hits = [0] * n

        for i in range(m):
            for j in range(n):
                # Compute row_hits
                if j == 0 or grid[i][j-1] == 'W':
                    row_hits = 0
                    k = j
                    while k < n and grid[i][k] != 'W':
                        if grid[i][k] == 'E':
                            row_hits += 1
                        k += 1
                # Compute col_hits
                if i == 0 or grid[i-1][j] == 'W':
                    col_hits[j] = 0
                    k = i
                    while k < m and grid[k][j] != 'W':
                        if grid[k][j] == 'E':
                            col_hits[j] += 1
                        k += 1
                if grid[i][j] == '0':
                    max_kills = max(max_kills, row_hits + col_hits[j])
        return max_kills

class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size();
        int max_kills = 0;
        int row_hits = 0;
        vector<int> col_hits(n, 0);

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // Compute row_hits
                if (j == 0 || grid[i][j-1] == 'W') {
                    row_hits = 0;
                    for (int k = j; k < n && grid[i][k] != 'W'; ++k) {
                        if (grid[i][k] == 'E') row_hits++;
                    }
                }
                // Compute col_hits
                if (i == 0 || grid[i-1][j] == 'W') {
                    col_hits[j] = 0;
                    for (int k = i; k < m && grid[k][j] != 'W'; ++k) {
                        if (grid[k][j] == 'E') col_hits[j]++;
                    }
                }
                if (grid[i][j] == '0') {
                    max_kills = max(max_kills, row_hits + col_hits[j]);
                }
            }
        }
        return max_kills;
    }
};

class Solution {
    public int maxKilledEnemies(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length, n = grid[0].length;
        int maxKills = 0;
        int rowHits = 0;
        int[] colHits = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Compute rowHits
                if (j == 0 || grid[i][j-1] == 'W') {
                    rowHits = 0;
                    for (int k = j; k < n && grid[i][k] != 'W'; k++) {
                        if (grid[i][k] == 'E') rowHits++;
                    }
                }
                // Compute colHits
                if (i == 0 || grid[i-1][j] == 'W') {
                    colHits[j] = 0;
                    for (int k = i; k < m && grid[k][j] != 'W'; k++) {
                        if (grid[k][j] == 'E') colHits[j]++;
                    }
                }
                if (grid[i][j] == '0') {
                    maxKills = Math.max(maxKills, rowHits + colHits[j]);
                }
            }
        }
        return maxKills;
    }
}

var maxKilledEnemies = function(grid) {
    if (!grid || grid.length === 0 || grid[0].length === 0) return 0;
    let m = grid.length, n = grid[0].length;
    let maxKills = 0;
    let rowHits = 0;
    let colHits = new Array(n).fill(0);

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // Compute rowHits
            if (j === 0 || grid[i][j-1] === 'W') {
                rowHits = 0;
                for (let k = j; k < n && grid[i][k] !== 'W'; k++) {
                    if (grid[i][k] === 'E') rowHits++;
                }
            }
            // Compute colHits
            if (i === 0 || grid[i-1][j] === 'W') {
                colHits[j] = 0;
                for (let k = i; k < m && grid[k][j] !== 'W'; k++) {
                    if (grid[k][j] === 'E') colHits[j]++;
                }
            }
            if (grid[i][j] === '0') {
                maxKills = Math.max(maxKills, rowHits + colHits[j]);
            }
        }
    }
    return maxKills;
};

Problem Description

Given a 2D grid representing a map of the room where:

'E' represents an enemy
'W' represents a wall
'0' (zero) represents an empty cell

You can place a bomb in any empty cell ('0'). The bomb kills all enemies in the same row and column until it hits a wall ('W'). The bomb does not kill enemies behind a wall or in other rows/columns.

Your task is to find the maximum number of enemies that can be killed with a single bomb placement. You must not reuse elements and can only place one bomb.

Thought Process

The brute-force approach is straightforward: for every empty cell, simulate placing a bomb there and count how many enemies are killed in both the row and column, stopping at walls. However, this is inefficient because it repeats the same counting work for overlapping rows and columns many times.

To optimize, you can precompute or cache the number of enemies in each row and column segment (between walls), so that when you reach an empty cell, you already know how many enemies would be killed if a bomb is placed there. This avoids redundant counting and speeds up the process.

Solution Approach

The optimized algorithm works as follows:

Iterate through each cell in the grid.
For each cell, if it's at the start of a row segment (either the first column or after a wall), count the number of enemies to the right until a wall is hit, and store it as row_hits.
Similarly, for each column, if at the start of a column segment, count the number of enemies downwards until a wall is hit, and store it in col_hits (an array, one per column).
If the cell is empty ('0'), the total enemies killed by a bomb is row_hits + col_hits[j], where j is the column index.
Keep track of the maximum value seen during this process.

This approach only counts enemies for each row and column segment once, making it much faster than the naive approach.
We use simple variables and arrays for caching, which makes lookups and updates very efficient.

Example Walkthrough

Consider the grid:

  [
    ['0', 'E', '0', '0'],
    ['E', '0', 'W', 'E'],
    ['0', 'E', '0', '0']
  ]

Start at (0,0): it's empty. Count enemies to the right (hits 1 at (0,1)), and down (hits 1 at (1,0)). So total = 2.
At (0,1): enemy, skip.
At (0,2): empty. To the right: 0 enemies. Down: wall at (1,2), so only look at (0,2). Total = 0.
At (0,3): empty. To the right: 0. Down: (1,3) is enemy, (2,3) is empty. Total = 1.
Continue for each empty cell, using cached row and column counts.
The best cell is (1,1): row (1,1)-(1,2)-(1,3) has 1 enemy, column (0,1)-(1,1)-(2,1) has 2 enemies. Total = 3.

So, the maximum enemies killed is 3.

Time and Space Complexity

Brute-force approach: For each empty cell, scan its row and column, leading to O(mn(m+n)) time for an m x n grid.
Optimized approach: Each row and each column segment is only counted once, so the time complexity is O(mn).
Space complexity is O(n) for the column hits array, and O(1) for row hits.

This makes the optimized solution suitable for large grids.

Summary

The Bomb Enemy problem can be solved efficiently by caching the number of enemies in each row and column segment between walls. By avoiding redundant counting, we reduce the time complexity from O(mn(m+n)) to O(mn). The solution is elegant because it leverages simple observations about the grid structure and uses basic variables to store partial results, making it both fast and easy to implement.

AlgoMap.io

Want Help Cracking FAANG?