Java Solution for Detonate the Maximum Bombs Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe given problem involves finding the maximum number of bombs that can be detonated by
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe given problem involves finding the maximum number of bombs that can be detonated by choosing a single bomb. To solve this, we can represent the bombs as a graph, where each bomb is a node and there is an edge between two bombs if one can detonate the other. By using graph traversal techniques, such as Breadth-First Search (BFS), we can find the maximum number of detonated bombs.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Build the graph: Iterate over each pair of bombs and check if one bomb can detonate the other. If so, create a directed edge from the first bomb to the second bomb in the graph.\n1. Perform BFS: Iterate over each bomb and perform a BFS traversal starting from that bomb. Count the number of visited nodes during the traversal, which represents the number of detonated bombs.\n1. Update the maximum count: Keep track of the maximum detonated count encountered during the BFS traversal.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of building the graph is O(n^2) since we iterate over each pair of bombs. The BFS traversal is performed for each bomb, which has a time complexity of O(n + m), where n is the number of nodes (bombs) and m is the number of edges in the graph. In the worst case, the number of edges can be O(n^2), resulting in a time complexity of O(n^3). However, on average, the number of edges tends to be much smaller, resulting in an average time complexity closer to O(n^2).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is O(n^2) to store the graph using a HashMap, where n is the number of bombs. Additionally, the BFS traversal requires O(n) space for the queue and O(n) space for the visited set, resulting in a total space complexity of O(n^2 + n + n) = O(n^2).\n\n# Code\n```\nclass Solution {\n    public int maximumDetonation(int[][] bombs) {\n        Map<Integer, List<Integer>> graph = new HashMap<>();\n        int n = bombs.length;\n        \n        // Build the graph\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                int xi = bombs[i][0], yi = bombs[i][1], ri = bombs[i][2];\n                int xj = bombs[j][0], yj = bombs[j][1];\n                \n                // Create a path from node i to node j, if bomb i detonates bomb j.\n                if ((long)ri * ri >= (long)(xi - xj) * (xi - xj) + (long)(yi - yj) * (yi - yj)) {\n                    graph.computeIfAbsent(i, k -> new ArrayList<>()).add(j);\n                }\n            }\n        }\n        \n        int answer = 0;\n        for (int i = 0; i < n; i++) {\n            answer = Math.max(answer, bfs(i, graph));\n        }\n        \n        return answer;\n    }\n    \n    private int bfs(int i, Map<Integer, List<Integer>> graph) {\n        Deque<Integer> queue = new ArrayDeque<>();\n        Set<Integer> visited = new HashSet<>();\n        queue.offer(i);\n        visited.add(i);\n        while (!queue.isEmpty()) {\n            int cur = queue.poll();\n            for (int neib : graph.getOrDefault(cur, new ArrayList<>())) {\n                if (!visited.contains(neib)) {\n                    visited.add(neib);\n                    queue.offer(neib);\n                }\n            }\n        }\n        return visited.size();\n    }\n}\n```
['Java']