361. Bomb Enemy

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 that you can only put the bomb at an empty cell. 

Example:

For the given grid

0 E 0 0
E 0 W E
0 E 0 0

return 3. (Placing a bomb at (1,1) kills 3 enemies)

Solution:

We use two for loops to go through all points.

If we find the point is a horizontal start point, we calculate the enemies in this row till the next wall.

If the point is also a vertical start point, we calculate the enemies in this column till the next wall.

Then we check if this point is "0", we calculate the enemies it can bomb, and update the result.

We have three loops but the third loop is in parallel with the second one.

Thus, the time complexity is O(mn) and the space complexity is O(n).



Code:

public class Solution {
    public int maxKilledEnemies(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        if (grid[0] == null || grid[0].length == 0) {
            return 0;
        }
        int result = 0;
        int m = grid.length;
        int n = grid[0].length;
        int rowCnt = 0;
        int[] colCnt = new int[n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j == 0 || grid[i][j - 1] == 'W') {
                    rowCnt = 0;
                    for (int k = j; k < n && grid[i][k] != 'W'; k++) {
                        rowCnt += grid[i][k] == 'E' ? 1 : 0;
                    }
                }
                if (i == 0 || grid[i - 1][j] == 'W') {
                    colCnt[j] = 0;
                    for (int k = i; k < m && grid[k][j] != 'W'; k++) {
                        colCnt[j] += grid[k][j] == 'E' ? 1 : 0;
                    }
                }
                if (grid[i][j] == '0' && rowCnt + colCnt[j] > result) {
                    result = rowCnt + colCnt[j];
                }
            }
        }
        return result;
    }
}