# Python Brute Force O((mn)*(m+n)) to DP O(mn)

• The brute force solution is very intuitive.. just count 'E's in rows and cols for each 0 in the matrix and return the maximum. This takes O((mn)*(m+n)) as you have to traverse up, down, left, and right for every i,j.

We can optimize on this by doing 4 passes and adding the number of E's seen so far, and reset if we see a 'W'.
From left to right then right to left for E's seen in each row. And then from up to down and down to up for each E seen so far in column.

Total time -> O(4*mn) --> O(mn)

``````class Solution(object):
def maxKilledEnemies(self, grid):
if len(grid) == 0:
return 0
max_hits = 0
nums = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]

#From Left
for i in range(len(grid)):
row_hits = 0
for j in range(len(grid[0])):
if grid[i][j] == 'E':
row_hits += 1
elif grid[i][j] == 'W':
row_hits = 0
else:
nums[i][j] = row_hits

#From Right
for i in range(len(grid)):
row_hits = 0
for j in range(len(grid[0])-1, -1, -1):
if grid[i][j] == 'W':
row_hits = 0
elif grid[i][j] == 'E':
row_hits +=1
else:
nums[i][j] += row_hits

for i in range(len(nums[0])):
col_hits = 0
for col in range(len(nums)):
if grid[col][i] == 'E':
col_hits += 1
elif grid[col][i] == 'W':
col_hits = 0
else:
nums[col][i] += col_hits

for i in range(len(nums[0])):
col_hits = 0
for col in range(len(nums)-1, -1, -1):
if grid[col][i] == 'E':
col_hits +=1
elif grid[col][i] == 'W':
col_hits = 0
else:
nums[col][i] += col_hits
max_hits = max(max_hits, nums[col][i])

return max_hits

``````

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