LeetCode 361: Bomb Enemy

Problem Restatement

We are given an m x n grid.

Each cell is one of three characters:

We may place exactly one bomb, but only on an empty cell.

When the bomb explodes, it kills enemies in the same row and the same column.

The explosion stops when it hits a wall.

So a bomb can kill enemies:

left until a wall
right until a wall
up until a wall
down until a wall

Return the maximum number of enemies that can be killed by one bomb. If there is no useful bomb placement, return 0.

The official statement defines the grid cells as wall "W", enemy "E", or empty "0", and the bomb can only be placed in an empty cell. Walls block the explosion.

Input and Output

Example function shape:

def maxKilledEnemies(grid: list[list[str]]) -> int:
    ...

Examples

Example 1:

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

The best position is:

(1, 1)

From (1, 1):

Total:

3

So the answer is:

3

Example 2:

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

Each empty cell in row 1 can kill exactly one enemy below it.

So the answer is:

1

First Thought: Scan Four Directions

A direct solution is:

1. For every empty cell:
   • Scan left until a wall.
   • Scan right until a wall.
   • Scan up until a wall.
   • Scan down until a wall.
2. Count enemies.
3. Track the maximum count.

This works, but it repeats the same scans many times.

If the grid has no walls, then every empty cell scans almost the whole row and column.

With m rows and n columns, this can cost:

O(m * n * (m + n))

For grids up to 500 x 500, this is too slow.

Key Insight

Walls split each row and column into independent segments.

Inside one row segment between two walls, every empty cell can kill the same number of row enemies.

For example:

0 E 0 E 0 W E 0

The segment before the wall is:

0 E 0 E 0

Every empty cell in this segment can kill 2 row enemies.

So we should compute the row segment count once, then reuse it.

The same idea works for columns.

At each empty cell, the answer is:

row_enemies + col_enemies

where both counts are for the wall-bounded row and column segments containing that cell.

Algorithm

Maintain:

Scan the grid from top-left to bottom-right.

At cell (i, j):

1. If j == 0 or the cell to the left is a wall, recompute row_hits.
   • Scan right from (i, j) until a wall or end of row.
   • Count enemies.
2. If i == 0 or the cell above is a wall, recompute col_hits[j].
   • Scan down from (i, j) until a wall or end of column.
   • Count enemies.
3. If grid[i][j] == "0", update:

best = max(best, row_hits + col_hits[j])

4. Return best.

Correctness

A wall blocks the explosion, so the bomb can only affect enemies inside the same wall-bounded row segment and the same wall-bounded column segment.

When the scan reaches the start of a row segment, the algorithm counts all enemies in that row segment and stores the value in row_hits. Every later cell in the same segment reuses this value. This is correct because all cells in the same row segment see the same horizontal enemies.

Similarly, when the scan reaches the start of a column segment, the algorithm counts all enemies in that column segment and stores the value in col_hits[j]. Every later cell in that same column segment reuses this value. This is correct because all cells in the same column segment see the same vertical enemies.

For every empty cell, the algorithm adds the horizontal and vertical segment counts. These two counts represent exactly the enemies killed by a bomb at that cell. Walls stop both scans, so no enemy behind a wall is counted.

The algorithm evaluates every empty cell and keeps the maximum value. Therefore, it returns the maximum number of enemies one bomb can kill.

Complexity

Let m be the number of rows and n be the number of columns.

Although the code contains inner scans, each cell belongs to one row segment and one column segment, so the total work is linear in the grid size.

Implementation

class Solution:
    def maxKilledEnemies(self, grid: list[list[str]]) -> int:
        m = len(grid)
        n = len(grid[0])

        best = 0
        row_hits = 0
        col_hits = [0] * n

        for i in range(m):
            for j in range(n):
                if j == 0 or grid[i][j - 1] == "W":
                    row_hits = 0

                    col = j
                    while col < n and grid[i][col] != "W":
                        if grid[i][col] == "E":
                            row_hits += 1
                        col += 1

                if i == 0 or grid[i - 1][j] == "W":
                    col_hits[j] = 0

                    row = i
                    while row < m and grid[row][j] != "W":
                        if grid[row][j] == "E":
                            col_hits[j] += 1
                        row += 1

                if grid[i][j] == "0":
                    best = max(best, row_hits + col_hits[j])

        return best

Code Explanation

We read the grid dimensions:

m = len(grid)
n = len(grid[0])

The answer starts at zero:

best = 0

The current row segment count is stored here:

row_hits = 0

For columns, we need one cached count per column:

col_hits = [0] * n

When we are at the start of a row segment, we recompute row_hits:

if j == 0 or grid[i][j - 1] == "W":

Then scan right until a wall:

while col < n and grid[i][col] != "W":

Each enemy contributes one hit:

if grid[i][col] == "E":
    row_hits += 1

The column logic is symmetric.

When we are at the start of a column segment:

if i == 0 or grid[i - 1][j] == "W":

we scan downward and count enemies into col_hits[j].

Finally, only empty cells are valid bomb positions:

if grid[i][j] == "0":
    best = max(best, row_hits + col_hits[j])

Enemy cells and wall cells can contribute to segment counts, but they cannot hold the bomb.

Testing

def run_tests():
    s = Solution()

    assert s.maxKilledEnemies([
        ["0", "E", "0", "0"],
        ["E", "0", "W", "E"],
        ["0", "E", "0", "0"],
    ]) == 3

    assert s.maxKilledEnemies([
        ["W", "W", "W"],
        ["0", "0", "0"],
        ["E", "E", "E"],
    ]) == 1

    assert s.maxKilledEnemies([
        ["0"],
    ]) == 0

    assert s.maxKilledEnemies([
        ["E"],
    ]) == 0

    assert s.maxKilledEnemies([
        ["0", "E", "W", "E", "0"],
    ]) == 1

    assert s.maxKilledEnemies([
        ["0"],
        ["E"],
        ["W"],
        ["E"],
        ["0"],
    ]) == 1

    print("all tests passed")

run_tests()

Test meaning: