361. Bomb Enemy

Version # 1 Optimized DP
Space O(m)  Time O(mn)

Look all the way to the right nearest wall/border and count the enemies on the way
Look all the way to the bottom nearest wall/border and  count the enemies on the way
This will be the current count of total enemies if current position is a empty '0'
We don't need to update any enemies count unless we step into a wall position
After we step over a wall, all the left and up enemies count will become zero, now we need to walk toward right and bottom again to recalculate the enemies again
The amortized time complexity is O(mn)

99.05 %
class Solution {
    public int maxKilledEnemies(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
// count of emenies [x, nearest wall/border on the right]
int horizontalCount = 0;
// verticalCount[y] [y, nearest wall/border under current y)
int max = 0;
int[] verticalCount = new int[cols];
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
// update when going to new line or see a wall
if (x == 0 || grid[y][x - 1] == 'W') {
horizontalCount = 0;
int j = x;
while (j < cols && grid[y][j] != 'W') {
if (grid[y][j] == 'E') {
horizontalCount++;
}
j++;
}
// System.out.println(x + " " + y + " -> " + horizontalCount);
}
if (y == 0 || grid[y - 1][x] == 'W') {
verticalCount[x] = 0;
int i = y;
verticalCount[x] = 0;
while (i < rows && grid[i][x] != 'W') {
if (grid[i][x] == 'E') {
verticalCount[x]++;
}
i++;
}
// System.out.println(x + " " + y + " -> vertical " + verticalCount[x]);
}
if (grid[y][x] == '0') {
max = Math.max(max, horizontalCount + verticalCount[x]);
}
}
}
return max;
}
}