Bomb Enemy Python Solution with Tests

Tested Python solution for LeetCode 361 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 361, Medium. Topics: Array, Dynamic Programming, Matrix. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 16 parametrized pytest cases, and a playground notebook:

lcpy gen -n 361   # by problem number
lcpy gen -s bomb_enemy   # by problem name

​

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.

​

Examples

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

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

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(m * n)
    # Space: O(n)
    def max_killed_enemies(self, grid: list[list[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        m, n = len(grid), len(grid[0])
        result = 0
        row_hits = 0
        col_hits = [0] * n
        for i in range(m):
            for j in range(n):
                if j == 0 or grid[i][j - 1] == "W":
                    row_hits = 0
                    k = j
                    while k < n and grid[i][k] != "W":
                        row_hits += grid[i][k] == "E"
                        k += 1
                if i == 0 or grid[i - 1][j] == "W":
                    col_hits[j] = 0
                    k = i
                    while k < m and grid[k][j] != "W":
                        col_hits[j] += grid[k][j] == "E"
                        k += 1
                if grid[i][j] == "0":
                    result = max(result, row_hits + col_hits[j])
        return result

​

Complexity

Time	Space
O(m * n)	O(n)

​

Tags