Python solution with detailed explanation


  • 3
    G

    Solution

    Bomb Enemy https://leetcode.com/problems/bomb-enemy/

    Brute Force Solution

    • There is an obvious brute force solution where we start from each 0 and scan the row and column. We need to be careful in doing this count - move right and then move left. Similarly move up and move down. Complexity of this solution is O(mn(m+n)).
    class Solution(object):
        def scan_vertical(self, i,j,grid, direction):
            N, M = len(grid), len(grid[0])
            cnt = 0
            while 0<=i<N and grid[i][j] != "W":
                cnt = cnt + 1 if grid[i][j] == "E" else cnt
                i = i + 1 if direction == "D" else i-1
            return cnt
        
        def scan_horizontal(self, i,j,grid, direction):
            N, M = len(grid), len(grid[0])
            cnt = 0
            while 0<=j<M and grid[i][j] != "W":
                cnt = cnt + 1 if grid[i][j] == "E" else cnt
                j = j + 1 if direction == "R" else j-1
            return cnt
        
        def maxKilledEnemies(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            if grid == []:
                return 0
            N, M = len(grid), len(grid[0])
            max_bomb_enemy = 0
            for i in range(N):
                for j in range(M):
                    if grid[i][j] == "0":
                        c = self.scan_vertical(i,j,grid, "D") + self.scan_vertical(i,j,grid, "U")
                        c = c + self.scan_horizontal(i,j,grid, "L") + self.scan_horizontal(i,j,grid, "R")
                        max_bomb_enemy = max(max_bomb_enemy, c)
            return max_bomb_enemy
    

    Optimized Solution

    • We can perform an optimization: we can create a 2D array. For row wise direction, we can simply count the number of enemies between two walls, and then each value between 2 walls will be increased by the count of the enemies. A similar thing can be done column wise.
    • Check this image: https://goo.gl/photos/s8cS5p3zLjawXJkM8. The code simply implements this.
    class Solution(object):
        def process_left_right(self, i, grid, value):
            cnt, N, M = 0, len(grid), len(grid[0])
            for j in range(M):
                if grid[i][j] == "W":
                    cnt  = 0
                elif grid[i][j] == "E":
                    cnt += 1
                else:
                    value[i][j] += cnt
            return
        
        def process_right_left(self, i, grid, value):
            cnt, N, M = 0, len(grid), len(grid[0])
            for j in range(M-1, -1, -1):
                if grid[i][j] == "W":
                    cnt  = 0
                elif grid[i][j] == "E":
                    cnt += 1
                else:
                    value[i][j] += cnt
            return
        
        def process_up_down(self, j, grid, value):
            cnt, N, M = 0, len(grid), len(grid[0])        
            for i in range(N):
                if grid[i][j] == "W":
                    cnt  = 0
                elif grid[i][j] == "E":
                    cnt += 1
                else:
                    value[i][j] += cnt 
            return
        
        def process_down_up(self, j, grid, value):
            cnt, N, M = 0, len(grid), len(grid[0])        
            for i in range(N-1, -1, -1):
                if grid[i][j] == "W":
                    cnt  = 0
                elif grid[i][j] == "E":
                    cnt += 1
                else:
                    value[i][j] += cnt
            return
        
        def maxKilledEnemies(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            if grid == []:
                return 0
            N, M = len(grid), len(grid[0])
            value = [[0]*M for _ in range(N)]
            self.max_bomb_enemy = 0
            for i in range(N):
                self.process_left_right(i, grid, value)
                self.process_right_left(i, grid, value)
            for j in range(M):
                self.process_up_down(j, grid, value)
                self.process_down_up(j, grid, value)
            for i in range(N):
                if value[i]:
                    self.max_bomb_enemy = max(self.max_bomb_enemy, max(value[i]))
            return self.max_bomb_enemy
    

Log in to reply
 

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