Skip to main content
Back to problems
#361
Medium Algorithms

Bomb enemy

Array Dynamic Programming Matrix
52.8% acceptance
Mar 31, 2026
1003
118

No description available.

Solution

Rust
Time O(n³)
Space O(n)
LeetCode
solution.rs
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 col_hits = vec![0i32; n];
    let mut row_hits;
    let mut ans = 0;

    for i in 0..m {
      for j in 0..n {
        // Recompute row_hits when at col 0 or just after a wall
        if j == 0 || grid[i][j - 1] == 'W' {
          row_hits = 0;
          let mut k = j;
          while k < n && grid[i][k] != 'W' {
            if grid[i][k] == 'E' {
              row_hits += 1;
            }
            k += 1;
          }
        } else {
          // row_hits carries over
        }
        // Recompute col_hits[j] when at row 0 or just after a wall
        if i == 0 || grid[i - 1][j] == 'W' {
          col_hits[j] = 0;
          let mut k = i;
          while k < m && grid[k][j] != 'W' {
            if grid[k][j] == 'E' {
              col_hits[j] += 1;
            }
            k += 1;
          }
        }
        if grid[i][j] == '0' {
          // Need row_hits here; let's restructure
        }
      }
    }

    // Cleaner approach: precompute properly
    let mut result = 0;
    let mut col_kills = vec![0i32; n];
    for i in 0..m {
      let mut row_kill = 0i32;
      for j in 0..n {
        if j == 0 || grid[i][j - 1] == 'W' {
          row_kill = 0;
          let mut k = j;
          while k < n && grid[i][k] != 'W' {
            if grid[i][k] == 'E' { row_kill += 1; }
            k += 1;
          }
        }
        if i == 0 || grid[i - 1][j] == 'W' {
          col_kills[j] = 0;
          let mut k = i;
          while k < m && grid[k][j] != 'W' {
            if grid[k][j] == 'E' { col_kills[j] += 1; }
            k += 1;
          }
        }
        if grid[i][j] == '0' {
          result = result.max(row_kill + col_kills[j]);
        }
      }
    }
    result
  }
}