2101. Detonate the Maximum Bombs

You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb.

The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [xi, yi, ri]. xi and yi denote the X-coordinate and Y-coordinate of the location of the ith bomb, whereas ri denotes the radius of its range.

You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range. These bombs will further detonate the bombs that lie in their ranges.

Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb.

Example 1:

Input: bombs = [[2,1,3],[6,1,4]]
Output: 2
Explanation:
The above figure shows the positions and ranges of the 2 bombs.
If we detonate the left bomb, the right bomb will not be affected.
But if we detonate the right bomb, both bombs will be detonated.
So the maximum bombs that can be detonated is max(1, 2) = 2.

Example 2:

Input: bombs = [[1,1,5],[10,10,5]]
Output: 1
Explanation:
Detonating either bomb will not detonate the other bomb, so the maximum number of bombs that can be detonated is 1.

Example 3:

Input: bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
Output: 5
Explanation:
The best bomb to detonate is bomb 0 because:
- Bomb 0 detonates bombs 1 and 2. The red circle denotes the range of bomb 0.
- Bomb 2 detonates bomb 3. The blue circle denotes the range of bomb 2.
- Bomb 3 detonates bomb 4. The green circle denotes the range of bomb 3.
Thus all 5 bombs are detonated.

Constraints:

• 1 <= bombs.length <= 100
• bombs[i].length == 3
• 1 <= xi, yi, ri <= 105

Solution

First, notice that the bomb will only detonate another bomb if its area touches the center of another bomb. Overlapping without touching the center does not detonate the other bomb as seen in Example 1.

Upon first look, it looks like we can simply loop through each bomb and count the bombs it denotes.

# does not work, 
def max_detonated_bombs(bombs):
    max_bombs_detonated = 0
    for i, (xi, yi, ri) in enumerate(bombs):
        bombs_detonated = 1
        for j, (xj, yj, rj) in enumerate(bombs):
            if i == j:
                continue
            if (xi - xj) ** 2 + (yi - yj) ** 2 <= ri ** 2:
                bombs_detonated += 1
        max_bombs_detonated = max(max_bombs_detonated, bombs_detonated)
    return max_bombs_detonated

However, this does not work because the bombs denoted by the initial bomb may also detonate new bombs which are not considered here.

The connectivity between bombs is a suggestion that it’s a graph problem. And the fact that the green bomb does not detonate the purple bomb in Example 1 suggest the graph has direction.

To solve this problem using breadth-first search, we can represent the bombs as nodes in a directed graph, where an edge exists from node A to node B if and only if the explosion radius of A covers the center of B. Then, we can perform a breadth-first search starting from each bomb to find the maximum number of bombs that can be detonated if that bomb is chosen to be detonated.

from collections import deque

def max_detonations(bombs):
    n = len(bombs)
    graph = [[] for _ in range(n)]
    
    # Build the graph
    for i in range(n):
        xi, yi, ri = bombs[i]
        for j in range(n):
            if i == j:
                continue
            xj, yj, rj = bombs[j]
            if (xi-xj)**2 + (yi-yj)**2 <= ri**2:
                graph[i].append(j)
    
    # Perform breadth-first search from each bomb
    max_detonations = 0
    for i in range(n):
        visited = [False] * n
        visited[i] = True
        queue = deque([i])
        detonations = 1
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append(neighbor)
                    detonations += 1
        max_detonations = max(max_detonations, detonations)
    
    return max_detonations

If you want to brush up your graph knowledge, check out this article.

Learn more about the core patterns to solve any problem:

https://algo.monster/