Bomb Enemy
MediumUpdated: Aug 2, 2025
Practice on:
Problem
Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
Note: You can only put the bomb at an empty cell.
Examples
Example 1
Input: [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3
Explanation: For the given grid,
0 E 0 0
E 0 W E
0 E 0 0
Placing a bomb at (1,1) kills 3 enemies.
Solution
Method 1 – Dynamic Programming with Preprocessing
Intuition
The key idea is to efficiently count the number of enemies that can be killed from each empty cell by precomputing the number of enemies in all four directions (left, right, up, down) until a wall is encountered. This avoids redundant counting and speeds up the solution.
Approach
- For each row and column, preprocess and store the number of enemies that can be killed in each direction for every cell, stopping at walls.
- For each empty cell ('0'), sum the number of enemies in all four directions.
- Track the maximum sum found for any empty cell.
- Return the maximum.
Code
C++
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(), ans = 0;
vector<vector<int>> row(m, vector<int>(n)), col(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
int cnt = 0;
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 'W') cnt = 0;
else if (grid[i][j] == 'E') ++cnt;
row[i][j] = cnt;
}
cnt = 0;
for (int j = n - 1; j >= 0; --j) {
if (grid[i][j] == 'W') cnt = 0;
else if (grid[i][j] == 'E') ++cnt;
row[i][j] = max(row[i][j], cnt);
}
}
for (int j = 0; j < n; ++j) {
int cnt = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][j] == 'W') cnt = 0;
else if (grid[i][j] == 'E') ++cnt;
col[i][j] = cnt;
}
cnt = 0;
for (int i = m - 1; i >= 0; --i) {
if (grid[i][j] == 'W') cnt = 0;
else if (grid[i][j] == 'E') ++cnt;
col[i][j] = max(col[i][j], cnt);
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '0')
ans = max(ans, row[i][j] + col[i][j]);
}
}
return ans;
}
};
Go
func maxKilledEnemies(grid [][]byte) int {
m, n := len(grid), len(grid[0])
ans := 0
row := make([][]int, m)
col := make([][]int, m)
for i := range row {
row[i] = make([]int, n)
col[i] = make([]int, n)
}
for i := 0; i < m; i++ {
cnt := 0
for j := 0; j < n; j++ {
if grid[i][j] == 'W' {
cnt = 0
} else if grid[i][j] == 'E' {
cnt++
}
row[i][j] = cnt
}
cnt = 0
for j := n - 1; j >= 0; j-- {
if grid[i][j] == 'W' {
cnt = 0
} else if grid[i][j] == 'E' {
cnt++
}
if row[i][j] < cnt {
row[i][j] = cnt
}
}
}
for j := 0; j < n; j++ {
cnt := 0
for i := 0; i < m; i++ {
if grid[i][j] == 'W' {
cnt = 0
} else if grid[i][j] == 'E' {
cnt++
}
col[i][j] = cnt
}
cnt = 0
for i := m - 1; i >= 0; i-- {
if grid[i][j] == 'W' {
cnt = 0
} else if grid[i][j] == 'E' {
cnt++
}
if col[i][j] < cnt {
col[i][j] = cnt
}
}
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '0' {
if ans < row[i][j]+col[i][j] {
ans = row[i][j] + col[i][j]
}
}
}
}
return ans
}
Java
class Solution {
public int maxKilledEnemies(char[][] grid) {
if (grid.length == 0 || grid[0].length == 0) return 0;
int m = grid.length, n = grid[0].length, ans = 0;
int[][] row = new int[m][n], col = new int[m][n];
for (int i = 0; i < m; i++) {
int cnt = 0;
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'W') cnt = 0;
else if (grid[i][j] == 'E') cnt++;
row[i][j] = cnt;
}
cnt = 0;
for (int j = n - 1; j >= 0; j--) {
if (grid[i][j] == 'W') cnt = 0;
else if (grid[i][j] == 'E') cnt++;
row[i][j] = Math.max(row[i][j], cnt);
}
}
for (int j = 0; j < n; j++) {
int cnt = 0;
for (int i = 0; i < m; i++) {
if (grid[i][j] == 'W') cnt = 0;
else if (grid[i][j] == 'E') cnt++;
col[i][j] = cnt;
}
cnt = 0;
for (int i = m - 1; i >= 0; i--) {
if (grid[i][j] == 'W') cnt = 0;
else if (grid[i][j] == 'E') cnt++;
col[i][j] = Math.max(col[i][j], cnt);
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '0')
ans = Math.max(ans, row[i][j] + col[i][j]);
}
}
return ans;
}
}
Kotlin
class Solution {
fun maxKilledEnemies(grid: Array<CharArray>): Int {
if (grid.isEmpty() || grid[0].isEmpty()) return 0
val m = grid.size
val n = grid[0].size
var ans = 0
val row = Array(m) { IntArray(n) }
val col = Array(m) { IntArray(n) }
for (i in 0 until m) {
var cnt = 0
for (j in 0 until n) {
if (grid[i][j] == 'W') cnt = 0
else if (grid[i][j] == 'E') cnt++
row[i][j] = cnt
}
cnt = 0
for (j in n - 1 downTo 0) {
if (grid[i][j] == 'W') cnt = 0
else if (grid[i][j] == 'E') cnt++
row[i][j] = maxOf(row[i][j], cnt)
}
}
for (j in 0 until n) {
var cnt = 0
for (i in 0 until m) {
if (grid[i][j] == 'W') cnt = 0
else if (grid[i][j] == 'E') cnt++
col[i][j] = cnt
}
cnt = 0
for (i in m - 1 downTo 0) {
if (grid[i][j] == 'W') cnt = 0
else if (grid[i][j] == 'E') cnt++
col[i][j] = maxOf(col[i][j], cnt)
}
}
for (i in 0 until m) {
for (j in 0 until n) {
if (grid[i][j] == '0')
ans = maxOf(ans, row[i][j] + col[i][j])
}
}
return ans
}
}
Python
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])
ans = 0
row = [[0]*n for _ in range(m)]
col = [[0]*n for _ in range(m)]
for i in range(m):
cnt = 0
for j in range(n):
if grid[i][j] == 'W': cnt = 0
elif grid[i][j] == 'E': cnt += 1
row[i][j] = cnt
cnt = 0
for j in range(n-1, -1, -1):
if grid[i][j] == 'W': cnt = 0
elif grid[i][j] == 'E': cnt += 1
row[i][j] = max(row[i][j], cnt)
for j in range(n):
cnt = 0
for i in range(m):
if grid[i][j] == 'W': cnt = 0
elif grid[i][j] == 'E': cnt += 1
col[i][j] = cnt
cnt = 0
for i in range(m-1, -1, -1):
if grid[i][j] == 'W': cnt = 0
elif grid[i][j] == 'E': cnt += 1
col[i][j] = max(col[i][j], cnt)
for i in range(m):
for j in range(n):
if grid[i][j] == '0':
ans = max(ans, row[i][j] + col[i][j])
return ans
Rust
impl Solution {
pub fn max_killed_enemies(grid: Vec<Vec<char>>) -> i32 {
if grid.is_empty() || grid[0].is_empty() { return 0; }
let m = grid.len();
let n = grid[0].len();
let mut ans = 0;
let mut row = vec![vec![0; n]; m];
let mut col = vec![vec![0; n]; m];
for i in 0..m {
let mut cnt = 0;
for j in 0..n {
if grid[i][j] == 'W' { cnt = 0; }
else if grid[i][j] == 'E' { cnt += 1; }
row[i][j] = cnt;
}
cnt = 0;
for j in (0..n).rev() {
if grid[i][j] == 'W' { cnt = 0; }
else if grid[i][j] == 'E' { cnt += 1; }
row[i][j] = row[i][j].max(cnt);
}
}
for j in 0..n {
let mut cnt = 0;
for i in 0..m {
if grid[i][j] == 'W' { cnt = 0; }
else if grid[i][j] == 'E' { cnt += 1; }
col[i][j] = cnt;
}
cnt = 0;
for i in (0..m).rev() {
if grid[i][j] == 'W' { cnt = 0; }
else if grid[i][j] == 'E' { cnt += 1; }
col[i][j] = col[i][j].max(cnt);
}
}
for i in 0..m {
for j in 0..n {
if grid[i][j] == '0' {
ans = ans.max(row[i][j] + col[i][j]);
}
}
}
ans
}
}
TypeScript
class Solution {
maxKilledEnemies(grid: string[][]): number {
if (!grid.length || !grid[0].length) return 0;
const m = grid.length, n = grid[0].length;
let ans = 0;
const row = Array.from({length: m}, () => Array(n).fill(0));
const col = Array.from({length: m}, () => Array(n).fill(0));
for (let i = 0; i < m; i++) {
let cnt = 0;
for (let j = 0; j < n; j++) {
if (grid[i][j] === 'W') cnt = 0;
else if (grid[i][j] === 'E') cnt++;
row[i][j] = cnt;
}
cnt = 0;
for (let j = n - 1; j >= 0; j--) {
if (grid[i][j] === 'W') cnt = 0;
else if (grid[i][j] === 'E') cnt++;
row[i][j] = Math.max(row[i][j], cnt);
}
}
for (let j = 0; j < n; j++) {
let cnt = 0;
for (let i = 0; i < m; i++) {
if (grid[i][j] === 'W') cnt = 0;
else if (grid[i][j] === 'E') cnt++;
col[i][j] = cnt;
}
cnt = 0;
for (let i = m - 1; i >= 0; i--) {
if (grid[i][j] === 'W') cnt = 0;
else if (grid[i][j] === 'E') cnt++;
col[i][j] = Math.max(col[i][j], cnt);
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === '0')
ans = Math.max(ans, row[i][j] + col[i][j]);
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(mn); we visit each cell a constant number of times for preprocessing and summing, where m and n are the grid dimensions. - 🧺 Space complexity:
O(mn); we use two auxiliary matrices of the same size as the grid to store precomputed values.