# Java O(4mn) solution

• There are two loops as you can seen. The first loop I update every empty place by increase the enemy on its row. The second loop I update every place by increase the enemy on its col. Every loop is 2*mn, so the final time complexity is O(4mn).

``````public class Solution {
public int maxKilledEnemies(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int m = grid.length, n = grid[0].length;
int[][] matrix = new int[m][n];

for (int i = 0; i < m; i++) {
int col = 0;
int pre = 0;
while (col < n) {
int count = 0;

while (col < n && grid[i][col] != 'W') {
count = grid[i][col] == 'E' ? count + 1 : count;
col++;
}
for (int j = pre; j < col; j++) {
if (grid[i][j] != 'E' && grid[i][j] != 'W') matrix[i][j] += count;
}
pre = col + 1;
col++;
}
}

int max = 0;
for (int i = 0; i < n; i++) {
int row = 0;
int pre = 0;
while (row < m) {
int count = 0;

while (row < m && grid[row][i] != 'W') {
count = grid[row][i] == 'E' ? count + 1 : count;
row++;
}
for (int j = pre; j < row; j++) {
if (grid[j][i] != 'E' && grid[j][i] != 'W') {
matrix[j][i] += count;
max = matrix[j][i] > max ? matrix[j][i] : max;
}
}
pre = row + 1;
row++;
}
}
return max;
}
}
``````

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