Detonate the Maximum Bombs

Problem Statement

In this problem, you are given a list of bombs represented as a 0-indexed 2D integer array, bombs, where each element bombs[i] consists of three integers [xi, yi, ri]. These integers represent the coordinates (xi, yi) and the detonation range radius (ri) of the ith bomb. The detonation range of each bomb is a circle centered at its coordinates with radius corresponding to ri.

You are tasked to find out the maximum number of bombs that can be set off by detonating just one bomb initially. Detonating one bomb can potentially trigger a chain reaction where any bomb falling within the range of the explosion will also detonate. This recursive detonation process continues until no more bombs are affected by the last detonated bomb.

Your goal is to determine the maximum number of bombs that can be detonated starting with the detonation of only one bomb.

Examples

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

Approach and Intuition

To approach this problem, you'll want to simulate the chain reaction set off by detonating each bomb. Here's the intuition and plan to tackle this:

1. Understand how to determine if one bomb can trigger another:

   • Using the formula for Euclidean distance, distance = sqrt((x2 - x1)^2 + (y2 - y1)^2), check if the distance between two bombs is less than or equal to the radius of the bomb being detonated. This ensures that the second bomb is within the explosive range of the first.

2. Use Depth-First Search (DFS) or Breadth-First Search (BFS) to simulate the chain reaction:

   • For each bomb, treat the situation as a graph traversal problem where nodes are bombs and edges exist between nodes if one bomb can trigger the other.
   • Implement DFS or BFS starting from each bomb as the root node. The traversal will count how many bombs get detonated as it visits nodes/bombs recursively or iteratively.

3. Store and update the maximum number of bombs detonated:

   • As you compute the total bombs detonated by starting with each individual bomb, keep track of and update the maximum number encountered.

This method leverages graph theory concepts and ensures that every possibility is explored to find the optimal solution. Remember to consider edge cases, such as bombs that do not interact with any others, as seen in the examples provided. Each bomb, at a minimum, will detonate itself, hence the result should always be at least one.

Solutions

class Solution {
    public int maxDetonations(int[][] bombs) {
        Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
        int bombCount = bombs.length;
    
        // Building the adjacency list for each bomb
        for (int i = 0; i < bombCount; i++) {
            for (int j = 0; j < bombCount; j++) {
                int xi = bombs[i][0], yi = bombs[i][1], radius = bombs[i][2];
                int xj = bombs[j][0], yj = bombs[j][1];
                    
                // Checking detonation condition
                if ((long)radius * radius >= (long)(xi - xj) * (xi - xj) + (long)(yi - yj) * (yi - yj)) {
                    adjacencyList.computeIfAbsent(i, k -> new ArrayList<>()).add(j);
                }
            }
        }
            
        int maxDetonations = 0;
        for (int i = 0; i < bombCount; i++) {
            maxDetonations = Math.max(maxDetonations, performBFS(i, adjacencyList));
        }
            
        return maxDetonations;
    }
        
    private int performBFS(int start, Map<Integer, List<Integer>> adjacencyList) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> seen = new HashSet<>();
        queue.add(start);
        seen.add(start);
            
        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int neighbor : adjacencyList.getOrDefault(current, new ArrayList<>())) {
                if (!seen.contains(neighbor)) {
                    seen.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
        return seen.size();
    }
}