LeetCode Solutions Blog

Bomb Enemy

Number: 361

Difficulty: Medium

Paid? Yes

Companies: Uber, Google

Problem Description

You are given an m x n grid where each cell is either a wall 'W', an enemy 'E', or an empty cell '0'. When you place a bomb in an empty cell, it kills all enemies in the same row and column until a wall is encountered. Return the maximum number of enemies you can kill with one bomb.

Key Insights

Instead of brute-forcing every empty cell and scanning its row and column each time, we can reuse counts.
Use a running count for the current row segment (reset when a wall is encountered).
Use an array to store column counts, recomputing the count only when the cell above is a wall.
This dynamic programming-like approach allows updating counts only when necessary, reducing redundant computations.

Space and Time Complexity

Time Complexity: O(m * n) Space Complexity: O(n) (for the column count array)

Solution

We scan the grid once. For each cell, if it is at the beginning of a row segment (first column or left neighbor is a wall), we re-calculate the number of enemies to the right until a wall is met. Similarly, for columns, if the cell is at the beginning of a column segment (first row or top neighbor is a wall), we re-calculate the number of enemies downward until a wall is met. For empty cells '0', we sum the row and column counts to see if this location yields a higher kill count. This method leverages caching to avoid repeated work and efficiently computes the result in one pass.

Code Solutions

# Definition for a grid bomb killer
class Solution:
    def maxKilledEnemies(self, grid: List[List[str]]) -> int:
        # Check for empty grid
        if not grid or not grid[0]:
            return 0
        
        m, n = len(grid), len(grid[0])
        max_enemies = 0  # To store the maximum number of enemies killed by one bomb
        row_hits = 0   # Running count of enemies in the current row segment
        col_hits = [0] * n  # Array for storing enemy count in each column segment
        
        # Traverse each cell in the grid
        for i in range(m):
            for j in range(n):
                # Recalculate row_hits if at the start of row segment or if previous cell is a wall
                if j == 0 or grid[i][j-1] == 'W':
                    row_hits = 0
                    k = j
                    # Count enemies until a wall is hit
                    while k < n and grid[i][k] != 'W':
                        if grid[i][k] == 'E':
                            row_hits += 1
                        k += 1
                # Recalculate col_hits[j] if at the start of column segment or if above cell is a wall
                if i == 0 or grid[i-1][j] == 'W':
                    col_hits[j] = 0
                    k = i
                    # Count enemies in the column until a wall is hit
                    while k < m and grid[k][j] != 'W':
                        if grid[k][j] == 'E':
                            col_hits[j] += 1
                        k += 1
                # If cell is empty, update maximum if current bomb gives a higher kill count
                if grid[i][j] == '0':
                    max_enemies = max(max_enemies, row_hits + col_hits[j])
        return max_enemies