Detonate the Maximum Bombs

LeetCode 2101: Detonate the Maximum Bombs Solution & Explanation

Problem Overview

TL;DR: Model the bombs as a directed graph where edges represent detonation reach, then perform a Depth-First Search (DFS) from every bomb to find the starting point that yields the largest set of reachable nodes.

The Detonate the Maximum Bombs problem asks us to determine the maximum number of bombs that can be triggered by detonating a single chosen bomb. Each bomb has a circular range defined by a radius. When a bomb detonates, it triggers all other bombs whose centers lie within its circular range. This creates a chain reaction. Because radii differ, the relationship is not necessarily mutual; a large bomb might trigger a small one, but the small one might not trigger the large one.

This is a classic application of graph theory on a geometric dataset, making LeetCode 2101 a popular interview question for testing the ability to translate physical constraints into data structures.

Brute Force Approach for Detonate the Maximum Bombs

A naive interpretation of the problem might involve simulating the chain reaction step-by-step without constructing a formal graph structure.

1. Select a starting bomb.
2. Iterate through the entire list of bombs to see which ones are within range.
3. Add the triggered bombs to a "to-do" list.
4. Repeat the check for every newly triggered bomb against the entire list again to find subsequent detonations.
5. Repeat this entire process for every possible starting bomb.

Why this is suboptimal

While this approach logically finds the solution, it performs redundant geometric calculations. For every step in the chain reaction, we might iterate through the entire array bombs to check distances, leading to significant overhead. Specifically, checking reachability "on the fly" requires repeated distance formula calculations ($O(N)$) for every node visited in every traversal, resulting in a time complexity closer to $O(N^3)$ or $O(N^4)$ depending on implementation details.

Although the constraint $N \le 100$ allows this to pass, explicitly modeling the relationships as a graph first is cleaner, faster, and demonstrates the correct engineering pattern.

Algorithm Strategy: Graph Traversal Patterns (DFS & BFS)

We will implement the solution using the Graph DFS pattern.

1. Graph Construction:

   • Create an adjacency list to represent the graph.
   • Iterate through every pair of bombs $(i, j)$.
   • Calculate the squared Euclidean distance between their centers.
   • If the squared distance is less than or equal to the square of bomb $i$'s radius, add a directed edge $i \to j$.

2. DFS Traversal:

   • Since any bomb could potentially trigger the largest chain reaction, we iterate through each bomb index from $0$ to $N-1$ to act as the source.
   • For each source, initialize a visited set to track detonations in the current chain.
   • Perform a standard DFS (or BFS) starting from source.
   • Count the number of unique nodes visited.

3. Result Aggregation:

   • Maintain a variable max_detonations.
   • After the DFS for a specific source completes, update max_detonations with the larger of the current count or the existing maximum.
   • Return max_detonations.

Execution Flow

Let's trace the algorithm with a simple example: bombs = [[0,0,2], [0,3,2]].

1. Build Graph:

   • Compare Bomb 0 and Bomb 1.
   • Distance squared is $(0-0)^2 + (0-3)^2 = 9$.
   • Bomb 0 radius squared is $2^2 = 4$. $9 > 4$, so $0 \not\to 1$.
   • Bomb 1 radius squared is $2^2 = 4$. $9 > 4$, so $1 \not\to 0$.
   • Adjacency List: 0: [], 1: [].

2. Iterate Sources:

   • Source = 0:
     • visited = {0}.
     • Stack: [0]. Pop 0. Neighbors: None.
     • Count: 1. max_detonations = 1.
   • Source = 1:
     • visited = {1}.
     • Stack: [1]. Pop 1. Neighbors: None.
     • Count: 1. max_detonations = 1.

3. Return: 1.

Consider a connected example: A -> B.

1. Source A: DFS visits A, sees edge to B. DFS visits B. Count = 2. Update Max = 2.
2. Source B: DFS visits B. No outgoing edges. Count = 1. Max remains 2.
3. Return: 2.

Proof of Correctness

The correctness relies on the faithful representation of the physical problem as a graph. The condition $(x_i-x_j)^2 + (y_i-y_j)^2 \le r_i^2$ is the exact mathematical definition of "Bomb $j$ is in range of Bomb $i$." By constructing directed edges based on this inequality, the graph topology perfectly mirrors the detonation logic.

The DFS algorithm is guaranteed to visit every node reachable from a starting vertex in a finite graph. By resetting the visited state and running DFS for every possible start node, we exhaustively check the reachability potential of every bomb. Thus, the maximum value found is guaranteed to be the global maximum.

Pattern Reuse Notes

The Graph DFS pattern used in LeetCode 2101 is highly versatile. It appears in various forms across many interview problems:

• LeetCode 200: Number of Islands: Uses DFS to find connected components in a grid (undirected graph).
• LeetCode 547: Number of Provinces: Uses DFS on an adjacency matrix to count connected components (undirected).
• LeetCode 130: Surrounded Regions: Uses DFS from boundary nodes to determine reachability (undirected).
• LeetCode 417: Pacific Atlantic Water Flow: Uses DFS from ocean boundaries to find reachable cells (directed graph based on height).

While Detonate the Maximum Bombs requires traversing from every node due to its directed nature, the core logic of using recursion or a stack to explore a graph remains identical.

Reference Implementation

C++ Solution for LeetCode 2101

1class Solution {
2public:
3    int maximumDetonation(vector<vector<int>>& bombs) {
4        int n = bombs.size();
5        // Adjacency list for the directed graph
6        vector<vector<int>> graph(n);
7        
8        // Build the graph
9        for (int i = 0; i < n; i++) {
10            for (int j = 0; j < n; j++) {
11                if (i == j) continue;
12                
13                long long x1 = bombs[i][0], y1 = bombs[i][1], r1 = bombs[i][2];
14                long long x2 = bombs[j][0], y2 = bombs[j][1];
15                
16                // Calculate squared distance to avoid sqrt precision issues
17                long long distSq = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
18                long long rSq = r1 * r1;
19                
20                if (distSq <= rSq) {
21                    graph[i].push_back(j);
22                }
23            }
24        }
25        
26        int maxBombs = 0;
27        
28        // Try detonating each bomb as the starting point
29        for (int i = 0; i < n; i++) {
30            int count = 0;
31            vector<bool> visited(n, false);
32            dfs(i, visited, count, graph);
33            maxBombs = max(maxBombs, count);
34        }
35        
36        return maxBombs;
37    }
38
39private:
40    void dfs(int node, vector<bool>& visited, int& count, const vector<vector<int>>& graph) {
41        visited[node] = true;
42        count++;
43        
44        for (int neighbor : graph[node]) {
45            if (!visited[neighbor]) {
46                dfs(neighbor, visited, count, graph);
47            }
48        }
49    }
50};

Java Solution for LeetCode 2101

1import java.util.*;
2
3class Solution {
4    public int maximumDetonation(int[][] bombs) {
5        int n = bombs.length;
6        List<List<Integer>> graph = new ArrayList<>();
7        
8        for (int i = 0; i < n; i++) {
9            graph.add(new ArrayList<>());
10        }
11        
12        // Build the directed graph
13        for (int i = 0; i < n; i++) {
14            for (int j = 0; j < n; j++) {
15                if (i == j) continue;
16                
17                long x1 = bombs[i][0], y1 = bombs[i][1], r1 = bombs[i][2];
18                long x2 = bombs[j][0], y2 = bombs[j][1];
19                
20                // Use long to prevent overflow during squaring
21                long distSq = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
22                long rSq = r1 * r1;
23                
24                if (distSq <= rSq) {
25                    graph.get(i).add(j);
26                }
27            }
28        }
29        
30        int maxBombs = 0;
31        
32        // DFS from each node to find maximum reachability
33        for (int i = 0; i < n; i++) {
34            maxBombs = Math.max(maxBombs, dfs(i, new boolean[n], graph));
35        }
36        
37        return maxBombs;
38    }
39    
40    private int dfs(int node, boolean[] visited, List<List<Integer>> graph) {
41        visited[node] = true;
42        int count = 1;
43        
44        for (int neighbor : graph.get(node)) {
45            if (!visited[neighbor]) {
46                count += dfs(neighbor, visited, graph);
47            }
48        }
49        return count;
50    }
51}

Python Solution for LeetCode 2101

1class Solution:
2    def maximumDetonation(self, bombs: List[List[int]]) -> int:
3        n = len(bombs)
4        graph = [[] for _ in range(n)]
5        
6        # Build the directed graph
7        for i in range(n):
8            for j in range(n):
9                if i == j:
10                    continue
11                
12                x1, y1, r1 = bombs[i]
13                x2, y2, _ = bombs[j]
14                
15                # Check if bomb j is within range of bomb i
16                dist_sq = (x1 - x2)**2 + (y1 - y2)**2
17                if dist_sq <= r1**2:
18                    graph[i].append(j)
19        
20        def dfs(node, visited):
21            visited.add(node)
22            count = 1
23            for neighbor in graph[node]:
24                if neighbor not in visited:
25                    count += dfs(neighbor, visited)
26            return count
27
28        max_bombs = 0
29        
30        # Run DFS from every node
31        for i in range(n):
32            visited = set()
33            max_bombs = max(max_bombs, dfs(i, visited))
34            
35        return max_bombs