2101. Detonate the Maximum Bombs

MediumDepth-First SearchBreadth-First SearchGraphGeometryArrayMath
Leetcode Link

Problem Description

The problem revolves around a scenario where you have a list of bombs, each with its own location (X and Y coordinates) and a radius that represents the range of its explosion. When a bomb explodes, any bombs within its explosion range will also explode. This chain reaction can lead to a cascade of exploding bombs.

The challenge here is to figure out the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb to start the chain reaction.

The primary task is to detect connections between bombsโ€”understanding which bombs can trigger the explosion of other bombsโ€”and then finding the optimal starting point that results in the highest number of detonations in the chain reaction.

Intuition

To solve this problem, we need to find relationships between bombsโ€”specifically, which bombs can cause others to explode. This is akin to creating a graph where each node is a bomb, and there is a directed edge from one bomb to another if the second bomb is within the first bomb's blast radius.

We can approach the solution by creating such a graph and then using Breadth-First Search (BFS) to simulate the explosion of bombs one by one from a starting bomb. The BFS approach is well-suited here because it allows us to explore all possible chains of detonations level by level, ensuring we count all bombs reachable from the starting bomb.

To explore these chains efficiently, we check for each bomb whether it can trigger other bombs and maintain a list of such connections. Then, for each bomb chosen as the starting point, we apply BFS to count how many bombs would be detonated if we were to start from that bomb. While traversing the graph, we also maintain a visitation status to ensure we do not count any bomb more than once.

Finally, we keep track of the maximum number of detonations from each starting point, and return the highest count as our answer. This approach allows us to consider all possibilities and find the most explosive starting bomb, so to speak.

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

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of the following array represent a max heap?

Solution Approach

The solution provided uses Breadth-First Search (BFS) to traverse the graph constructed from the bombs' connections. Here's a step-by-step breakdown of the implementation:

Data Structures and Algorithm:

  • Graph Representation: A dictionary g is used to represent the graph where each key is a bomb index, and the associated value is a list of indices of bombs that can be triggered by this bomb.

  • Helper Function (check): A function is defined to determine whether bomb j is within the range of bomb i. This is done by calculating the Euclidean distance between the bombs and comparing it to the radius of bomb i.

  • Graph Construction: Two nested loops iterate over all pairs of bombs, and the check function is used to establish the graph's edges, which represent reachable bombs within explosion range.

  • BFS Traversal: For each bomb k, we perform a BFS starting from k. A queue q and a visitation list vis are maintained. The queue is initialized with the starting bomb, k, and its corresponding visitation status is marked as True.

  • Counting Detonations: While the queue is not empty, bombs are dequeed one by one, each time incrementing a counter cnt. For every dequeued bomb i, we enqueue all unvisited bombs that can be triggered by bomb i based on the graph g, marking them as visited to prevent repeated counting.

  • Finding the Maximum: A variable ans keeps track of the maximum number of detonations. After each BFS traversal for a starting bomb k, the counter cnt is compared with ans and updated if it is larger.

BFS in Action:

BFS is an ideal choice for this problem because it ensures that all bombs that can be detonated by one bomb are exhausted before moving to bombs that they trigger. This level-by-level approach guarantees we account for all potential detonations in the sequence they would occur in reality.

Final Result:

After iterating over each bomb as a potential starting point and performing the BFS traversal, the value of ans at the end of iteration would be the maximum number of bombs that can be detonated by triggering just one bomb. This value is then returned as the final answer.

The use of the BFS algorithm and data structures such as the graph (dictionary), queue (deque), and the visitation list (vis) forms the backbone of this solution, allowing effective simulation and counting of the resulting explosions.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Example Walkthrough

To illustrate the solution approach, let's assume we have the following small set of bombs:

  • Bomb A at (0,0) with a radius of 3
  • Bomb B at (4,0) with a radius of 2
  • Bomb C at (2,2) with a radius of 3
  • Bomb D at (6,1) with a radius of 2

We want to see which bomb to start with to detonate the most bombs in total.

Step 1: Create the Graph First, we represent the bombs as nodes in a graph. To establish directed edges, we calculate if one bomb is within the explosion radius of another by using the Euclidean distance formula. For instance, to check if bomb B is within the radius of bomb A, we calculate the distance between (0,0) and (4,0), which is 4. Since 4 is greater than bomb A's radius, bomb A cannot trigger bomb B.

After checking all pairs, our graph (let's call it g) might look something like this:

  • A: [C] because bomb A can trigger bomb C which is in its radius.
  • B: [] because bomb B cannot trigger any other bombs.
  • C: [A, D] because bomb C can trigger both A and D.
  • D: [] because bomb D cannot trigger any other bombs.

Step 2: Perform BFS We then perform BFS starting from each bomb:

  • For bomb A:
    • We visit bomb C since it's reachable, so our count cnt for A's chain is 2 (including A itself).
  • For bomb B:
    • No other bombs can be triggered, so the count is 1.
  • For bomb C:
    • We visit bomb A and from A we can visit bomb C itself again, but it's already been counted. We also visit bomb D. Thus, cnt for C's chain is 3 (including C itself).
  • For bomb D:
    • No other bombs can be triggered, so the count is 1.

Step 3: Find the Maximum Finally, we find the maximum of our counts:

  • Maximum detonations are 3, starting with bomb C which causes a chain reaction A->C->D.

This is the final result for this example. The number of bombs that can be detonated by triggering just one bomb, in this case, is three when starting with bomb C.

Solution Implementation

1from collections import defaultdict, deque
2from typing import List
3
4class Solution:
5    def maximumDetonation(self, bombs: List[List[int]]) -> int:
6        # Helper function to check if bomb j is in range of bomb i
7        def in_detonation_range(i, j):
8            if i == j:
9                return False
10            delta_x, delta_y = bombs[i][0] - bombs[j][0], bombs[i][1] - bombs[j][1]
11            radius = bombs[i][2]
12            return radius * radius >= delta_x * delta_x + delta_y * delta_y
13
14        # Initialize a graph to store detonation adjacency
15        detonation_graph = defaultdict(list)
16        num_bombs = len(bombs)
17      
18        # Create adjacency list for the graph
19        for i in range(num_bombs):
20            for j in range(num_bombs):
21                if in_detonation_range(i, j):
22                    detonation_graph[i].append(j)
23
24        max_detonations = 0
25        # Check every bomb to get the maximum number of detonations
26        for bomb_index in range(num_bombs):
27            queue = deque([bomb_index])
28            visited = [False] * num_bombs
29            visited[bomb_index] = True
30            current_detonations = 0
31            while queue:
32                current_bomb = queue.popleft()
33                current_detonations += 1
34                # Enqueue all bombs that can be detonated by the current bomb
35                for adjacent in detonation_graph[current_bomb]:
36                    if not visited[adjacent]:
37                        visited[adjacent] = True
38                        queue.append(adjacent)
39            max_detonations = max(max_detonations, current_detonations)
40      
41        return max_detonations
42
1class Solution {
2    // Globally store the input bomb coordinates and radii
3    private int[][] bombs;
4
5    public int maximumDetonation(int[][] bombs) {
6        this.bombs = bombs;
7        int n = bombs.length;
8
9        // Generate a graph where g[i][j] is true if bomb i can trigger bomb j
10        boolean[][] graph = new boolean[n][n];
11        for (int i = 0; i < n; ++i) {
12            for (int j = 0; j < n; ++j) {
13                graph[i][j] = canTrigger(i, j);
14            }
15        }
16
17        // The maximum number of bombs that can be detonated by triggering one bomb
18        int maxDetonations = 0;
19
20        // Iterate over all bombs to find the starting bomb for the chain reaction
21        for (int startBomb = 0; startBomb < n; ++startBomb) {
22            Deque<Integer> queue = new ArrayDeque<>();
23            queue.offer(startBomb);
24          
25            // Track visited bombs to avoid infinite loops in the chain reaction
26            boolean[] visited = new boolean[n];
27            visited[startBomb] = true;
28            int detonatedCount = 0;
29        
30            // BFS to simulate a chain reaction starting from the current bomb
31            while (!queue.isEmpty()) {
32                int currentBomb = queue.poll();
33                ++detonatedCount;
34              
35                // Check all reachable bombs that have not yet been visited/detonated
36                for (int nextBomb = 0; nextBomb < n; ++nextBomb) {
37                    if (graph[currentBomb][nextBomb] && !visited[nextBomb]) {
38                        visited[nextBomb] = true;
39                        queue.offer(nextBomb);
40                    }
41                }
42            }
43        
44            // Record the maximum number of detonations achieved
45            maxDetonations = Math.max(maxDetonations, detonatedCount);
46        }
47
48        return maxDetonations;
49    }
50
51    // Helper function to determine if bomb i can trigger bomb j
52    private boolean canTrigger(int i, int j) {
53        // No bomb can trigger itself
54        if (i == j) {
55            return false;
56        }
57
58        // Calculate the squared distance between bomb i and bomb j
59        long deltaX = bombs[i][0] - bombs[j][0];
60        long deltaY = bombs[i][1] - bombs[j][1];
61        long radiusSquared = (long) bombs[i][2] * bombs[i][2];
62
63        // If the squared distance is less than or equal to the squared bomb radius,
64        // then bomb i can trigger bomb j
65        return radiusSquared >= deltaX * deltaX + deltaY * deltaY;
66    }
67}
68
1class Solution {
2public:
3    int maximumDetonation(vector<vector<int>>& bombs) {
4        int bombCount = bombs.size(); // Number of bombs.
5        // Creating a 2D grid to represent the reachability of one bomb from another.
6        vector<vector<bool>> graph(bombCount, vector<bool>(bombCount));
7
8        // Filling the grid with reachability information.
9        for (int i = 0; i < bombCount; ++i) {
10            for (int j = 0; j < bombCount; ++j) {
11                graph[i][j] = checkDetonationRange(i, j, bombs);
12            }
13        }
14
15        int maxDetonations = 0; // Variable to store the maximum number of detonations.
16
17        // Trying to start the chain reaction from each bomb.
18        for (int startBombIdx = 0; startBombIdx < bombCount; ++startBombIdx) {
19            queue<int> toDetonate; // A queue to manage the chain reaction of bombs.
20            toDetonate.push(startBombIdx);
21            vector<bool> visited(bombCount); // Vector to track visited bombs.
22            visited[startBombIdx] = true;
23            int detonationsCount = 0; // Counter for the number of bombs detonated in the chain.
24
25            // Process the queue until all reachable bombs have detonated.
26            while (!toDetonate.empty()) {
27                int currentBombIdx = toDetonate.front();
28                toDetonate.pop();
29                ++detonationsCount;
30
31                // Check all other bombs to see if they can be reached by the current bomb.
32                for (int nextBombIdx = 0; nextBombIdx < bombCount; ++nextBombIdx) {
33                    // If the next bomb can be detonated and has not yet been visited...
34                    if (graph[currentBombIdx][nextBombIdx] && !visited[nextBombIdx]) {
35                        visited[nextBombIdx] = true; // Mark it as visited.
36                        toDetonate.push(nextBombIdx); // And add it to the queue to detonate.
37                    }
38                }
39            }
40            // Update the maximum number of detonations if this chain reaction is the biggest so far.
41            maxDetonations = max(maxDetonations, detonationsCount);
42        }
43        return maxDetonations; // Return the maximum number of detonations found.
44    }
45
46    // Function to check if bomb 'i' can detonate bomb 'j' based on distance and radius.
47    bool checkDetonationRange(int i, int j, vector<vector<int>>& bombs) {
48        if (i == j) return false; // A bomb cannot detonate itself.
49        long long xDistance = bombs[i][0] - bombs[j][0]; // Horizontal distance between bombs.
50        long long yDistance = bombs[i][1] - bombs[j][1]; // Vertical distance between bombs.
51        long long radius = bombs[i][2]; // Radius of bomb 'i'.
52        // If the squared distance is less than or equal to the squared radius, 'i' can detonate 'j'.
53        return radius * radius >= xDistance * xDistance + yDistance * yDistance;
54    }
55};
56
1type Bomb = [number, number, number]; // Define a tuple type for a bomb (x coordinate, y coordinate, radius)
2
3let bombCount: number; // Number of bombs
4let graph: boolean[][]; // 2D array to represent the reachability of bombs from each other
5
6// Function to initialize the graph based on bomb reachability
7function initializeGraph(bombs: Bomb[]): void {
8    bombCount = bombs.length;
9    graph = Array.from({length: bombCount}, () => Array(bombCount).fill(false));
10
11    for (let i = 0; i < bombCount; ++i) {
12        for (let j = 0; j < bombCount; ++j) {
13            graph[i][j] = checkDetonationRange(i, j, bombs);
14        }
15    }
16}
17
18// Function to calculate the maximum number of detonations that can be achieved from any bomb
19function maximumDetonation(bombs: Bomb[]): number {
20    initializeGraph(bombs);
21    let maxDetonations: number = 0;
22
23    for (let startBombIdx = 0; startBombIdx < bombCount; ++startBombIdx) {
24        let toDetonate: number[] = [];
25        toDetonate.push(startBombIdx);
26        let visited: boolean[] = new Array(bombCount).fill(false);
27        visited[startBombIdx] = true;
28        let detonationsCount: number = 0;
29
30        while (toDetonate.length > 0) {
31            let currentBombIdx: number = toDetonate.shift()!; // Assume the array is not empty
32            ++detonationsCount;
33
34            for (let nextBombIdx = 0; nextBombIdx < bombCount; ++nextBombIdx) {
35                if (graph[currentBombIdx][nextBombIdx] && !visited[nextBombIdx]) {
36                    visited[nextBombIdx] = true;
37                    toDetonate.push(nextBombIdx);
38                }
39            }
40        }
41        maxDetonations = Math.max(maxDetonations, detonationsCount);
42    }
43    return maxDetonations;
44}
45
46// Function to check if bomb 'i' can detonate bomb 'j' based on their distance and the radius of bomb 'i'
47function checkDetonationRange(i: number, j: number, bombs: Bomb[]): boolean {
48    if (i === j) return false; // A bomb cannot detonate itself
49  
50    let [x1, y1, r] = bombs[i]; // Destructure to get the x, y coordinate and radius of bomb i
51    let [x2, y2] = bombs[j]; // Destructure to get the x, y coordinate of bomb j
52    let xDistance = x1 - x2;
53    let yDistance = y1 - y2;
54  
55    // Compare the squared distance with the squared radius to determine reachability
56    return r ** 2 >= xDistance ** 2 + yDistance ** 2;
57}
58
Not Sure What to Study? Take the 2-min Quiz๏ผš

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Time and Space Complexity

The given Python code defines a Solution class with a method maximumDetonation that computes the largest number of bombs that can be detonated by a single bomb. It involves graph theory concepts where each bomb is a node in the graph, and there is an edge from bomb i to bomb j if bomb i can detonate bomb j. Below is the analysis of time and space complexity:

Time Complexity

  1. The check function checks whether bomb i can detonate bomb j. It runs in constant time, O(1), as it performs a few arithmetic operations and a comparison.
  2. The main part of the code initializes a directed graph g using adjacency lists, which is essentially a dictionary with each bomb's index mapping to a list of other bomb indices it can detonate. The double for loop constructs the graph and runs in O(n^2) time, where n is the total number of bombs.
  3. For each bomb k, the code performs a Breadth-First Search (BFS) to find all bombs that can be detonated, starting with bomb k. The BFS for each bomb can visit every other bomb and edge at most once, leading to a time complexity of O(n + e), where e is the number of edges in the graph.
  4. Since the graph is dense, and in the worst case each bomb can detonate every other bomb, e can be O(n^2). So the complexity for each BFS becomes O(n^2).
  5. The outer loop runs BFS for each bomb, so we multiply the complexity of BFS by the number of bombs to get O(n^3).

Therefore, the overall time complexity of the code is O(n^2) + O(n) * O(n^2), which simplifies to O(n^3).

Space Complexity

  1. The graph g can hold up to n^2 edges if every bomb can detonate every other bomb, so it requires O(n^2) space.
  2. The vis array is of size n, used during each BFS to keep track of the visited bombs, resulting in O(n) space.
  3. The BFS queue q could, in the worst case, hold all bombs if they were all interconnected in a way that allows sequential detonation. This also would take O(n) space.
  4. Counting the space used by ans and other variables would only add a constant amount of space, O(1).

In summary, the space complexity is dominated by the graph's size, so the overall space complexity is O(n^2).

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

Fast Track Your Learning with Our Quick Skills Quiz:

How does merge sort divide the problem into subproblems?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ