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.

Core Insight for Detonate the Maximum Bombs

The key insight is to abstract the geometry away immediately. Instead of thinking about circles and coordinates during the traversal, we pre-process the input into a Directed Graph.

1. Nodes: Each bomb is a node (0 to $N-1$).
2. Directed Edges: A directed edge exists from Bomb $i$ to Bomb $j$ if and only if Bomb $j$ is within the blast radius of Bomb $i$.
   • Formula: Distance $(x_i - x_j)^2 + (y_i - y_j)^2 \le r_i^2$.

Because the graph is directed, the set of reachable nodes depends entirely on the starting node. Therefore, to find the maximum number of detonations, we must run a graph traversal (DFS) starting from each node independently and count the number of visited nodes for that specific run.

Visual Description: Imagine the bombs as nodes in space. Draw an arrow from Bomb A to Bomb B only if B is inside A's circle. We are looking for the "root" node that has paths leading to the highest number of other nodes. The algorithm visualizes this by lighting up a start node, following all outgoing arrows recursively, and counting the total number of lit nodes.

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.

Reference Implementation

C++ Solution for LeetCode 2101

cpp
class Solution {
public:
    int maximumDetonation(vector<vector<int>>& bombs) {
        int n = bombs.size();
        // Adjacency list for the directed graph
        vector<vector<int>> graph(n);
        
        // Build the graph
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                
                long long x1 = bombs[i][0], y1 = bombs[i][1], r1 = bombs[i][2];
                long long x2 = bombs[j][0], y2 = bombs[j][1];
                
                // Calculate squared distance to avoid sqrt precision issues
                long long distSq = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
                long long rSq = r1 * r1;
                
                if (distSq <= rSq) {
                    graph[i].push_back(j);
                }
            }
        }
        
        int maxBombs = 0;
        
        // Try detonating each bomb as the starting point
        for (int i = 0; i < n; i++) {
            int count = 0;
            vector<bool> visited(n, false);
            dfs(i, visited, count, graph);
            maxBombs = max(maxBombs, count);
        }
        
        return maxBombs;
    }

private:
    void dfs(int node, vector<bool>& visited, int& count, const vector<vector<int>>& graph) {
        visited[node] = true;
        count++;
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited, count, graph);
            }
        }
    }
};

Java Solution for LeetCode 2101

java
import java.util.*;

class Solution {
    public int maximumDetonation(int[][] bombs) {
        int n = bombs.length;
        List<List<Integer>> graph = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // Build the directed graph
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                
                long x1 = bombs[i][0], y1 = bombs[i][1], r1 = bombs[i][2];
                long x2 = bombs[j][0], y2 = bombs[j][1];
                
                // Use long to prevent overflow during squaring
                long distSq = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
                long rSq = r1 * r1;
                
                if (distSq <= rSq) {
                    graph.get(i).add(j);
                }
            }
        }
        
        int maxBombs = 0;
        
        // DFS from each node to find maximum reachability
        for (int i = 0; i < n; i++) {
            maxBombs = Math.max(maxBombs, dfs(i, new boolean[n], graph));
        }
        
        return maxBombs;
    }
    
    private int dfs(int node, boolean[] visited, List<List<Integer>> graph) {
        visited[node] = true;
        int count = 1;
        
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                count += dfs(neighbor, visited, graph);
            }
        }
        return count;
    }
}

Python Solution for LeetCode 2101

python
class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        n = len(bombs)
        graph = [[] for _ in range(n)]
        
        # Build the directed graph
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                
                x1, y1, r1 = bombs[i]
                x2, y2, _ = bombs[j]
                
                # Check if bomb j is within range of bomb i
                dist_sq = (x1 - x2)**2 + (y1 - y2)**2
                if dist_sq <= r1**2:
                    graph[i].append(j)
        
        def dfs(node, visited):
            visited.add(node)
            count = 1
            for neighbor in graph[node]:
                if neighbor not in visited:
                    count += dfs(neighbor, visited)
            return count

        max_bombs = 0
        
        # Run DFS from every node
        for i in range(n):
            visited = set()
            max_bombs = max(max_bombs, dfs(i, visited))
            
        return max_bombs