Jobs

Interviews

Discussions

Bomb Enemy

Medium

Asked by:

28 views

Topics:

ArraysDynamic Programming

Given an m x n grid grid where each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb.

You can only place the bomb in an empty cell.

The bomb kills all the enemies in the same row and column from the planted bomb until it hits the wall since the wall is too strong to be destroyed.

Example 1:

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

Example 2:

Input: grid = [["W","E","W"],["E","0","E"],["W","E","W"]]
Output: 0

Example 3:

Input: grid = [["0","E","0"],["0","0","0"],["0","E","0"]]
Output: 2

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid[i][j] is either 'W', 'E', or '0'.

Try coding it in LeetCode

Bomb Enemy

Medium

Asked by:

28 views

Topics:

ArraysDynamic Programming

Given an m x n grid grid where each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb.

You can only place the bomb in an empty cell.

The bomb kills all the enemies in the same row and column from the planted bomb until it hits the wall since the wall is too strong to be destroyed.

Example 1:

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

Example 2:

Input: grid = [["W","E","W"],["E","0","E"],["W","E","W"]]
Output: 0

Example 3:

Input: grid = [["0","E","0"],["0","0","0"],["0","E","0"]]
Output: 2

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid[i][j] is either 'W', 'E', or '0'.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid, and what are the maximum possible dimensions?
Besides 'W', 'E', and '0', are there any other characters possible in the grid?
Can the grid be empty, or contain null values?
If there are no enemies to bomb, should I return 0?
Are we optimizing for space, or should I focus primarily on the time complexity?

Brute Force Solution

Approach

The brute force way to solve this problem involves checking every possible spot in the grid where an enemy could be bombed. For each of those spots, we count how many enemies would be hit if a bomb was placed there.

Here's how the algorithm would work step-by-step:

Go through each empty space on the grid, one at a time.
For each empty space, imagine placing a bomb there.
Check every location directly to the left of the bomb, until you hit a wall. Count how many enemies you see.
Do the same thing to the right, upwards, and downwards from the bomb, counting the enemies you would hit in each direction.
Add up all the enemies you counted in all four directions. This is the number of enemies the bomb in this spot would hit.
Write down the number of enemies that this bomb would hit for that location.
Repeat this entire process for every other empty space on the grid.
Once you've done this for every empty space, find the location that would hit the most enemies. That's your answer.

Code Implementation

def bomb_enemy_brute_force(grid):
    if not grid:
        return 0

    rows = len(grid)
    cols = len(grid[0])
    max_enemies_killed = 0

    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == '0':
                # Check only empty cells
                enemies_killed = count_enemies_killed(grid, row, col)
                max_enemies_killed = max(max_enemies_killed, enemies_killed)

    return max_enemies_killed

def count_enemies_killed(grid, bomb_row, bomb_col):
    rows = len(grid)
    cols = len(grid[0])
    total_enemies = 0

    # Check enemies to the left
    for column_to_left in range(bomb_col - 1, -1, -1):
        if grid[bomb_row][column_to_left] == 'W':
            break
        if grid[bomb_row][column_to_left] == 'E':
            total_enemies += 1

    # Check enemies to the right
    for column_to_right in range(bomb_col + 1, cols):
        if grid[bomb_row][column_to_right] == 'W':
            break
        if grid[bomb_row][column_to_right] == 'E':
            total_enemies += 1

    # Check enemies upwards
    for row_above in range(bomb_row - 1, -1, -1):
        if grid[row_above][bomb_col] == 'W':
            break
        if grid[row_above][bomb_col] == 'E':
            total_enemies += 1

    # Check enemies downwards
    for row_below in range(bomb_row + 1, rows):
        if grid[row_below][bomb_col] == 'W':
            break
        if grid[row_below][bomb_col] == 'E':
            total_enemies += 1

    return total_enemies

Big(O) Analysis

Time Complexity

O(m*n*(m+n)) – The algorithm iterates through each cell in the grid (m rows and n columns). For each empty cell, it checks in four directions (left, right, up, down) until hitting a wall or the edge of the grid. The worst-case scenario is when the grid is mostly empty, and each direction requires traversing the entire row (length n) or column (length m). Therefore, for each cell, the algorithm performs up to m+n operations. Consequently, the overall time complexity is O(m*n*(m+n)).

Space Complexity

O(1) – The provided brute force algorithm does not use any auxiliary data structures beyond a few integer variables. It iterates through the grid and for each empty cell calculates the number of enemies that would be hit, but it doesn't store these counts in a separate data structure; it only keeps track of the maximum enemies hit so far. Therefore, the space used remains constant regardless of the size of the input grid, making the space complexity O(1).

Optimal Solution

Approach

The key to efficiently solving this problem is to pre-calculate how many enemies each row and column can kill independently. Then, for each empty spot, we combine these pre-calculated values to find the maximum number of enemies we can bomb from that location.

Here's how the algorithm would work step-by-step:

First, calculate how many enemies each row can kill from left to right. Stop counting when you hit a wall, and reset when you start a new row.
Do the same thing, but this time from right to left. This allows you to know the total enemies killable from a row by adding the left-to-right and right-to-left values.
Next, calculate how many enemies each column can kill from top to bottom. Stop counting when you hit a wall, and reset when you start a new column.
Similarly, calculate the enemies killable in each column from bottom to top. Now you have enemy counts from both directions.
Now, go through each empty spot in the grid. For each spot, add the pre-calculated row kill count (left-to-right + right-to-left) and the column kill count (top-to-bottom + bottom-to-top) for that row and column.
Keep track of the maximum number of enemies you can kill from any empty spot.
The largest value found is the answer.

Code Implementation

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

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

    row_kills_left_to_right = [[0] * cols for _ in range(rows)]
    row_kills_right_to_left = [[0] * cols for _ in range(rows)]
    col_kills_top_to_bottom = [[0] * cols for _ in range(rows)]
    col_kills_bottom_to_top = [[0] * cols for _ in range(rows)]

    for i in range(rows):
        kill_count = 0
        for j in range(cols):
            if grid[i][j] == 'E':
                kill_count += 1
            elif grid[i][j] == 'W':
                kill_count = 0
            row_kills_left_to_right[i][j] = kill_count

        kill_count = 0
        for j in range(cols - 1, -1, -1):
            if grid[i][j] == 'E':
                kill_count += 1
            elif grid[i][j] == 'W':
                kill_count = 0
            row_kills_right_to_left[i][j] = kill_count

    for j in range(cols):
        kill_count = 0
        for i in range(rows):
            if grid[i][j] == 'E':
                kill_count += 1
            elif grid[i][j] == 'W':
                kill_count = 0
            col_kills_top_to_bottom[i][j] = kill_count

        kill_count = 0
        for i in range(rows - 1, -1, -1):
            if grid[i][j] == 'E':
                kill_count += 1
            elif grid[i][j] == 'W':
                kill_count = 0
            col_kills_bottom_to_top[i][j] = kill_count

    max_kills = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '0':
                # Summing all four directions to get total kills for this cell
                total_kills = row_kills_left_to_right[i][j] + \
                              row_kills_right_to_left[i][j] + \
                              col_kills_top_to_bottom[i][j] + \
                              col_kills_bottom_to_top[i][j]

                max_kills = max(max_kills, total_kills)

    return max_kills

Big(O) Analysis

Time Complexity

O(m*n) – Let m be the number of rows and n be the number of columns in the grid. Calculating enemies killable from left to right, right to left, top to bottom, and bottom to top each involves iterating through the entire grid once, taking O(m*n) time each. Iterating through each empty spot in the grid and summing the pre-calculated row and column kill counts also takes O(m*n) time. Therefore, the overall time complexity is O(m*n) + O(m*n) + O(m*n) + O(m*n) + O(m*n) = O(m*n).

Space Complexity

O(MN) – The algorithm uses four 2D arrays (or matrices) of the same dimensions as the input grid to store the pre-calculated enemy counts for each row and column from left to right, right to left, top to bottom, and bottom to top. Where M is the number of rows and N is the number of columns in the grid, each of these arrays will have M * N integers. Therefore, the total auxiliary space used by these four arrays is proportional to M * N, leading to a space complexity of O(MN).

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 immediately as there are no bombs or enemies to consider.
Grid with only one row or one column	The solution should still correctly calculate the maximum enemies killed along that single row or column.
Grid filled entirely with walls ('W')	Return 0, as no bombs can be placed.
Grid filled entirely with enemies ('E')	If there is any open space calculate bomb placement for any open cell.
Grid filled entirely with empty cells ('0')	Return 0, as placing bombs will not kill any enemies.
Large grid (scaling performance)	Optimize the algorithm to avoid redundant calculations by pre-computing row and column enemy counts.
Grid with no valid bomb placement positions ('0')	If there are no '0' cells, return 0, as no bombs can be placed.
Integer overflow potential when counting enemies in very large rows/columns	Use a data type with larger capacity (e.g., long) to store enemy counts.

Null or empty grid

How to Handle:

Return 0 immediately as there are no bombs or enemies to consider.

Grid with only one row or one column

How to Handle:

The solution should still correctly calculate the maximum enemies killed along that single row or column.

Grid filled entirely with walls ('W')

How to Handle:

Return 0, as no bombs can be placed.

Grid filled entirely with enemies ('E')

How to Handle:

If there is any open space calculate bomb placement for any open cell.

Grid filled entirely with empty cells ('0')

How to Handle:

Return 0, as placing bombs will not kill any enemies.

Large grid (scaling performance)

How to Handle:

Optimize the algorithm to avoid redundant calculations by pre-computing row and column enemy counts.

Grid with no valid bomb placement positions ('0')

How to Handle:

If there are no '0' cells, return 0, as no bombs can be placed.

Integer overflow potential when counting enemies in very large rows/columns

How to Handle:

Use a data type with larger capacity (e.g., long) to store enemy counts.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid, and what are the maximum possible dimensions?
Besides 'W', 'E', and '0', are there any other characters possible in the grid?
Can the grid be empty, or contain null values?
If there are no enemies to bomb, should I return 0?
Are we optimizing for space, or should I focus primarily on the time complexity?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Go through each empty space on the grid, one at a time.
For each empty space, imagine placing a bomb there.
Check every location directly to the left of the bomb, until you hit a wall. Count how many enemies you see.
Do the same thing to the right, upwards, and downwards from the bomb, counting the enemies you would hit in each direction.
Add up all the enemies you counted in all four directions. This is the number of enemies the bomb in this spot would hit.
Write down the number of enemies that this bomb would hit for that location.
Repeat this entire process for every other empty space on the grid.
Once you've done this for every empty space, find the location that would hit the most enemies. That's your answer.

Code Implementation

def bomb_enemy_brute_force(grid):
    if not grid:
        return 0

    rows = len(grid)
    cols = len(grid[0])
    max_enemies_killed = 0

    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == '0':
                # Check only empty cells
                enemies_killed = count_enemies_killed(grid, row, col)
                max_enemies_killed = max(max_enemies_killed, enemies_killed)

    return max_enemies_killed

def count_enemies_killed(grid, bomb_row, bomb_col):
    rows = len(grid)
    cols = len(grid[0])
    total_enemies = 0

    # Check enemies to the left
    for column_to_left in range(bomb_col - 1, -1, -1):
        if grid[bomb_row][column_to_left] == 'W':
            break
        if grid[bomb_row][column_to_left] == 'E':
            total_enemies += 1

    # Check enemies to the right
    for column_to_right in range(bomb_col + 1, cols):
        if grid[bomb_row][column_to_right] == 'W':
            break
        if grid[bomb_row][column_to_right] == 'E':
            total_enemies += 1

    # Check enemies upwards
    for row_above in range(bomb_row - 1, -1, -1):
        if grid[row_above][bomb_col] == 'W':
            break
        if grid[row_above][bomb_col] == 'E':
            total_enemies += 1

    # Check enemies downwards
    for row_below in range(bomb_row + 1, rows):
        if grid[row_below][bomb_col] == 'W':
            break
        if grid[row_below][bomb_col] == 'E':
            total_enemies += 1

    return total_enemies

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, calculate how many enemies each row can kill from left to right. Stop counting when you hit a wall, and reset when you start a new row.
Do the same thing, but this time from right to left. This allows you to know the total enemies killable from a row by adding the left-to-right and right-to-left values.
Next, calculate how many enemies each column can kill from top to bottom. Stop counting when you hit a wall, and reset when you start a new column.
Similarly, calculate the enemies killable in each column from bottom to top. Now you have enemy counts from both directions.
Now, go through each empty spot in the grid. For each spot, add the pre-calculated row kill count (left-to-right + right-to-left) and the column kill count (top-to-bottom + bottom-to-top) for that row and column.
Keep track of the maximum number of enemies you can kill from any empty spot.
The largest value found is the answer.

Code Implementation

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

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

    row_kills_left_to_right = [[0] * cols for _ in range(rows)]
    row_kills_right_to_left = [[0] * cols for _ in range(rows)]
    col_kills_top_to_bottom = [[0] * cols for _ in range(rows)]
    col_kills_bottom_to_top = [[0] * cols for _ in range(rows)]

    for i in range(rows):
        kill_count = 0
        for j in range(cols):
            if grid[i][j] == 'E':
                kill_count += 1
            elif grid[i][j] == 'W':
                kill_count = 0
            row_kills_left_to_right[i][j] = kill_count

        kill_count = 0
        for j in range(cols - 1, -1, -1):
            if grid[i][j] == 'E':
                kill_count += 1
            elif grid[i][j] == 'W':
                kill_count = 0
            row_kills_right_to_left[i][j] = kill_count

    for j in range(cols):
        kill_count = 0
        for i in range(rows):
            if grid[i][j] == 'E':
                kill_count += 1
            elif grid[i][j] == 'W':
                kill_count = 0
            col_kills_top_to_bottom[i][j] = kill_count

        kill_count = 0
        for i in range(rows - 1, -1, -1):
            if grid[i][j] == 'E':
                kill_count += 1
            elif grid[i][j] == 'W':
                kill_count = 0
            col_kills_bottom_to_top[i][j] = kill_count

    max_kills = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '0':
                # Summing all four directions to get total kills for this cell
                total_kills = row_kills_left_to_right[i][j] + \
                              row_kills_right_to_left[i][j] + \
                              col_kills_top_to_bottom[i][j] + \
                              col_kills_bottom_to_top[i][j]

                max_kills = max(max_kills, total_kills)

    return max_kills

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 immediately as there are no bombs or enemies to consider.
Grid with only one row or one column	The solution should still correctly calculate the maximum enemies killed along that single row or column.
Grid filled entirely with walls ('W')	Return 0, as no bombs can be placed.
Grid filled entirely with enemies ('E')	If there is any open space calculate bomb placement for any open cell.
Grid filled entirely with empty cells ('0')	Return 0, as placing bombs will not kill any enemies.
Large grid (scaling performance)	Optimize the algorithm to avoid redundant calculations by pre-computing row and column enemy counts.
Grid with no valid bomb placement positions ('0')	If there are no '0' cells, return 0, as no bombs can be placed.
Integer overflow potential when counting enemies in very large rows/columns	Use a data type with larger capacity (e.g., long) to store enemy counts.

Null or empty grid

How to Handle:

Return 0 immediately as there are no bombs or enemies to consider.

Grid with only one row or one column

How to Handle:

The solution should still correctly calculate the maximum enemies killed along that single row or column.

Grid filled entirely with walls ('W')

How to Handle:

Return 0, as no bombs can be placed.

Grid filled entirely with enemies ('E')

How to Handle:

If there is any open space calculate bomb placement for any open cell.

Grid filled entirely with empty cells ('0')

How to Handle:

Return 0, as placing bombs will not kill any enemies.

Large grid (scaling performance)

How to Handle:

Optimize the algorithm to avoid redundant calculations by pre-computing row and column enemy counts.

Grid with no valid bomb placement positions ('0')

How to Handle:

If there are no '0' cells, return 0, as no bombs can be placed.

Integer overflow potential when counting enemies in very large rows/columns

How to Handle:

Use a data type with larger capacity (e.g., long) to store enemy counts.