361. Bomb Enemy

MediumArrayDynamic ProgrammingMatrix
Leetcode Link

Problem Description

In this problem, we're given a 2D grid, which can be thought of as a game board where each cell can contain a wall represented by 'W', an enemy represented by 'E', or be an empty space represented by '0'. The task is to compute the maximum number of enemies that can be eliminated by placing a bomb in one of the empty cells. A bomb, when detonated, will eliminate all enemies in the same row and column, but the blast cannot pass through walls. The objective is to find the optimal placement for the bomb that results in the most enemies killed.

Intuition

The underlying concept for this solution is the employment of dynamic programming to traverse the grid in such a way that we count the number of enemies that can be affected by a bomb placed in an empty cell, taking walls into account which can block the blast. To accomplish this efficiently, we can do the following:

  1. We traverse each row from left to right and from right to left. For each cell, we add the number of enemies that can be blasted in that row segment if a bomb were placed there.

  2. We do a similar traversal for columns, going from top to bottom and then from bottom to top. Addition to each cell's count is done in the same manner as the row traversal.

  3. As we're calculating the potential blast impact, we store these values into an auxiliary matrix (let's call it g) so that we can keep track of the number of enemies that can be hit from each empty cell.

  4. Once the g matrix is filled with the blast potential for each empty cell, we find the maximum value in g for which the cell in the original grid is '0' (empty), as only empty cells are eligible for bomb placement.

The algorithm works because it decomposes the problem into calculating the impact of a bomb in individual rows and columns, rather than considering the entire grid for each cell. This greatly reduces the amount of computation needed to find the optimal bomb placement.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Solution Approach

The solution implements a methodical approach to calculate the maximum number of enemies that can be killed with a single bomb location. It uses dynamic programming techniques and carries out the task in several sweeps across the matrix.

Here's how the implementation proceeds:

  1. Preparation:

    • Initialize a matrix g of the same dimensions as grid, to store the potential blast count for each cell. Initially, all values in g are zeros.
    • Define variables m and n to store the number of rows and columns of the grid respectively.

  2. Row-wise Sweep:

    • For each row in grid, traverse from left to right and incrementally update the bomb impact count in g unless a wall is encountered. If a wall is encountered, reset the temporary count t to zero, as the wall blocks the bomb's blast.
    • Repeat the sweep from right to left to account for enemies that can only be hit from this direction, once again updating g and resetting t to zero every time a wall is hit.

  3. Column-wise Sweep:

    • For each column in grid, repeat a similar process, traversing from top to bottom and then from bottom to top. This step ensures that vertical blast impacts are also counted and added to the same cells in g.

  4. Maximum Enemies Killed:

    • Iterate through the entire g matrix and check the potential blast counts for each empty cell ('0') in the original grid.
    • Keep track of the maximum count found and return it as the final answer.

Coding constructs used:

  • For loops are used extensively for matrix traversal.
  • Conditional statements (if, elif) to differentiate between wall ('W'), enemy ('E'), and empty cell ('0').
  • A nested list comprehension combined with max function is used at the end to find the highest potential blast count where the cell in grid is an empty space.

Through this method, we save on both time and space complexity by avoiding redundant calculations of the blast effect for each empty cell and instead using a pre-computed g matrix to answer the main question.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer techniques do you use to check if a string is a palindrome?

Example Walkthrough

Let's use a small 4x3 grid as an example to illustrate the solution approach. Our grid looks like this:

1E 0 E
2W E 0
3E W 0
40 E 0

  1. Preparation:

    • We initialize a matrix g with zeros that matches the dimensions of our grid, (4x3): 
      10 0 0
20 0 0
30 0 0
40 0 0
    • We have m=4 rows and n=3 columns.

  2. Row-wise Sweep:

    • For the first row, we traverse from left to right. Since the first cell contains an enemy ('E'), we set a temporary count t = 1 and proceed to the next cell, which is empty. We update the g matrix at this empty cell to reflect the number of enemies a bomb could hit in this row, so g[0][1] = 1. We continue and find another enemy, increasing t to 2. The row ends here.
    • For the first row, we reverse sweep from right to left. Starting from t = 0 (since it's the end), the first cell on the right is an enemy, so t = 1. The next cell, which is empty, gets updated with 1 (existing value in g + t), and the leftmost enemy contributes to the existing count, so t = 2. The row is complete, and we've updated g[0][1] = 2.
    • After performing similar processes for the other rows, g might look something like this: 
      11 2 1
20 1 2
31 0 2
42 3 2

  3. Column-wise Sweep:

    • We sweep from top to bottom for each column now, starting with the first column. The first cell has an enemy, so t = 1 and updating as we move down through empty spaces and other enemies. However, the second row has a wall, so t resets to 0 after that point.
    • Sweeping from bottom up, we update the g matrix based on the number of enemies in each column, checking for walls.
    • After the column-wise sweep, g might be updated to: 
      11 2 1
20 2 3
31 0 3
42 3 3

  4. Maximum Enemies Killed:

    • We iterate over g and check it against the original grid to find the maximum number of enemies we could kill by placing a bomb in empty cells.
    • We find that the maximum number is 3, corresponding to any of the bottom row empty cells. So, placing a bomb at g[1][2], g[2][2] or g[3][1] or g[3][2] would kill the most enemies, which is 3.

Following the given methodology, we determined the optimal bombing locations while reducing redundant calculations, therefore making our algorithm efficient in terms of both time and space.

Solution Implementation

1class Solution:
2    def maxKilledEnemies(self, grid: List[List[str]]) -> int:
3        # Get the number of rows and columns in the grid
4        rows, cols = len(grid), len(grid[0])
5      
6        # Initialize a grid to keep track of the kill count  
7        kill_count = [[0] * cols for _ in range(rows)]
8
9        # Traverse the grid row-wise from left to right and right to left
10        for i in range(rows):
11            row_hits = 0  # Counter for enemies in the current row
12            # Left to right traversal
13            for j in range(cols):
14                if grid[i][j] == 'W':  # Reset counter when a wall is found
15                    row_hits = 0
16                elif grid[i][j] == 'E':  # Increment counter if an enemy is found
17                    row_hits += 1
18                kill_count[i][j] += row_hits  # Accumulate hits for the current cell
19          
20            # Right to left traversal
21            row_hits = 0  # Reset counter for the reverse traversal
22            for j in range(cols - 1, -1, -1):
23                if grid[i][j] == 'W':
24                    row_hits = 0
25                elif grid[i][j] == 'E':
26                    row_hits += 1
27                kill_count[i][j] += row_hits  # Accumulate hits for the current cell
28      
29        # Traverse the grid column-wise from top to bottom and bottom to top
30        for j in range(cols):
31            col_hits = 0  # Counter for enemies in the current column
32            # Top to bottom traversal
33            for i in range(rows):
34                if grid[i][j] == 'W':  # Reset counter when a wall is found
35                    col_hits = 0
36                elif grid[i][j] == 'E':  # Increment counter if an enemy is found
37                    col_hits += 1
38                kill_count[i][j] += col_hits  # Accumulate hits for the current cell
39          
40            # Bottom to top traversal
41            col_hits = 0  # Reset counter for the reverse traversal
42            for i in range(rows - 1, -1, -1):
43                if grid[i][j] == 'W':
44                    col_hits = 0
45                elif grid[i][j] == 'E':
46                    col_hits += 1
47                kill_count[i][j] += col_hits  # Accumulate hits for the current cell
48
49        # Calculate the max kills possible by placing a bomb in an empty cell ('0')
50        max_kills = max(
51            [kill_count[i][j] for i in range(rows) for j in range(cols) if grid[i][j] == '0'],
52            default=0,  # Fallback value to use if no '0' cells are found
53        )
54
55        return max_kills  # Return the maximum number of kills
56
1class Solution {
2    public int maxKilledEnemies(char[][] grid) {
3        int rows = grid.length;
4        int cols = grid[0].length;
5        int[][] killCount = new int[rows][cols];
6      
7        // Calculate the number of enemies that can be killed horizontally
8        for (int i = 0; i < rows; ++i) {
9            int rowCount = 0;
10            for (int j = 0; j < cols; ++j) {
11                if (grid[i][j] == 'W') { // Wall encountered, reset count
12                    rowCount = 0;
13                } else if (grid[i][j] == 'E') { // Enemy encountered, increment count
14                    ++rowCount;
15                }
16                killCount[i][j] += rowCount;
17            }
18            rowCount = 0;
19            for (int j = cols - 1; j >= 0; --j) {
20                if (grid[i][j] == 'W') {
21                    rowCount = 0;
22                } else if (grid[i][j] == 'E') {
23                    ++rowCount;
24                }
25                killCount[i][j] += rowCount;
26            }
27        }
28      
29        // Calculate the number of enemies that can be killed vertically
30        for (int j = 0; j < cols; ++j) {
31            int colCount = 0;
32            for (int i = 0; i < rows; ++i) {
33                if (grid[i][j] == 'W') {
34                    colCount = 0;
35                } else if (grid[i][j] == 'E') {
36                    ++colCount;
37                }
38                killCount[i][j] += colCount;
39            }
40            colCount = 0;
41            for (int i = rows - 1; i >= 0; --i) {
42                if (grid[i][j] == 'W') {
43                    colCount = 0;
44                } else if (grid[i][j] == 'E') {
45                    ++colCount;
46                }
47                killCount[i][j] += colCount; // Enemy on top of current square can also be killed
48            }
49        }
50      
51        // Find the cell that can kill the most enemies
52        int maxKills = 0;
53        for (int i = 0; i < rows; ++i) {
54            for (int j = 0; j < cols; ++j) {
55                if (grid[i][j] == '0') { // Empty cell, potential for a bomb
56                    maxKills = Math.max(maxKills, killCount[i][j]);
57                }
58            }
59        }
60      
61        return maxKills; // Return the maximum enemies that can be killed
62    }
63}
64
1class Solution {
2public:
3    int maxKilledEnemies(vector<vector<char>>& grid) {
4        // Get the number of rows and columns in the grid.
5        int rows = grid.size(), cols = grid[0].size();
6
7        // Create a 2D vector to store the number of enemies that can be killed for each cell.
8        vector<vector<int>> killCount(rows, vector<int>(cols, 0));
9
10        // Traverse the grid to calculate potential kills horizontally.
11        for (int i = 0; i < rows; ++i) {
12            int consecutiveEnemies = 0;
13            // Left to right sweep
14            for (int j = 0; j < cols; ++j) {
15                if (grid[i][j] == 'W') {
16                    consecutiveEnemies = 0;
17                } else if (grid[i][j] == 'E') {
18                    ++consecutiveEnemies;
19                }
20                killCount[i][j] += consecutiveEnemies;
21            }
22            // Reset the counter for the right to left sweep
23            consecutiveEnemies = 0;
24            // Right to left sweep
25            for (int j = cols - 1; j >= 0; --j) {
26                if (grid[i][j] == 'W') {
27                    consecutiveEnemies = 0;
28                } else if (grid[i][j] == 'E') {
29                    ++consecutiveEnemies;
30                }
31                killCount[i][j] += consecutiveEnemies;
32            }
33        }
34
35        // Traverse the grid to calculate potential kills vertically.
36        for (int j = 0; j < cols; ++j) {
37            int consecutiveEnemies = 0;
38            // Top to bottom sweep
39            for (int i = 0; i < rows; ++i) {
40                if (grid[i][j] == 'W') {
41                    consecutiveEnemies = 0;
42                } else if (grid[i][j] == 'E') {
43                    ++consecutiveEnemies;
44                }
45                killCount[i][j] += consecutiveEnemies;
46            }
47            // Reset the counter for the bottom to top sweep
48            consecutiveEnemies = 0;
49            // Bottom to top sweep
50            for (int i = rows - 1; i >= 0; --i) {
51                if (grid[i][j] == 'W') {
52                    consecutiveEnemies = 0;
53                } else if (grid[i][j] == 'E') {
54                    ++consecutiveEnemies;
55                }
56                killCount[i][j] += consecutiveEnemies;
57            }
58        }
59
60        // Find the maximum number of enemies that can be killed by placing a bomb on an empty cell.
61        int maxKills = 0;
62        for (int i = 0; i < rows; ++i) {
63            for (int j = 0; j < cols; ++j) {
64                if (grid[i][j] == '0') {
65                    maxKills = max(maxKills, killCount[i][j]);
66                }
67            }
68        }
69      
70        return maxKills;
71    }
72};
73
1// Function to get the maximum number of enemies killed by placing a bomb on an empty cell in the grid.
2function maxKilledEnemies(grid: char[][]): number {
3    // Get the number of rows and columns in the grid.
4    const rows = grid.length;
5    const cols = grid[0].length;
6
7    // Create an array to store the number of enemies that can be killed for each cell.
8    const killCount: number[][] = Array.from({ length: rows }, () => Array(cols).fill(0));
9
10    // Traverse the grid to calculate potential kills horizontally.
11    for (let i = 0; i < rows; ++i) {
12        let consecutiveEnemies = 0;
13        // Left to right sweep
14        for (let j = 0; j < cols; ++j) {
15            if (grid[i][j] === 'W') {
16                consecutiveEnemies = 0;
17            } else if (grid[i][j] === 'E') {
18                consecutiveEnemies++;
19            }
20            killCount[i][j] += consecutiveEnemies;
21        }
22        // Reset the counter for the right to left sweep
23        consecutiveEnemies = 0;
24        // Right to left sweep
25        for (let j = cols - 1; j >= 0; --j) {
26            if (grid[i][j] === 'W') {
27                consecutiveEnemies = 0;
28            } else if (grid[i][j] === 'E') {
29                consecutiveEnemies++;
30            }
31            // Include kills from the right in the killCount, avoiding double count the cell itself
32            killCount[i][j] += consecutiveEnemies - (grid[i][j] === 'E' ? 1 : 0);
33        }
34    }
35
36    // Traverse the grid to calculate potential kills vertically.
37    for (let j = 0; j < cols; ++j) {
38        let consecutiveEnemies = 0;
39        // Top to bottom sweep
40        for (let i = 0; i < rows; ++i) {
41            if (grid[i][j] === 'W') {
42                consecutiveEnemies = 0;
43            } else if (grid[i][j] === 'E') {
44                consecutiveEnemies++;
45            }
46            killCount[i][j] += consecutiveEnemies;
47        }
48        // Reset the counter for the bottom to top sweep
49        consecutiveEnemies = 0;
50        // Bottom to top sweep
51        for (let i = rows - 1; i >= 0; --i) {
52            if (grid[i][j] === 'W') {
53                consecutiveEnemies = 0;
54            } else if (grid[i][j] === 'E') {
55                consecutiveEnemies++;
56            }
57            // Include kills from the bottom in the killCount, avoiding double count the cell itself
58            killCount[i][j] += consecutiveEnemies - (grid[i][j] === 'E' ? 1 : 0);
59        }
60    }
61
62    // Find the maximum number of enemies that can be killed by placing a bomb on an empty cell.
63    let maxKills = 0;
64    for (let i = 0; i < rows; ++i) {
65        for (let j = 0; j < cols; ++j) {
66            if (grid[i][j] === '0') {
67                maxKills = Math.max(maxKills, killCount[i][j]);
68            }
69        }
70    }
71  
72    return maxKills;
73}
74
Not Sure What to Study? Take the 2-min Quiz

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Time and Space Complexity

The given code traverses through the grid to calculate the maximum number of enemies that can be killed by placing a bomb on an empty cell ('0'). The algorithm processes the 2D grid in four separate linear passes: two are row-wise (left-to-right and right-to-left) and two are column-wise (top-to-bottom and bottom-to-top). Each pass counts the enemies ('E') in each direction, with walls ('W') resetting the count.

The time complexity is determined by these four traversals over all rows and columns:

  • The first two row-wise traversals have a complexity of O(m*n) each, as they go through each cell in each row.
  • The next two column-wise traversals also have a complexity of O(m*n) each, since they go through each cell in each column.

Since all four traversals are sequential and independent, the total time complexity for the algorithm is O(4*m*n) which simplifies to O(m*n).

The space complexity is determined by the additional grid g used to store the counts of enemies that can be hit from each cell. Since this grid is the same size as the input grid, the space complexity is O(m*n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«