Bomb Enemy - Practice Coding Problems

Bomb Enemy - Problem

You are given an m x n matrix grid where each cell contains one of the following:

'W' - represents a wall
'E' - represents an enemy
'0' - represents an empty cell

You want to place a bomb in an empty cell that will kill the maximum number of enemies. The bomb kills all enemies in the same row and column from the bomb's position until it hits a wall, since walls are too strong to be destroyed.

Return the maximum number of enemies you can kill with one bomb.

Input & Output

Example 1 — Basic Grid

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

› Output: 3

💡 Note: Placing bomb at (1,1) kills 3 enemies: one to the left in same row, one above and one below in same column

Example 2 — Wall Blocking

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

› Output: 1

💡 Note: Wall blocks the bomb explosion, so maximum enemies killed is 1

Example 3 — No Empty Cells

$ Input: grid = [["W","E"],["E","W"]]

› Output: 0

💡 Note: No empty cells available to place a bomb, so return 0

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Matrix with walls (W), enemies (E), and empty cells (0)

Bomb Explosion

Bomb kills enemies in same row and column until hitting walls

Maximum Result

Return the highest enemy count possible

Key Takeaway

🎯 Key Insight: Walls create independent segments - pre-compute enemy counts to avoid redundant calculations

Asked in

G Google 45 F Facebook 38 A Amazon 32

The key insight is that walls divide the grid into independent row and column segments. The optimal approach uses dynamic programming to pre-compute enemy counts for each segment, avoiding redundant calculations. Time: O(mn), Space: O(mn).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(m²n²)	O(1)	Check every empty cell and count enemies in all four directions
Dynamic Programming	O(mn)	O(mn)	Pre-compute enemy counts for each row and column segment separated by walls

Brute Force — Algorithm Steps

Iterate through each cell in the grid
For empty cells, expand in 4 directions counting enemies
Stop counting when hitting a wall
Track maximum enemies killed

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Empty Cell

Locate a cell with '0'

Count in 4 Directions

Expand left, right, up, down counting enemies

Track Maximum

Keep track of highest enemy count found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char** grid, int gridSize, int* gridColSize) {
    if (gridSize == 0 || gridColSize[0] == 0) return 0;
    
    int m = gridSize, n = gridColSize[0];
    int maxEnemies = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '0') {
                int enemies = 0;
                
                // Count enemies to the left
                for (int k = j - 1; k >= 0; k--) {
                    if (grid[i][k] == 'W') break;
                    if (grid[i][k] == 'E') enemies++;
                }
                
                // Count enemies to the right
                for (int k = j + 1; k < n; k++) {
                    if (grid[i][k] == 'W') break;
                    if (grid[i][k] == 'E') enemies++;
                }
                
                // Count enemies upward
                for (int k = i - 1; k >= 0; k--) {
                    if (grid[k][j] == 'W') break;
                    if (grid[k][j] == 'E') enemies++;
                }
                
                // Count enemies downward
                for (int k = i + 1; k < m; k++) {
                    if (grid[k][j] == 'W') break;
                    if (grid[k][j] == 'E') enemies++;
                }
                
                if (enemies > maxEnemies) {
                    maxEnemies = enemies;
                }
            }
        }
    }
    
    return maxEnemies;
}

int main() {
    char buffer[10000];
    fgets(buffer, sizeof(buffer), stdin);
    
    // Simple parsing for the test format
    char** grid = malloc(100 * sizeof(char*));
    int* gridColSize = malloc(100 * sizeof(int));
    int gridSize = 0;
    
    // Parse manually - simplified for this problem
    // For demonstration, assume 3x4 grid from example
    gridSize = 3;
    gridColSize[0] = gridColSize[1] = gridColSize[2] = 4;
    
    for (int i = 0; i < gridSize; i++) {
        grid[i] = malloc(4 * sizeof(char));
    }
    
    // Example hardcoded for demonstration
    strcpy(grid[0], "0E00");
    strcpy(grid[1], "E0WE");
    strcpy(grid[2], "0E00");
    
    int result = solution(grid, gridSize, gridColSize);
    printf("%d\n", result);
    
    for (int i = 0; i < gridSize; i++) {
        free(grid[i]);
    }
    free(grid);
    free(gridColSize);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n²)

For each of m×n cells, we potentially scan entire row and column (m+n operations)

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track maximum and current counts

✓ Linear Space

32.5K Views

Medium Frequency

~25 min Avg. Time

876 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler