Another O(mn) solution

• The idea is to scan each row twice and each column twice.

``````class Solution {
public int maxKilledEnemies(char[][] grid) {
int m = grid.length, n = (m>0)?grid[0].length : 0;
int max = 0;
int [][] count=new int[m][n];
int countE=0;
// rows
for (int i=0; i<m; i++) {
// row: left to right
countE=0;
for (int j=0;j<n;j++){
if (grid[i][j]=='W') countE=0;
if (grid[i][j]=='E') countE++;
if (grid[i][j]=='0') count[i][j]+=countE;
}
// row: right to left
countE=0;
for (int j=n-1;j>=0;j--){
if (grid[i][j]=='W') countE=0;
if (grid[i][j]=='E') countE++;
if (grid[i][j]=='0') count[i][j]+=countE;
}
}
// cols
for (int j=0; j<n; j++) {
// col: top to bottom
countE=0;
for (int i=0;i<m;i++){
if (grid[i][j]=='W') countE=0;
if (grid[i][j]=='E') countE++;
if (grid[i][j]=='0') count[i][j]+=countE;
}
// col: bottom to top
countE=0;
for (int i=m-1;i>=0;i--){
if (grid[i][j]=='W') countE=0;
if (grid[i][j]=='E') countE++;
if (grid[i][j]=='0') {
count[i][j]+=countE;
max = (count[i][j]>max)?count[i][j]:max;
}
}
}
return max;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.