Coding

Bomb Enemy

Asked at

Uber

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

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.

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]] Output: 3 Explanation : Placing bomb at index(1 based) [2,2] will eleminate employees at index [2,1] , [1,2] and [3,2].

Input: grid = [["W","W","W"],["0","0","0"],["E","E","E"]] Output: 1 Explanation: ["W", "W", "W"] ["0", "0", "0"] ["E", "E", "E"] Placing the bomb at the best empty cell can eliminate up to 3 enemies. The bomb affects all enemies in the same row and column until a wall blocks its path.

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

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid[i][j] is either 'W', 'E', or '0'.

cpp

class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        // Your code goes here
    }
};

java

class Solution {
    public int maxKilledEnemies(char[][] grid) {
        // Your code goes here
    }
}

python

class Solution(object):
    def maxKilledEnemies(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        # Your code goes here

javascript

/**
 * @param {character[][]} grid
 * @return {number}
 */
var maxKilledEnemies = function(grid) {
    // Your code goes here
};

csharp

public class Solution
{
    public int maxKilledEnemies(char[][] grid)
    {
        // Your code goes here
    }
}

func maxKilledEnemies(grid [][]byte) int

Stuck? Show a way to structure it+

01Scan each cell row-major.
02Recompute row count only after a wall boundary.
03Recompute column count only after a wall boundary.
04At empty cells maximize row plus column count.

Reference answer

For each row segment between walls, all empty cells share the same visible horizontal enemies; similarly for each column segment. During a row-major scan, recompute the row count when at the segment start and recompute a column count when entering a new column segment. At an empty cell, rowHits + colHits is its kill count. This is O(mn) time and O(n) space for column counts, rather than scanning four directions at every empty cell. In an interview, make the invariant explicit before writing code, trace a boundary example that breaks a tempting shortcut, state what each stored value represents, and explain why every update preserves correctness. This verification step also surfaces empty-input, duplicate-value, and numeric-limit cases.

Then expect these follow-ups

How would you return the best bomb position too?
Tests: tracking argmax
What changes if multiple bombs can be placed?
Tests: optimization

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question