Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Bomb Enemy solution and explanation

MediumArrayDynamic ProgrammingMatrix3 min read52.8% acceptanceUpdated 23 Mar 2026Premium elsewhere, free here
Asked atGoogleUber
Practise Bomb Enemy
8:45
LeetCode 361. Bomb Enemy Explanation and Solutionhappygirlzt · 8:45 · 5K viewsWatch on YouTube
7 more videos on this problem
  1. LeetCode 361. Bomb Enemy Explanation and Solutionhappygirlzt · 8:45 · 5K views
  2. Bomb Enemy | Dynamic Programming | Python | LeetcodeLazyGenZ-Learners · 32:35 · 2K views
  3. LeetCode 361. Bomb Enemy 中文解释 Chinese Versionhappygirlzt · 8:15 · 1K views
  4. 361. Bomb Enemy - Week 3/5 Leetcode May ChallengeProgramming Live with Larry · 14:18 · 526 views
  5. Bomb Enemy, LeetCode Medium, C++H William Polenz · 1:08:18 · 157 views
  6. 361. Bomb EnemyDevBytes with Devpriya · 43:16 · 128 views
  7. leetcode bomb enemyTime World 🧭 · 0:27 · 26 views
  8. LeetCode 361: Bomb EnemyAlitaCode · 28:55 · 22 views

The problem

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

class Solution:
    def maxKilledEnemies(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        g = [[0] * n for _ in range(m)]
        for i in range(m):
            t = 0
            for j in range(n):
                if grid[i][j] == 'W':
                    t = 0
                elif grid[i][j] == 'E':
                    t += 1
                g[i][j] += t
            t = 0
            for j in range(n - 1, -1, -1):
                if grid[i][j] == 'W':
                    t = 0
                elif grid[i][j] == 'E':
                    t += 1
                g[i][j] += t
        for j in range(n):
            t = 0
            for i in range(m):
                if grid[i][j] == 'W':
                    t = 0
                elif grid[i][j] == 'E':
                    t += 1
                g[i][j] += t
            t = 0
            for i in range(m - 1, -1, -1):
                if grid[i][j] == 'W':
                    t = 0
                elif grid[i][j] == 'E':
                    t += 1
                g[i][j] += t
        return max(
            [g[i][j] for i in range(m) for j in range(n) if grid[i][j] == '0'],
            default=0,
        )
class Solution {
    public int maxKilledEnemies(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] g = new int[m][n];
        for (int i = 0; i < m; ++i) {
            int t = 0;
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'W') {
                    t = 0;
                } else if (grid[i][j] == 'E') {
                    ++t;
                }
                g[i][j] += t;
            }
            t = 0;
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 'W') {
                    t = 0;
                } else if (grid[i][j] == 'E') {
                    ++t;
                }
                g[i][j] += t;
            }
        }
        for (int j = 0; j < n; ++j) {
            int t = 0;
            for (int i = 0; i < m; ++i) {
                if (grid[i][j] == 'W') {
                    t = 0;
                } else if (grid[i][j] == 'E') {
                    ++t;
                }
                g[i][j] += t;
            }
            t = 0;
            for (int i = m - 1; i >= 0; --i) {
                if (grid[i][j] == 'W') {
                    t = 0;
                } else if (grid[i][j] == 'E') {
                    ++t;
                }
                g[i][j] += t;
            }
        }
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0') {
                    ans = Math.max(ans, g[i][j]);
                }
            }
        }
        return ans;
    }
}
class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> g(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            int t = 0;
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'W')
                    t = 0;
                else if (grid[i][j] == 'E')
                    ++t;
                g[i][j] += t;
            }
            t = 0;
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 'W')
                    t = 0;
                else if (grid[i][j] == 'E')
                    ++t;
                g[i][j] += t;
            }
        }
        for (int j = 0; j < n; ++j) {
            int t = 0;
            for (int i = 0; i < m; ++i) {
                if (grid[i][j] == 'W')
                    t = 0;
                else if (grid[i][j] == 'E')
                    ++t;
                g[i][j] += t;
            }
            t = 0;
            for (int i = m - 1; i >= 0; --i) {
                if (grid[i][j] == 'W')
                    t = 0;
                else if (grid[i][j] == 'E')
                    ++t;
                g[i][j] += t;
            }
        }
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0') ans = max(ans, g[i][j]);
            }
        }
        return ans;
    }
};
func maxKilledEnemies(grid [][]byte) int {
	m, n := len(grid), len(grid[0])
	g := make([][]int, m)
	for i := range g {
		g[i] = make([]int, n)
	}
	for i := 0; i < m; i++ {
		t := 0
		for j := 0; j < n; j++ {
			if grid[i][j] == 'W' {
				t = 0
			} else if grid[i][j] == 'E' {
				t++
			}
			g[i][j] += t
		}
		t = 0
		for j := n - 1; j >= 0; j-- {
			if grid[i][j] == 'W' {
				t = 0
			} else if grid[i][j] == 'E' {
				t++
			}
			g[i][j] += t
		}
	}
	for j := 0; j < n; j++ {
		t := 0
		for i := 0; i < m; i++ {
			if grid[i][j] == 'W' {
				t = 0
			} else if grid[i][j] == 'E' {
				t++
			}
			g[i][j] += t
		}
		t = 0
		for i := m - 1; i >= 0; i-- {
			if grid[i][j] == 'W' {
				t = 0
			} else if grid[i][j] == 'E' {
				t++
			}
			g[i][j] += t
		}
	}
	ans := 0
	for i, row := range grid {
		for j, v := range row {
			if v == '0' && ans < g[i][j] {
				ans = g[i][j]
			}
		}
	}
	return ans
}
Try this approach in the editor

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

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.

Comments

Next problem · similarMinimum Cost Homecoming of a Robot in a GridMedium
Now write it yourselfClose this page and solve Bomb Enemy in the editor, without looking.
Practise Bomb Enemy