You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb.
The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [xi, yi, ri]. xi and yi denote the X-coordinate and Y-coordinate of the location of the ith bomb, whereas ri denotes the radius of its range.
You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range. These bombs will further detonate the bombs that lie in their ranges.
Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb.
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 <= 100bombs[i].length == 31 <= xi, yi, ri <= 105Represent each bomb as a node in a graph. An edge exists from bomb i to bomb j if bomb i can detonate bomb j. The goal is to start from each bomb and use BFS to find how many bombs can be detonated. Return the maximum number of detonatable bombs starting from any single bomb.
This code constructs a graph with each bomb as a node and checks if a bomb can detonate another based on their respective ranges. BFS is used from each bomb to determine the total number of bombs that can be detonated, and the maximum among all is returned.
Java
Time Complexity: O(n^2), where n is the number of bombs, as we need to check each pair of bombs.
Space Complexity: O(n), for storing the adjacency list of the graph and the visited list.
Another approach to solve this problem is by using a DFS traversal instead of BFS. We use a similar graph representation where each bomb is a node and an edge exists if one bomb can detonate another. The maximum number of bombs that can be reached starting from each node (bomb) is determined using DFS.
This C++ implementation uses DFS to explore each detonation starting from every bomb and computes the maximum possible detonations. It uses a recursive function to delve deeper into the graph from each bomb until all reachable bombs are visited starting from a given bomb.
JavaScript
Time Complexity: O(n^2) for constructing the graph and performing DFS traversals.
Space Complexity: O(n) used in the recursion stack and the visited vector.
| Approach | Complexity |
|---|---|
| Graph Representation with BFS | Time Complexity: O(n^2), where n is the number of bombs, as we need to check each pair of bombs. |
| Graph Representation with DFS | Time Complexity: O(n^2) for constructing the graph and performing DFS traversals. |
Detonate the Maximum Bombs - Leetcode 2101 - Python • NeetCodeIO • 15,672 views views
Watch 9 more video solutions →Practice Detonate the Maximum Bombs with our built-in code editor and test cases.
Practice on FleetCode