Bomb Enemy

Naive Solution

A brute-force solution would involve iterating through each empty cell in the grid and then, for each cell, scanning in all four directions (up, down, left, right) to count the number of enemies that would be killed if a bomb were placed at that cell. The maximum number of enemies killed is then tracked. This approach is simple to understand but inefficient.

def max_killed_enemies_brute_force(grid):
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    max_enemies = 0

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '0':
                enemies = 0

                # Check up
                for k in range(i - 1, -1, -1):
                    if grid[k][j] == 'E':
                        enemies += 1
                    elif grid[k][j] == 'W':
                        break

                # Check down
                for k in range(i + 1, rows):
                    if grid[k][j] == 'E':
                        enemies += 1
                    elif grid[k][j] == 'W':
                        break

                # Check left
                for k in range(j - 1, -1, -1):
                    if grid[i][k] == 'E':
                        enemies += 1
                    elif grid[i][k] == 'W':
                        break

                # Check right
                for k in range(j + 1, cols):
                    if grid[i][k] == 'E':
                        enemies += 1
                    elif grid[i][k] == 'W':
                        break

                max_enemies = max(max_enemies, enemies)

    return max_enemies

Big O Runtime

O(m * n * (m + n)), where m is the number of rows and n is the number of columns. This is because for each empty cell (O(m * n)), we potentially scan the entire row and column (O(m + n)).

Big O Space Usage

O(1) - Constant space is used.

Optimal Solution

The optimal solution utilizes dynamic programming to precompute the number of enemies that can be killed from each cell in each direction. Four 2D arrays can be used to store the number of enemies to the left, right, up, and down from each cell. By precomputing these values, we can calculate the number of enemies killed by placing a bomb at a particular empty cell in O(1) time.

def max_killed_enemies(grid):
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    left = [[0] * cols for _ in range(rows)]
    right = [[0] * cols for _ in range(rows)]
    up = [[0] * cols for _ in range(rows)]
    down = [[0] * cols for _ in range(rows)]

    # Calculate left
    for i in range(rows):
        count = 0
        for j in range(cols):
            if grid[i][j] == 'E':
                count += 1
            elif grid[i][j] == 'W':
                count = 0
            left[i][j] = count

    # Calculate right
    for i in range(rows):
        count = 0
        for j in range(cols - 1, -1, -1):
            if grid[i][j] == 'E':
                count += 1
            elif grid[i][j] == 'W':
                count = 0
            right[i][j] = count

    # Calculate up
    for j in range(cols):
        count = 0
        for i in range(rows):
            if grid[i][j] == 'E':
                count += 1
            elif grid[i][j] == 'W':
                count = 0
            up[i][j] = count

    # Calculate down
    for j in range(cols):
        count = 0
        for i in range(rows - 1, -1, -1):
            if grid[i][j] == 'E':
                count += 1
            elif grid[i][j] == 'W':
                count = 0
            down[i][j] = count

    max_enemies = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '0':
                max_enemies = max(max_enemies, left[i][j] + right[i][j] + up[i][j] + down[i][j])

    return max_enemies

Big O Runtime

O(m * n), where m is the number of rows and n is the number of columns. The four arrays are populated by iterating through all the elements in the grid. Then, the grid is traversed once more to determine the maximum number of enemies killed for each '0' cell.

Big O Space Usage

O(m * n), where m is the number of rows and n is the number of columns. Four 2D arrays of this size are created to store the left, right, up, and down counts.

Edge Cases

• Empty grid: If the input grid is empty or has no columns, the function should return 0.
• Grid with no empty cells: If the grid does not contain any empty cells ('0'), the function should return 0, as no bomb can be placed.
• Grid with no enemies: If the grid does not contain any enemies ('E'), the function should return 0, as placing a bomb will not kill any enemies.
• Grid with only walls: A grid consisting entirely of walls should return 0, since there are no places to put bombs.
• Grid with walls blocking all enemies: If walls completely isolate all enemies from any empty cell, the result is 0.