LeetCode 361 - Bomb Enemy

The problem presents an m x n matrix called grid where each element is a character representing either a wall 'W', an enemy 'E', or an empty cell '0'. The task is to determine the maximum number of enemies that can be eliminated by placing a single bomb in an empty cell.

leetcodemediumarraydynamic-programmingmatrix

LeetCode Problem 361

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

The problem presents an m x n matrix called grid where each element is a character representing either a wall 'W', an enemy 'E', or an empty cell '0'. The task is to determine the maximum number of enemies that can be eliminated by placing a single bomb in an empty cell. The bomb affects all enemies in the same row and column, but its effect is blocked by walls.

The input is a 2D matrix of size up to 500x500, which implies that a brute-force solution that checks every cell in every row and column could become computationally expensive. The output is an integer representing the maximum number of enemies that can be killed by placing the bomb optimally.

Important edge cases include grids with no empty cells, grids with no enemies, grids entirely filled with walls, and very long rows or columns that could stress performance. The problem guarantees valid inputs and non-empty grids, so we do not need to handle null or malformed inputs.

Approaches

Brute Force

A naive approach would involve iterating over every empty cell and counting the number of enemies in the same row and column until a wall is encountered. This ensures correctness because it checks every possible bomb placement. However, for a grid of size m x n, each check requires scanning up to m + n cells, resulting in a time complexity of O(m^2 * n + m * n^2) in the worst case. This is too slow for large grids like 500x500.

Optimal Approach

The key insight is that enemy counts in a row or column do not change unless a wall is encountered. We can precompute the number of enemies in segments of rows and columns between walls and reuse these counts for all empty cells in those segments. By storing these counts in temporary variables and updating them only when a new segment begins, we avoid repeated scanning and reduce time complexity to O(m * n).

Approach Time Complexity Space Complexity Notes
Brute Force O(m^2 * n + m * n^2) O(1) Check each empty cell by scanning full row and column
Optimal O(m * n) O(1) Reuse row and column counts, updating only at walls

Algorithm Walkthrough

  1. Initialize a variable max_enemies to store the maximum enemies that can be killed. Initialize row_hits to count enemies in the current row segment and an array col_hits of size n to count enemies in each column segment.
  2. Iterate over each cell in the grid. For each row, reset row_hits when starting a new row segment after a wall or at the beginning of a row. For each column, update col_hits[j] only at the start of a column segment or after a wall.
  3. If the current cell is an enemy 'E', increment row_hits and col_hits[j]. These counts represent the total number of enemies that would be killed if a bomb is placed at an empty cell in this segment.
  4. If the current cell is empty '0', compute the total kills as row_hits + col_hits[j] and update max_enemies if this is larger than the current maximum.
  5. Continue this process for the entire grid. After traversing all cells, max_enemies will contain the answer.

Why it works: The algorithm guarantees correctness because it accurately counts the number of enemies in each row and column segment separated by walls. By updating counts only at segment boundaries, it avoids repeated scanning and ensures that every empty cell is evaluated against the correct number of enemies.

Python Solution

from typing import List

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_enemies = 0
        col_hits = [0] * n

        for i in range(m):
            row_hits = 0
            for j in range(n):
                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
                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_enemies = max(max_enemies, row_hits + col_hits[j])
        return max_enemies

The implementation uses row_hits to track enemies in the current row segment and col_hits to track column enemies. For each empty cell, it calculates the total enemies killed by summing these counts. Counts are recomputed only when a new segment starts after a wall, which ensures optimal performance.

Go Solution

func maxKilledEnemies(grid [][]byte) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }
    m, n := len(grid), len(grid[0])
    maxEnemies := 0
    colHits := make([]int, n)

    for i := 0; i < m; i++ {
        rowHits := 0
        for j := 0; j < n; j++ {
            if j == 0 || grid[i][j-1] == 'W' {
                rowHits = 0
                for k := j; k < n && grid[i][k] != 'W'; k++ {
                    if grid[i][k] == 'E' {
                        rowHits++
                    }
                }
            }
            if i == 0 || grid[i-1][j] == 'W' {
                colHits[j] = 0
                for k := i; k < m && grid[k][j] != 'W'; k++ {
                    if grid[k][j] == 'E' {
                        colHits[j]++
                    }
                }
            }
            if grid[i][j] == '0' {
                if rowHits+colHits[j] > maxEnemies {
                    maxEnemies = rowHits + colHits[j]
                }
            }
        }
    }
    return maxEnemies
}

In Go, slices are used for colHits, and the logic mirrors the Python version. Edge cases are handled with initial checks for empty grids. Go does not require type hints, but the approach is otherwise identical.

Worked Examples

Example 1

Input:

grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]

Step by step evaluation:

i j row_hits col_hits[j] max_enemies
0 0 1 1 2
0 1 1 1 2
0 2 1 1 3
1 1 1 2 3

Final output: 3

Example 2

Input:

grid = [["W","W","W"],["0","0","0"],["E","E","E"]]

Evaluation:

Only empty cells are in row 1. Each has at most 1 enemy below before a wall, so max_enemies = 1.

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Each cell is visited once and enemy counts are updated at most twice per row/column segment
Space O(n) Only a single row_hits integer and a col_hits array of size n are used

This approach efficiently reduces unnecessary repeated scanning, making it feasible for large 500x500 grids.

Test Cases

# test cases
assert Solution().maxKilledEnemies([["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]) == 3  # Example 1
assert Solution().maxKilledEnemies([["W","W","W"],["0","0","0"],["E","E","E"]]) == 1  # Example 2
assert Solution().maxKilledEnemies([["0"]]) == 0  # Single empty cell, no enemies
assert Solution().maxKilledEnemies([["E"]]) == 0  # Single enemy, no empty cell
assert Solution().maxKilledEnemies([["W"]]) == 0  # Single wall, no empty cell
assert Solution().maxKilledEnemies([["0","0","0"],["0","0","0"],["0","0","0"]]) == 0  # Empty grid
assert Solution().maxKilledEnemies([["E","E","E"],["E","E","E"],["E","E","E"]]) == 0  # No empty cells
Test Why
Example 1 Standard case with multiple empty cells and walls
Example 2 Rows with only enemies separated by walls