Sponsored
Sponsored
Represent 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.
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.
1import java.util.*;
2
3class Solution {
4 private boolean canDetonate(int[] bomb1, int[] bomb2) {
5 long x1 = bomb1[0], y1 = bomb1[1], r1 = bomb1[2];
6 long x2 = bomb2[0], y2 = bomb2[1];
7 return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= r1 * r1;
8 }
9
10 public int maximumDetonation(int[][] bombs) {
11 int n = bombs.length;
12 List<Integer>[] graph = new ArrayList[n];
13 for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
14
15 for (int i = 0; i < n; i++) {
16 for (int j = 0; j < n; j++) {
17 if (i != j && canDetonate(bombs[i], bombs[j])) {
18 graph[i].add(j);
19 }
20 }
21 }
22
23 int maxDetonated = 0;
24 for (int i = 0; i < n; i++) {
25 boolean[] visited = new boolean[n];
26 Queue<Integer> queue = new LinkedList<>();
27 queue.offer(i);
28 visited[i] = true;
29 int count = 0;
30
31 while (!queue.isEmpty()) {
32 int current = queue.poll();
33 count++;
34 for (int neighbor : graph[current]) {
35 if (!visited[neighbor]) {
36 visited[neighbor] = true;
37 queue.offer(neighbor);
38 }
39 }
40 }
41 maxDetonated = Math.max(maxDetonated, count);
42 }
43
44 return maxDetonated;
45 }
46}Similar to the Python implementation, this Java version constructs an adjacency list for the graph of bombs and uses BFS to search through the graph from each possible starting bomb. The maximum number of detonatable bombs is computed and returned.
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.
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.
1function canDetonate(bomb1, bomb2) {
2
This JavaScript solution uses a DFS recursive approach to enumerate all bombs that can be detonated starting from one bomb. It iterates over each bomb, employs DFS to count reachable detonations, and stores the maximum value observed.