# python accepted O(mn) solution (rather than O(mn*(m+n)))

• Calculate grid value by 4-way scan, each O(mn), then find the max, still O(mn)

``````class Solution(object):
def maxKilledEnemies(self, grid):

if not grid: return 0
if not grid[0]: return 0

# collect row, col info O(m+n)
row_cnt, col_cnt = len(grid), len(grid[0])
self.grid = grid
self.value = [[0]*col_cnt for _ in range(row_cnt)]

# row direction scan, O(m*n)
for i in range(row_cnt):
# accumulate toward right
cnt = 0
for j in range(col_cnt):
self.value[i][j] += cnt
if grid[i][j] == 'E': cnt += 1
if grid[i][j] == 'W': cnt = 0
# accumulate toward right
cnt = 0
for j in reversed(range(col_cnt)):
self.value[i][j] += cnt
if grid[i][j] == 'E': cnt += 1
if grid[i][j] == 'W': cnt = 0

# col direction scan, O(m*n)
for j in reversed(range(col_cnt)):
# accumulate toward right
cnt = 0
for i in range(row_cnt):
self.value[i][j] += cnt
if grid[i][j] == 'E': cnt += 1
if grid[i][j] == 'W': cnt = 0
# accumulate toward right
cnt = 0
for i in reversed(range(row_cnt)):
self.value[i][j] += cnt
if grid[i][j] == 'E': cnt += 1
if grid[i][j] == 'W': cnt = 0

# print(self.value)
# only empty could be bump
for i in range(row_cnt):
for j in range(col_cnt):
if grid[i][j] != '0':
self.value[i][j] = 0
# print(self.value)

return max([max(v) for v in self.value])``````

• I like this one, not only because we have the same idea, but also it looks like this idea is the most "systematic" one.
However, the code is longer...

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