Bomb Enemy

Bomb Enemy

What is this problem about?

You are given a 2D grid representing a field with enemies ('E'), walls ('W'), and empty spaces ('0'). You can place a single bomb in any empty space. When the bomb explodes, it kills all enemies in its row and column until the blast hits a wall. The goal is to find the maximum number of enemies you can kill with one bomb.

Why is this asked in interviews?

This is a popular matrix-based Dynamic Programming problem at Google. It tests your ability to optimize redundant calculations. The naive approach (calculating the kill count for every empty cell by scanning its entire row and column) is $O(M imes N imes (M+N))$. A better approach uses DP to cache the counts, reducing the complexity to $O(M imes N)$.

Algorithmic pattern used

This problem uses Dynamic Programming on a Matrix. The trick is to only recompute the "row kill count" when you start a new row or hit a wall, and to keep an array of "column kill counts" that you update when you start a new column or hit a wall. For each cell, the total kills is row_count + col_counts[j].

Example explanation

Grid: 0 E 0 E W E 0 E 0

1. At (0,0): Bomb here kills 2 enemies (one in row, one in column).
2. At (1,1): It's a wall. Cannot place.
3. At (2,2): Bomb here kills 2 enemies.
4. If you place it at (1,0): Row count is blocked by the wall at (1,1). Only kills enemies at (0,0) and (2,0). The maximum kills in this grid would be 2.

Common mistakes candidates make

The most common mistake is the inefficient $O(N^3)$ approach. Another is getting the wall-blocking logic wrong—forgetting that a wall at (1,1) stops a bomb at (1,0) from hitting an enemy at (1,2). Finally, some candidates struggle with managing the state of the "current" row and column counts during a single pass.

Interview preparation tip

When working with grid problems that involve "range" effects (like bombs or vision), look for ways to cache values that are shared across adjacent cells. If you can't solve it in one pass, try precomputing four DP tables: one for each direction (up, down, left, right).