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


  • 0
    M

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

  • 0
    M

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


Log in to reply
 

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