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

1
2
3
4
5
6
7
8
9

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

  1. 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.
  2. For each empty cell (‘0’), sum the number of enemies in all four directions.
  3. Track the maximum sum found for any empty cell.
  4. Return the maximum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

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.