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.

Description Solution Video 8:45

361. Bomb Enemy

Medium52.8% acceptance2 companiesPremium elsewhere, free here

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'.

Asked at 2 companies

Google Uber

Topics

8:45

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

361. Bomb Enemy

Asked at 2 companies

Topics

Similar problems