LeetCode 361: Bomb Enemy Solution in Python – A Step-by-Step Guide

What Is LeetCode 361: Bomb Enemy?

LeetCode 361: Bomb Enemy gives you a 2D grid with three types of cells: 'W' (wall), 'E' (enemy), and '0' (empty). You can place a bomb in an empty cell, and it will destroy all enemies in its row and column until hitting a wall. Your task is to find the maximum number of enemies you can eliminate with one bomb. It’s a grid-based optimization problem with a strategic twist!

Problem Statement

• Input:
• grid: 2D list of characters ('0', 'E', 'W').
• Output: Integer - Maximum number of enemies that can be killed by one bomb.
• Rules:
• Bomb can only be placed in an empty cell ('0').
• Explosion travels up, down, left, right, stopping at walls ('W').
• Count enemies ('E') hit in all four directions.

Constraints

• 0 <= m, n <= 300 (m rows, n columns)
• Grid contains only '0', 'E', 'W'.

Examples

• Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
• Output: 3
• Place bomb at (1,1): Kills (0,1), (1,0), (2,1) → 3 enemies.
• Input: grid = [["W","W","E"],["0","0","W"],["E","E","0"]]
• Output: 2
• Place bomb at (1,0): Kills (2,0), (2,1) → 2 enemies.

These show the explosion’s reach—let’s solve it!

Understanding the Problem: Maximizing Enemy Kills

To tackle LeetCode 361 in Python, we need to: 1. Identify empty cells ('0') as potential bomb spots. 2. Count enemies ('E') in all four directions from each spot, stopping at walls ('W'). 3. Find the maximum enemy count across all spots.

A simple approach might check each direction for every empty cell, but that’s slow. Instead, we’ll use:

• Best Solution: Dynamic programming with precomputed counts—O(m*n) time, O(m*n) space—fast and smart.
• Alternative Solution: Brute force—O(m*n*(m+n)) time, O(1) space—clear but inefficient.

Let’s blast with the best solution!

Best Solution: Dynamic Programming with Precomputed Counts

Why This Is the Best Solution

The dynamic programming approach runs in O(m*n) time by precomputing enemy counts in rows and columns, then combining them at each empty cell. It avoids redundant traversals by caching counts between walls—making it the most efficient solution for this grid problem!

How It Works

Think of it like mapping the battlefield:

• Precompute:
• For each row, count enemies left-to-right and right-to-left between walls.
• For each column, count enemies top-to-bottom and bottom-to-top between walls.
• Combine: At each empty cell, sum the row and column counts.
• Maximize: Track the maximum total across all empty cells.

It’s like scouting the grid once and using the intel!

Step-by-Step Example

For grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]:

• Grid:

0 E 0 0 E 0 W E 0 E 0 0

• Row Counts (left-to-right):
• Row 0: [0,1,1,1] (0→E=1, no wall).
• Row 1: [1,1,0,1] (E→0=1, W resets, E=1).
• Row 2: [0,1,1,1] (0→E=1, no wall).
• Column Counts (top-to-bottom):
• Col 0: [1,2,2] (0→E=1, E=2, no wall).
• Col 1: [1,1,2] (E=1, 0→E=2).
• Col 2: [0,0,0] (all 0 until W).
• Col 3: [0,1,1] (0→E=1).
• Combine at '0' cells:
• (0,0): Row=0 + Col=1 = 1.
• (0,2): Row=1 + Col=0 = 1.
• (0,3): Row=1 + Col=0 = 1.
• (1,1): Row=1 + Col=1 = 2.
• (2,0): Row=0 + Col=2 = 2.
• (2,2): Row=1 + Col=0 = 1.
• (2,3): Row=1 + Col=1 = 2.
• Max: 3 (e.g., verified at (1,1) with manual check: up=1, left=1, down=1).

Output: 3.

Code with Explanation

Here’s the Python code using dynamic programming:

Copy codeclass Solution:
    def maxKilledEnemies(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0

        m, n = len(grid), len(grid[0])
        # Arrays to store enemy counts for rows and columns
        row_hits = [[0] * n for _ in range(m)]
        col_hits = [[0] * n for _ in range(m)]

        # Precompute row hits (left-to-right)
        for i in range(m):
            count = 0
            for j in range(n):
                if grid[i][j] == 'W':
                    count = 0
                elif grid[i][j] == 'E':
                    count += 1
                row_hits[i][j] = count

        # Precompute row hits (right-to-left)
        for i in range(m):
            count = 0
            for j in range(n-1, -1, -1):
                if grid[i][j] == 'W':
                    count = 0
                elif grid[i][j] == 'E':
                    count += 1
                row_hits[i][j] += count - (1 if grid[i][j] == 'E' else 0)

        # Precompute column hits (top-to-bottom)
        for j in range(n):
            count = 0
            for i in range(m):
                if grid[i][j] == 'W':
                    count = 0
                elif grid[i][j] == 'E':
                    count += 1
                col_hits[i][j] = count

        # Precompute column hits (bottom-to-top)
        for j in range(n):
            count = 0
            for i in range(m-1, -1, -1):
                if grid[i][j] == 'W':
                    count = 0
                elif grid[i][j] == 'E':
                    count += 1
                col_hits[i][j] += count - (1 if grid[i][j] == 'E' else 0)

        # Find max enemies killed at each '0'
        max_killed = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '0':
                    total = row_hits[i][j] + col_hits[i][j]
                    max_killed = max(max_killed, total)

        return max_killed

Explanation

• Lines 3-5: Handle empty grid case.
• Lines 7-8: Get dimensions, initialize arrays for row and column counts.
• Lines 10-17: Left-to-right row scan: Count enemies until wall, store cumulative count.
• Lines 19-26: Right-to-left row scan: Add counts, subtract self-count if 'E'.
• Lines 28-35: Top-to-bottom column scan: Similar to rows.
• Lines 37-44: Bottom-to-top column scan: Add counts, adjust for self.
• Lines 46-52: For each '0', sum row and column hits, track max.

• Time Complexity: O(m*n)—four passes over the grid.
• Space Complexity: O(m*n)—two auxiliary arrays.

This is like pre-mapping the blast zones—fast and precise!

Alternative Solution: Brute Force

Why an Alternative Approach?

The brute force solution is O(mn(m+n)) but straightforward—check each direction from every empty cell. It’s less efficient but easier to grasp—perfect for understanding the basics!

How It Works

• Scan: For each '0', count enemies in all four directions until walls.
• Maximize: Track the highest total.

Step-by-Step Example

For grid = [["0","E","0"],["E","0","W"]]:

• (0,0): Up=0, Down=1, Left=0, Right=1 → 2.
• (0,2): Up=0, Down=0, Left=1, Right=0 → 1.
• (1,1): Up=1, Down=0, Left=1, Right=0 → 2.
• Max: 2.

Code with Explanation

Copy codeclass Solution:
    def maxKilledEnemies(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0

        m, n = len(grid), len(grid[0])
        max_killed = 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '0':
                    # Count enemies in all 4 directions
                    count = 0
                    # Up
                    for r in range(i-1, -1, -1):
                        if grid[r][j] == 'W':
                            break
                        if grid[r][j] == 'E':
                            count += 1
                    # Down
                    for r in range(i+1, m):
                        if grid[r][j] == 'W':
                            break
                        if grid[r][j] == 'E':
                            count += 1
                    # Left
                    for c in range(j-1, -1, -1):
                        if grid[i][c] == 'W':
                            break
                        if grid[i][c] == 'E':
                            count += 1
                    # Right
                    for c in range(j+1, n):
                        if grid[i][c] == 'W':
                            break
                        if grid[i][c] == 'E':
                            count += 1
                    max_killed = max(max_killed, count)

        return max_killed

Explanation

• Lines 7-12: Loop over grid, check '0' cells.
• Lines 13-35: For each '0', count enemies in four directions, stopping at 'W'.
• Time: O(m*n*(m+n))—up to m+n steps per cell.
• Space: O(1)—no extra space.

It’s like manually scouting each bomb spot!

Comparing the Two Solutions

• DP with Counts (Best):
• Time: O(m*n)—linear passes.
• Space: O(m*n)—auxiliary arrays.
• Pros: Fast, scalable.
• Cons: More memory.
• Brute Force (Alternative):
• Time: O(m*n*(m+n))—quadratic per cell.
• Space: O(1)—minimal.
• Pros: Simple logic.
• Cons: Slow for large grids.

DP wins for efficiency!

Additional Examples and Edge Cases

• Empty grid: 0.
• No '0': 0.
• All 'E': Limited by walls.

Both handle these, DP is faster.

Complexity Breakdown

• DP:
• Time: O(m*n).
• Space: O(m*n).
• Brute Force:
• Time: O(m*n*(m+n)).
• Space: O(1).

DP excels for performance.

Key Takeaways

• DP: Precompute for speed—smart strategy!
• Brute Force: Check everything—easy to start!
• Grids: Optimization is key.
• Python Tip: Loops and arrays rock—see [Python Basics](/python/basics).

Final Thoughts: Blast Those Enemies

LeetCode 361: Bomb Enemy in Python is a grid-based challenge. DP with counts is the efficiency champ, while brute force builds understanding. Want more? Try LeetCode 200: Number of Islands or LeetCode 463: Island Perimeter. Ready to bomb? Visit Solve LeetCode 361 on LeetCode and maximize that blast today!