📘 Problem Statement
You are given a 2D grid with three possible values:
'W': Wall'E': Enemy'0': Empty cell
You can place one bomb in any empty cell, which will kill all the enemies in the same row and column until it hits a wall.
Return the maximum number of enemies you can kill with one bomb.
🧠 Key Insight
We want to avoid recalculating how many enemies are in the same row and column repeatedly.
Use dynamic programming + caching:
- Traverse the grid.
- Reuse row kills and column kills unless blocked by a wall.
- When we hit an empty cell, we calculate the potential kill and update the maximum.
🐍 Python Code
python
from typing import List
class Solution:
def maxKilledEnemies(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
max_kills = 0
row_hits = 0
col_hits = [0] * cols
for i in range(rows):
for j in range(cols):
# Calculate row hits when at first column or after a wall
if j == 0 or grid[i][j - 1] == 'W':
row_hits = 0
k = j
while k < cols and grid[i][k] != 'W':
if grid[i][k] == 'E':
row_hits += 1
k += 1
# Calculate column hits when at first row or after a wall
if i == 0 or grid[i - 1][j] == 'W':
col_hits[j] = 0
k = i
while k < rows and grid[k][j] != 'W':
if grid[k][j] == 'E':
col_hits[j] += 1
k += 1
# Place bomb at empty cell
if grid[i][j] == '0':
max_kills = max(max_kills, row_hits + col_hits[j])
return max_kills
🔍 Step-by-Step Explanation
1. Initialization
python
row_hits = 0
col_hits = [0] * cols
row_hits: caches enemies in the current row (until wall).col_hits[j]: caches enemies in column j (until wall).
2. Recalculate Row Hits Only After a Wall
python
if j == 0 or grid[i][j - 1] == 'W':
- Reset and recalculate from here to the next wall.
3. Recalculate Column Hits Only After a Wall
python
if i == 0 or grid[i - 1][j] == 'W':
- Recalculate column from this cell downwards until wall.
4. Update Max at Empty Cell
python
if grid[i][j] == '0':
max_kills = max(max_kills, row_hits + col_hits[j])
- Calculate how many enemies would be hit if a bomb is placed here.
💡 Example
python
Input:
[
["0","E","0","0"],
["E","0","W","E"],
["0","E","0","0"]
]
Output: 3
- Best place to drop the bomb is at
grid[1][1] to hit 3 enemies: top, left, and right.
⏱️ Time & Space Complexity
MetricComplexityTimeO(m × n)SpaceO(n)
🧵 Final Thoughts
This problem is a great test of dynamic programming tricks within grid traversal:
- Use caching smartly to avoid redundant calculations.
- Understand direction-based scanning (
row, column) and where walls interrupt.