Problem Description

You have a list of bombs, where each bomb has a circular explosion range. When you detonate a bomb, it triggers all other bombs within its range, and those bombs will in turn trigger bombs within their ranges, creating a chain reaction.

Each bomb is represented as bombs[i] = [xi, yi, ri] where:

• (xi, yi) is the location of the bomb on a 2D plane
• ri is the radius of the bomb's explosion range

A bomb at position (x1, y1) with radius r1 can trigger another bomb at position (x2, y2) if the distance between them is less than or equal to r1. The distance is calculated using the Euclidean formula: √((x1-x2)² + (y1-y2)²).

You can choose to detonate exactly one bomb initially. Your goal is to find the maximum number of bombs that can be detonated (including the initial bomb and all bombs triggered through chain reactions) by choosing the optimal starting bomb.

For example, if bomb A triggers bomb B, and bomb B triggers bomb C, then detonating bomb A would result in 3 total detonations. The problem asks you to find which initial bomb choice gives you the maximum total detonations.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: This problem can be modeled as a directed graph where:
  • Each bomb is a node
  • There's a directed edge from bomb i to bomb j if bomb i can trigger bomb j (when the distance between them ≤ radius of bomb i)
  • The chain reaction of detonations is essentially graph traversal

Is it a tree?

• No: The graph is not a tree because:
  • It can have cycles (bomb A can trigger B, and B can trigger A if they're both within each other's range)
  • A node can have multiple parents (multiple bombs can trigger the same bomb)
  • It's a directed graph where edges are based on explosion ranges

Is the problem related to directed acyclic graphs?

• No: The graph can contain cycles as bombs can be within each other's explosion ranges

Is the problem related to shortest paths?

• No: We're not looking for the shortest path between nodes. Instead, we want to find the maximum number of nodes (bombs) reachable from a starting node

Does the problem involve connectivity?

• Yes: The core of the problem is about connectivity - finding how many bombs are connected (reachable) from a starting bomb through the chain reaction

Does the problem have small constraints?

• Yes: With typical constraints of n ≤ 100 bombs, we can afford to run DFS/BFS from each bomb as a starting point

DFS/backtracking?

• Yes: DFS (or BFS as shown in the solution) is perfect for exploring all reachable nodes from a starting point

Conclusion: The flowchart suggests using DFS to explore the connectivity of the graph. We build a directed graph based on explosion ranges, then use DFS from each bomb to find the maximum number of bombs that can be detonated in a chain reaction.

Intuition

The key insight is recognizing that this is a graph traversal problem disguised as a geometry problem. When a bomb explodes, it triggers other bombs within its range, which then trigger more bombs - this is exactly how we traverse a graph from one node to its neighbors.

Think of each bomb as a node in a directed graph. If bomb A can trigger bomb B (meaning B is within A's explosion radius), we draw a directed edge from A to B. Notice that this relationship is not symmetric - bomb A might be able to trigger bomb B, but B might not be able to trigger A if B has a smaller radius.

To determine if one bomb can trigger another, we calculate the Euclidean distance between them: distance = √((x1-x2)² + (y1-y2)²). If this distance is less than or equal to the first bomb's radius, it can trigger the second bomb.

Once we've built this directed graph, the problem becomes: "Starting from which node can we reach the maximum number of nodes?" This is a classic graph traversal problem. We need to try starting from each bomb and see how many bombs we can reach through the chain reaction.

For each starting bomb, we perform a graph traversal (BFS or DFS) to visit all reachable bombs. We keep track of visited bombs to avoid counting the same bomb twice and to handle cycles in the graph. The traversal naturally simulates the chain reaction - as we visit each bomb, we explore all bombs it can trigger, then all bombs those can trigger, and so on.

The answer is the maximum count of bombs we can detonate across all possible starting choices. If at any point we can detonate all n bombs, we can return early since that's the maximum possible.

Learn more about Depth-First Search, Breadth-First Search, Graph and Math patterns.

Solution Approach

The solution uses BFS to traverse the graph and find the maximum number of bombs that can be detonated.

Step 1: Build the Directed Graph

First, we create an adjacency list g where g[i] contains all bombs that can be triggered by bomb i. We iterate through all pairs of bombs and calculate the distance between them using the hypot function (which computes √((x1-x2)² + (y1-y2)²)).

For each pair of bombs i and j:

• If dist <= r1 (distance is within bomb i's radius), bomb i can trigger bomb j, so we add j to g[i]
• If dist <= r2 (distance is within bomb j's radius), bomb j can trigger bomb i, so we add i to g[j]

Note that we only check pairs where i < j to avoid duplicate calculations, but we add edges in both directions when applicable.

Step 2: BFS from Each Starting Bomb

For each bomb k as a potential starting point:

1. Initialize a visited set vis with just bomb k
2. Create a queue q starting with bomb k
3. Process the queue using BFS:
   • For each bomb i in the queue, explore all bombs j in g[i] (bombs that i can trigger)
   • If bomb j hasn't been visited, mark it as visited and add it to the queue
   • This simulates the chain reaction spreading to all reachable bombs

Step 3: Track the Maximum

After BFS completes for starting bomb k, the size of vis tells us how many bombs were detonated in total. We keep track of the maximum across all starting points.

Optimization: If at any point we can detonate all n bombs (when len(vis) == n), we immediately return n since that's the maximum possible.

The time complexity is O(n³) where n is the number of bombs: O(n²) to build the graph (checking all pairs) and O(n²) for BFS from each of the n starting points. The space complexity is O(n²) for storing the adjacency list.

Example Walkthrough

Let's walk through a small example with 3 bombs:

• Bomb 0: [1, 1, 2] (position (1,1), radius 2)
• Bomb 1: [2, 2, 1] (position (2,2), radius 1)
• Bomb 2: [5, 5, 3] (position (5,5), radius 3)

Step 1: Build the Directed Graph

We calculate distances between all pairs:

• Distance from Bomb 0 to Bomb 1: √((1-2)² + (1-2)²) = √2 ≈ 1.41

  • Since 1.41 ≤ 2 (Bomb 0's radius), Bomb 0 can trigger Bomb 1 → Add edge 0→1
  • Since 1.41 > 1 (Bomb 1's radius), Bomb 1 cannot trigger Bomb 0

• Distance from Bomb 0 to Bomb 2: √((1-5)² + (1-5)²) = √32 ≈ 5.66

  • Since 5.66 > 2 (Bomb 0's radius), Bomb 0 cannot trigger Bomb 2
  • Since 5.66 > 3 (Bomb 2's radius), Bomb 2 cannot trigger Bomb 0

• Distance from Bomb 1 to Bomb 2: √((2-5)² + (2-5)²) = √18 ≈ 4.24

  • Since 4.24 > 1 (Bomb 1's radius), Bomb 1 cannot trigger Bomb 2
  • Since 4.24 > 3 (Bomb 2's radius), Bomb 2 cannot trigger Bomb 1

Our adjacency list becomes:

g[0] = [1]  // Bomb 0 can trigger Bomb 1
g[1] = []   // Bomb 1 cannot trigger any bombs
g[2] = []   // Bomb 2 cannot trigger any bombs

Step 2: BFS from Each Starting Bomb

Starting from Bomb 0:

1. Initialize: vis = {0}, q = [0]
2. Process Bomb 0: Check neighbors in g[0] = [1]
   • Bomb 1 not visited, add to vis = {0, 1} and q = [1]
3. Process Bomb 1: Check neighbors in g[1] = [] (no neighbors)
4. Queue empty, BFS complete
5. Total detonations: 2 (Bombs 0 and 1)

Starting from Bomb 1:

1. Initialize: vis = {1}, q = [1]
2. Process Bomb 1: Check neighbors in g[1] = [] (no neighbors)
3. Queue empty, BFS complete
4. Total detonations: 1 (only Bomb 1)

Starting from Bomb 2:

1. Initialize: vis = {2}, q = [2]
2. Process Bomb 2: Check neighbors in g[2] = [] (no neighbors)
3. Queue empty, BFS complete
4. Total detonations: 1 (only Bomb 2)

Step 3: Find Maximum

Maximum detonations = max(2, 1, 1) = 2

Therefore, by choosing to detonate Bomb 0 initially, we can achieve the maximum of 2 total detonations through the chain reaction.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n³)

The time complexity analysis breaks down as follows:

• Building the graph requires O(n²) time, as we have a nested loop comparing each pair of bombs once (lines 5-12)
• The BFS/graph traversal section (lines 13-22) runs n times (once for each starting bomb)
• For each starting position, we perform a BFS that in the worst case visits all n bombs
• Each bomb can have up to n-1 edges in its adjacency list
• Therefore, the worst-case time for all BFS traversals is O(n) × O(n²) = O(n³)
  • Outer loop: n iterations
  • BFS can visit up to n nodes
  • Each node can have up to n-1 neighbors to check

Space Complexity: O(n²)

The space complexity analysis:

• The adjacency list g can store up to O(n²) edges in the worst case (when every bomb can detonate every other bomb)
• The visited set vis uses O(n) space
• The queue q uses O(n) space in the worst case
• Since O(n²) + O(n) + O(n) = O(n²), the overall space complexity is O(n²)

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

Common Pitfalls

1. Integer Overflow in Distance Calculation

One of the most common pitfalls in this problem is using integer arithmetic for distance comparison, which can cause integer overflow for large coordinates.

Problematic approach:

# This can overflow for large values
distance_squared = (x1 - x2) ** 2 + (y1 - y2) ** 2
if distance_squared <= radius ** 2:  # Comparing squared values
    # Add edge

Why it's problematic:

• When coordinates are near the constraint limits (e.g., 10^5), the squared differences can exceed integer limits
• Python handles big integers well, but in other languages this causes overflow
• Even in Python, comparing very large integers can be less efficient

Better solution:

# Use floating-point distance calculation
distance = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
if distance <= radius:
    # Add edge

2. Bidirectional Edge Confusion

Another pitfall is incorrectly assuming the detonation relationship is symmetric. Just because bomb A can detonate bomb B doesn't mean bomb B can detonate bomb A.

Incorrect approach:

for i in range(num_bombs):
    for j in range(i + 1, num_bombs):
        distance = calculate_distance(bombs[i], bombs[j])
        if distance <= bombs[i][2]:  # Only checking one radius
            graph[i].append(j)
            graph[j].append(i)  # Wrong! Assuming symmetry

Correct approach:

for i in range(num_bombs):
    for j in range(i + 1, num_bombs):
        distance = calculate_distance(bombs[i], bombs[j])
        if distance <= bombs[i][2]:  # Bomb i can detonate bomb j
            graph[i].append(j)
        if distance <= bombs[j][2]:  # Bomb j can detonate bomb i
            graph[j].append(i)

3. Using DFS Instead of BFS

While both DFS and BFS work correctly for this problem, using recursive DFS can lead to stack overflow for large inputs with deep chains.

Risky recursive DFS:

def dfs(bomb, visited, graph):
    visited.add(bomb)
    for neighbor in graph[bomb]:
        if neighbor not in visited:
            dfs(neighbor, visited, graph)  # Can cause stack overflow

Safer iterative BFS (as shown in solution):

queue = [start_bomb]
for current_bomb in queue:
    for neighbor_bomb in graph[current_bomb]:
        if neighbor_bomb not in visited:
            visited.add(neighbor_bomb)
            queue.append(neighbor_bomb)

The iterative BFS approach avoids recursion depth issues and is generally more memory-efficient for this type of graph traversal problem.