LeetCode Problem 2101

Difficulty: 🟡 Medium
Topics: Array, Math, Depth-First Search, Breadth-First Search, Graph Theory, Geometry

Solution

Problem Understanding

In this problem, each bomb is represented by three integers: its x-coordinate, y-coordinate, and explosion radius. If a bomb explodes, every other bomb whose center lies within or on the boundary of that radius will also explode. Those newly exploded bombs can continue triggering additional bombs, creating a chain reaction.

The task is to determine the maximum number of bombs that can be detonated by manually triggering exactly one bomb at the start.

The important detail is that detonation is directional. If bomb A can reach bomb B, that does not automatically mean bomb B can reach bomb A. A bomb with a large radius may trigger another bomb with a smaller radius, but the reverse might not be possible.

We can think of this as a directed graph problem:

• Each bomb is a node.
• There is a directed edge from bomb i to bomb j if bomb j lies within the explosion radius of bomb i.

Once the graph is built, the problem becomes:

For every node, compute how many nodes are reachable from it, then return the maximum reachable count.

The constraints are relatively small:

• 1 <= bombs.length <= 100
• Coordinates and radii can be as large as 10^5

Since there are at most 100 bombs, an O(n^2) or even O(n^3) solution is completely acceptable.

One important implementation detail is avoiding floating point arithmetic. To determine whether one bomb can reach another, we compare squared distances instead of computing square roots:

$$(x_1 - x_2)^2 + (y_1 - y_2)^2 \le r^2$$

$(x_1-x_2)^2+(y_1-y_2)^2\le r^2$

This avoids precision issues and is more efficient.

Several edge cases are important:

• A single bomb should return 1.
• Bombs may overlap completely.
• No bombs may be reachable from any other bomb.
• Detonation chains may be long and indirect.
• Large coordinate values can cause overflow in some languages if integer types are too small.

The problem guarantees valid input sizes and positive radii, so we do not need to handle malformed data.

Approaches

Brute Force Approach

The most direct approach is to simulate the detonation process starting from every bomb.

For each starting bomb:

1. Determine which bombs are directly reachable.
2. Trigger those bombs.
3. Continue expanding the chain reaction until no new bombs explode.
4. Count how many bombs were detonated.

A naive implementation might repeatedly scan every bomb pair during the simulation instead of precomputing relationships. That would work correctly because every possible chain reaction is explored, but it would perform unnecessary repeated calculations.

The brute-force method is correct because it exhaustively simulates all possible detonations starting from each bomb. However, repeatedly recomputing geometric reachability during traversal is inefficient.

Key Insight

The critical observation is that reachability between bombs does not change during the simulation. Whether bomb i can detonate bomb j depends only on their positions and radius.

Therefore, we can first build a directed graph:

• Node i represents bomb i
• Directed edge i -> j exists if bomb i can detonate bomb j

After constructing the graph, the problem reduces to a standard graph traversal problem. From every node, run either DFS or BFS to count how many nodes are reachable.

Because there are only at most 100 bombs, building the graph with all pair comparisons is efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(n)	Recomputes reachability during every traversal
Optimal	O(n²)	O(n²)	Precompute graph once, then run DFS/BFS from each node

Algorithm Walkthrough

1. Create an adjacency list representing the directed graph.

For every pair of bombs (i, j), determine whether bomb i can detonate bomb j.

Let:

• (xi, yi) be the center of bomb i
• ri be the radius of bomb i
• (xj, yj) be the center of bomb j

Compute the squared distance:

$$(x_i - x_j)^2 + (y_i - y_j)^2$$

If this value is less than or equal to ri², then add a directed edge from i to j.

1. After building the graph, iterate through every bomb as a possible starting point.
2. For each starting bomb, perform a depth-first search.

DFS explores every bomb reachable through chain reactions.

Use a visited set to avoid processing the same bomb multiple times. This prevents infinite loops in cyclic graphs. 3. During DFS:

• Mark the current bomb as visited.
• Recursively visit all neighbors that have not yet been visited.

4. After DFS completes, the size of the visited set represents the total number of detonated bombs for that starting bomb.
5. Track the maximum value across all starting bombs.
6. Return the maximum detonated count.

Why it works

The graph accurately models all direct detonation relationships. A path from bomb A to bomb B means there exists a valid chain reaction that eventually detonates B.

DFS explores exactly the set of bombs reachable from a starting node in a directed graph. Therefore, running DFS from every bomb correctly computes the number of bombs detonated by starting from that bomb. Taking the maximum over all starting bombs gives the optimal answer.

Python Solution

from typing import List

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        n = len(bombs)

        # Build directed graph
        graph = [[] for _ in range(n)]

        for i in range(n):
            xi, yi, ri = bombs[i]

            for j in range(n):
                if i == j:
                    continue

                xj, yj, _ = bombs[j]

                dx = xi - xj
                dy = yi - yj

                distance_squared = dx * dx + dy * dy

                if distance_squared <= ri * ri:
                    graph[i].append(j)

        def dfs(node: int, visited: set[int]) -> int:
            visited.add(node)

            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor, visited)

            return len(visited)

        max_detonated = 0

        for start in range(n):
            visited = set()
            detonated_count = dfs(start, visited)
            max_detonated = max(max_detonated, detonated_count)

        return max_detonated

The implementation begins by constructing the directed graph. Each index corresponds to a bomb, and each adjacency list stores the bombs directly reachable from it.

The nested loops compare every pair of bombs. Instead of using Euclidean distance with square roots, the code compares squared values. This avoids floating point operations and improves numerical safety.

The DFS function recursively explores all bombs reachable from the current node. The visited set ensures each bomb is counted only once, even if cycles exist.

Finally, the algorithm runs DFS starting from every bomb and records the largest reachable count.

Go Solution

func maximumDetonation(bombs [][]int) int {
	n := len(bombs)

	graph := make([][]int, n)

	// Build directed graph
	for i := 0; i < n; i++ {
		xi, yi, ri := bombs[i][0], bombs[i][1], bombs[i][2]

		for j := 0; j < n; j++ {
			if i == j {
				continue
			}

			xj, yj := bombs[j][0], bombs[j][1]

			dx := int64(xi - xj)
			dy := int64(yi - yj)

			distanceSquared := dx*dx + dy*dy
			radiusSquared := int64(ri) * int64(ri)

			if distanceSquared <= radiusSquared {
				graph[i] = append(graph[i], j)
			}
		}
	}

	var dfs func(int, []bool) int

	dfs = func(node int, visited []bool) int {
		visited[node] = true

		count := 1

		for _, neighbor := range graph[node] {
			if !visited[neighbor] {
				count += dfs(neighbor, visited)
			}
		}

		return count
	}

	maxDetonated := 0

	for start := 0; start < n; start++ {
		visited := make([]bool, n)

		detonatedCount := dfs(start, visited)

		if detonatedCount > maxDetonated {
			maxDetonated = detonatedCount
		}
	}

	return maxDetonated
}

The Go implementation follows the same algorithmic structure as the Python solution, but there are several language-specific considerations.

Go integers can overflow if large squared values are stored in standard int arithmetic on some systems. To avoid this, the implementation converts coordinate differences and radius values to int64 before squaring.

Instead of a Python set, Go uses a boolean slice for the visited structure. Since bomb indices range from 0 to n-1, a boolean array is efficient and straightforward.

The DFS function returns the total number of reachable bombs by recursively accumulating counts.

Worked Examples

Example 1

bombs = [[2,1,3],[6,1,4]]

Step 1: Build Graph

From	To	Distance²	Radius²	Edge Exists
0	1	(2-6)² + (1-1)² = 16	9	No
1	0	(6-2)² + (1-1)² = 16	16	Yes

Graph:

0 -> []
1 -> [0]

Step 2: DFS from Bomb 0

Visited progression:

Step	Current Node	Visited
1	0	{0}

Total detonated = 1

Step 3: DFS from Bomb 1

Visited progression:

Step	Current Node	Visited
1	1	{1}
2	0	{0,1}

Total detonated = 2

Maximum = 2

Example 2

bombs = [[1,1,5],[10,10,5]]

Step 1: Build Graph

From	To	Distance²	Radius²	Edge Exists
0	1	162	25	No
1	0	162	25	No

Graph:

0 -> []
1 -> []

Step 2: DFS Traversals

Starting from either bomb only reaches itself.

Start Bomb	Reachable Bombs
0	1
1	1

Maximum = 1

Example 3

bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]

Step 1: Build Graph

The important edges are:

0 -> 1
0 -> 2
2 -> 3
3 -> 4

Step 2: DFS from Bomb 0

Step	Current Node	Visited
1	0	{0}
2	1	{0,1}
3	2	{0,1,2}
4	3	{0,1,2,3}
5	4	{0,1,2,3,4}

Total detonated = 5

No other starting bomb produces a larger result.

Final answer = 5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Building the graph requires comparing every bomb pair, DFS traversals together remain O(n²)
Space	O(n²)	Worst-case adjacency list stores every directed edge

The graph construction phase compares every pair of bombs once, which costs O(n²).

Each DFS traversal visits at most n nodes and traverses at most n² edges overall. Since n <= 100, performing DFS from every node remains efficient.

The adjacency list can contain up to n * (n - 1) directed edges in the worst case, resulting in O(n²) space usage.

Test Cases

from typing import List

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        n = len(bombs)

        graph = [[] for _ in range(n)]

        for i in range(n):
            xi, yi, ri = bombs[i]

            for j in range(n):
                if i == j:
                    continue

                xj, yj, _ = bombs[j]

                dx = xi - xj
                dy = yi - yj

                if dx * dx + dy * dy <= ri * ri:
                    graph[i].append(j)

        def dfs(node, visited):
            visited.add(node)

            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor, visited)

            return len(visited)

        answer = 0

        for i in range(n):
            answer = max(answer, dfs(i, set()))

        return answer

solution = Solution()

assert solution.maximumDetonation([[2,1,3],[6,1,4]]) == 2
# Example 1, directional reachability

assert solution.maximumDetonation([[1,1,5],[10,10,5]]) == 1
# Example 2, disconnected bombs

assert solution.maximumDetonation([[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]) == 5
# Example 3, full chain reaction

assert solution.maximumDetonation([[1,1,100]]) == 1
# Single bomb edge case

assert solution.maximumDetonation([[0,0,10],[1,1,10],[2,2,10]]) == 3
# Fully connected graph

assert solution.maximumDetonation([[0,0,1],[100,100,1],[200,200,1]]) == 1
# No bomb can reach another

assert solution.maximumDetonation([[0,0,5],[3,0,5],[6,0,5]]) == 3
# Linear chain

assert solution.maximumDetonation([[0,0,2],[2,0,2],[4,0,2],[6,0,2]]) == 4
# Exact boundary distance

assert solution.maximumDetonation([
    [0,0,100000],
    [99999,0,1],
    [200000,0,1]
]) == 2
# Large coordinate values

assert solution.maximumDetonation([
    [0,0,5],
    [4,0,5],
    [8,0,5],
    [12,0,5],
    [50,50,1]
]) == 4
# Separate isolated component

Test	Why
[[2,1,3],[6,1,4]]	Validates directional detonation
[[1,1,5],[10,10,5]]	Validates disconnected bombs
Example 3 input	Validates long chain reaction
Single bomb	Smallest valid input
Fully connected bombs	Tests dense graph behavior
Completely isolated bombs	Tests zero connectivity
Linear chain	Tests indirect reachability
Exact boundary case	Ensures <= comparison is correct
Large coordinate values	Tests overflow safety
Mixed connected and isolated bombs	Tests partial graph connectivity

Edge Cases

Single Bomb

When the input contains only one bomb, the answer must be 1 because detonating that bomb only affects itself.

This case can expose bugs in graph traversal implementations that assume at least one outgoing edge exists. The current implementation handles this naturally because DFS visits the starting node before exploring neighbors.

Exact Boundary Reachability

A bomb should detonate another bomb even if the target lies exactly on the edge of its explosion radius.

This is why the implementation uses:

$$distance^2 \le radius^2$$

instead of a strict less-than comparison.

Failing to include equality would incorrectly reject valid detonations.

Cyclic Detonation Chains

Bombs may form cycles. For example:

0 -> 1
1 -> 2
2 -> 0

Without a visited structure, DFS would recurse infinitely.

The implementation avoids this by marking bombs as visited immediately upon entering DFS. Each bomb is processed only once per traversal.

Large Coordinate Values

Coordinates and radii can be as large as 100000. Squaring these values can exceed 32-bit integer limits in some languages.

The Go solution explicitly uses int64 arithmetic before squaring distances and radii. This prevents overflow and guarantees correct geometric comparisons.