Bomb Enemy - Video Solutions

Problem Overview: You are given a 2D grid containing walls (W), enemies (E), and empty cells (0). Placing a bomb in an empty cell eliminates every enemy in the same row and column until a wall blocks the blast. The task is to find the placement that kills the maximum number of enemies.

Approach 1: Brute Force Scan (O(m*n*(m+n)) time, O(1) space)

Iterate through every cell in the grid and consider placing the bomb only when the cell contains 0. From that position, scan left, right, up, and down until hitting a wall (W). Count every enemy encountered during these scans. Keep track of the maximum number of enemies killed across all valid placements. This approach is straightforward but inefficient because the same rows and columns are repeatedly scanned for many cells.

Approach 2: Row and Column Kill Caching (O(m*n) time, O(n) space)

Instead of rescanning the entire row and column for every empty cell, cache the number of enemies that can be killed in the current row segment and column segment. When you start a new row segment (either at column 0 or right after a wall), iterate forward until the next wall to count enemies and store it in rowHits. For columns, maintain an array colHits[j] representing the enemy count for the column segment starting at the current row. Recompute it only when the cell above is a wall. For each empty cell, the total kills are simply rowHits + colHits[j]. This avoids repeated scans and processes each grid cell at most a constant number of times.

The technique relies on recognizing independent row and column segments separated by walls. Once the enemy count for a segment is known, every empty cell inside that segment shares the same potential blast coverage. This transforms repeated directional scans into a linear pass across the grid.

Recommended for interviews: The row and column caching approach is the expected solution. The brute force version demonstrates understanding of the problem mechanics, but the optimized scan shows strong command of grid traversal and reuse of computed results. This pattern frequently appears in matrix traversal problems and optimization techniques related to arrays and light dynamic programming style state reuse.