Skip to main content
Talentd

Bomb Enemy - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDynamic ProgrammingMatrix5 min readAsked at: Uber, Google
Practice this problem

Problem Statement

Given an m x n matrix grid where each cell is either a wall 'W', an enemy 'E' or empty '0', 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 point until it hits the wall since it 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","W","W"],["0","0","0"],["E","E","E"]]
Output: 1

 

Constraints:

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

Approach Overview

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.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Directional ScanO(m*n*(m+n))O(1)Good for understanding the problem mechanics or very small grids
Row and Column Kill Caching (Optimized Scan)O(m*n)O(n)Optimal approach for interviews and large grids

Video Solution

LeetCode 361. Bomb Enemy Explanation and Solution • happygirlzt • 5,089 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Bomb Enemy easy or hard?
Bomb Enemy is generally classified as a medium difficulty problem. The brute force idea is simple, but identifying how to reuse row and column counts efficiently requires careful reasoning about grid segments and walls.
Bomb Enemy Python/Java solution
Python and Java implementations follow the same idea: iterate through the grid, recompute row enemy counts when entering a new row segment, and maintain a column hits array for vertical segments. Each empty cell calculates its result using cached values, keeping the algorithm O(m*n).
How to solve Bomb Enemy in O(n)?
Treat rows and columns as segments separated by walls. When starting a new row segment, count enemies to the right until a wall and store the result. Maintain a column array that tracks enemy counts downward until a wall appears. For each empty cell, combine the cached row and column counts to compute the total kills in constant time.
What is the best approach for Bomb Enemy?
The optimal solution scans the grid once while caching enemy counts for row and column segments separated by walls. When entering a new segment, the algorithm counts enemies until the next wall and reuses that value for all cells in the segment. This reduces repeated scanning and achieves O(m*n) time complexity with O(n) extra space.
Is Bomb Enemy asked at Google/Amazon/Meta?
Bomb Enemy is a classic grid optimization problem often discussed in interview prep for companies like Google and Amazon. It tests matrix traversal, reuse of computed state, and optimization from brute force to linear scanning.
What data structure is used in Bomb Enemy?
The solution mainly uses arrays and a 2D grid traversal. A single integer for row hits and an auxiliary array for column hits store enemy counts for each column segment. The grid itself is processed like a matrix with simple counters rather than complex data structures.
What is the time complexity of Bomb Enemy?
The optimized approach runs in O(m*n) time where m is the number of rows and n is the number of columns. Each grid cell is processed a constant number of times while row and column enemy counts are reused. The brute force method is slower at O(m*n*(m+n)) because it scans four directions for every empty cell.

Ready to solve this problem?

Practice Bomb Enemy with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Unguarded Cells in the Grid

Next

Maximum Trailing Zeros in a Cornered Path