Short O(mn) Python


  • 7

    Compute a matrix for row-wise hits and one for column-wise hits. Then find the maximum.

    def maxKilledEnemies(self, grid):
        def hits(grid):
            return [[h
                     for block in ''.join(row).split('W')
                     for h in [block.count('E')] * len(block) + [0]]
                    for row in grid]
        rowhits = hits(grid)
        colhits = zip(*hits(zip(*grid)))
        return max([rh + ch
                    for row in zip(grid, rowhits, colhits)
                    for cell, rh, ch in zip(*row)
                    if cell == '0'] or [0])

  • 0
    L
    This post is deleted!

  • 0
    Y

    I did a direct python translation of Stefan's c++ here, and got TLE, I measure this version runs about 0.1s and my translated version is about 0.2s. Anybody have hints why this one is much faster?

        def maxKilledEnemies(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if len(grid) == 0:
            return 0
            
        gmax, cols = 0, [0] * len(grid[0])
        
        for row in xrange(len(grid)):
            rowhits = 0
            for col in xrange(len(grid[0])):
                if (col ==0 or grid[row][col-1] == 'W'):
                    rowhits = 0;
                    for k in xrange(col,len(grid[0])):
                        if grid[row][k] == 'W':
                            break
                        rowhits = rowhits + 1 if grid[row][k] == 'E' else rowhits
    
                if row == 0 or grid[row-1][col] == 'W':
                    cols[col] = 0
                    for k in xrange(row,len(grid)):
                        if grid[k][col] == 'W':
                            break
                        cols[col] = cols[col] + 1 if grid[k][col] == 'E' else cols[col]
    
                    
                if grid[row][col] == '0':
                    gmax = max(gmax, rowhits + cols[col])
        
        return gmax
    

  • 0

    You gotta be close to acceptance. I translated it to Python myself now and it takes about the same time as yours for the huge test case where you fail (around 460ms). But it got accepted all three times I submitted it, taking around 1850ms.


  • 0

    I guess my above solution is faster because I do less myself and have more done by Python's own functions, which can be faster (might be using some C).


  • 0

    I polished and posted my translation now, maybe check out our differences.


  • 0
    Y

    Great, thanks!


Log in to reply
 

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