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


  • 3
    H

    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
    
    

Log in to reply
 

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