Too strict time limit on Python?


  • 4

    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

  • 0

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


  • 0

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

    Btw, the "@" symbol works here?


  • 0

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


  • 0
    O

    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


  • 1

    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])
    

  • 0

    @Global-Moderators Do you think so?


  • 0

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


  • 0

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


  • 0

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


  • 0
    W

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


  • 0

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


  • 0
    W

    @LHearen

    I checked. So I posted my own question.


  • 0

    @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.


  • 0

    @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.


  • 0

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


  • 0
    Z

    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.


  • 0
    Z

    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]))]
            answer = 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':
                        answer = max(answer, row_count + col_count[j])
                        
            return answer
    

  • 0
    W

    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.


  • 0

    @zizhengwu said in Too strict time limit on Python?:

    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.


Log in to reply
 

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