# Too strict time limit on Python?

• Same idea as @StefanPochmann posted but cannot get accepted. I think the last test case is too large for Python to pass it.

``````class Solution(object):
def maxKilledEnemies(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if grid is None or len(grid) == 0 or len(grid[0]) == 0:
return 0

dp = [[[0, 0] for j in range(len(grid[0]))] for i in range(len(grid))]
for i in xrange(0, len(grid)):
for j in xrange(0, len(grid[0])):
if grid[i][j] == "E":
dp[i][j] = [dp[i - 1][j][0] + 1,  + dp[i][j - 1][1] + 1]
elif grid[i][j] == "0":
dp[i][j] = [dp[i - 1][j][0], dp[i][j - 1][1]]

maxKilled = 0
for i in reversed(xrange(0, len(grid))):
for j in reversed(xrange(0, len(grid[0]))):
if j != len(grid[0]) - 1:
if grid[i][j + 1] != "W":
dp[i][j][1] = dp[i][j + 1][1]
if i != len(grid) - 1:
if grid[i + 1][j] != "W":
dp[i][j][0] = dp[i + 1][j][0]
if grid[i][j] == "0":
curKilled = dp[i][j][0] + dp[i][j][1]
if curKilled > maxKilled:
maxKilled = curKilled

return maxKilled``````

• My Python translation of my C++ solution gets accepted in around 1830ms and my first Python solution gets accepted in around 1040ms.

• Maybe I need to optimize the implementation but the idea should be acceptable due to obvious O(mn) complexity.

Btw, the "@" symbol works here?

• No, "@" doesn't work here, I just saw this because I spend too much time here :-D

• Yeah, I have the same problem with you. The code has O(mn) time complexity but got TLE. I think for python the time limit might be too strict

• Me too folks, I don't think this code is that bad...

``````class Solution(object):
def maxKilledEnemies(self, grid):
m, n = len(grid), len(grid[0]) if grid else 0
up, dw, lt, rt = tuple(collections.defaultdict(int) for _ in range(4))
zeroes = set()
for r in range(m):
for c in range(n):
x, y = m - r - 1, n - c - 1
E, W = (grid[r][c] == 'E'), (grid[r][c] != 'W')
G, K = (grid[x][y] == 'E'), (grid[x][y] != 'W')
up[r,c] = (up[r-1,c] + E) * W
lt[r,c] = (lt[r,c-1] + E) * W
dw[x,y] = (dw[x+1,y] + G) * K
rt[x,y] = (rt[x,y+1] + G) * K
if grid[r][c] == "0": zeroes.add((r, c))
return max([up[r,c] + dw[r,c] + lt[r,c] + rt[r,c] for r, c in zeroes] or [0])
``````

• @Global-Moderators Do you think so?

• @jedihy the @ definitely works here, that's what brought me here. But what's the problem exactly here? You mean the test case?

• @LHearen Could you add one more second to the TLE limit for Python?

• @jedihy Not just python, C++ also... so optimise your solution is the practical way here.

• @LHearen Then what is the best running time of all submitted python code? Or anyone can think of a solution better than o(mn)?

• @hao88 Stefan just posted it here, you haven't checked it?

• @LHearen

I checked. So I posted my own question.

• @hao88 So what do you mean here? There are lots of submissions in python, but yours are not one of them; then there must be wrong about your code or `if you have any doubt about the system test cases`, please present some specific issues. So many thanks, man.

• @LHearen I also got accepted but I used some built-in functions like split and count, which are much faster than count them by my own code because these are done by C library.

• @jedihy So there are always ways to get it done right.

• My O(mn) time and O(mn) space algorithm gets TLE as well. It runs ~500ms on the last big test case while an accepted algorithm posted by StefanPochmann is ~400ms.

I agree that the time limit is too strict and it turns out that you have to optimize space. It turns out if you are doing something like `count = [[0]*len(grid[0]) for i in range(0, len(grid))]` you will get TLE with python while fine in other languages.

• A naïve rewrite of StefanPochmann's algorithm get's TLE as well. Please lessen the constraint:

``````# TLE
class Solution(object):
def maxKilledEnemies(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if len(grid) == 0:
return 0

row_count = 0
col_count = [0 for i in range(0, len(grid[0]))]

for i in range(0, len(grid)):
for j in range(0, len(grid[0])):
if grid[i][j] == 'W':
continue
if j == 0 or grid[i][j-1] == 'W':
# update row
row_count = 0
fast = j
while(fast < len(grid[0])):
if grid[i][fast] == 'E':
row_count += 1
elif grid[i][fast] == 'W':
break
fast += 1
if i == 0 or grid[i-1][j] == 'W':
# update column
col_count[j] = 0
fast = i
while(fast < len(grid)):
if grid[fast][j] == 'E':
col_count[j] += 1
elif grid[fast][j] == 'W':
break
fast += 1
if grid[i][j] == '0':

``````

• One question about the TLE in leetcode: is the time limit based on the real interview requirement or it's just set by leetcode operators to help us practice? I guess it's the latter one.

• A naïve rewrite of StefanPochmann's algorithm get's TLE as well.

After replacing your C-ish `for i in range(0, len(grid))` with the pythonic `for i, row in enumerate(grid)` and then using `row` instead of `grid[i]` everywhere, I submitted it three times and it got accepted all three times.

Not arguing against a higher time limit, though. Just showing a straight-forward way to get that one under the current limit.

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