🏆 Detailed Explanation 🏆 ( DFS ) with time and space complexity analysis.
Approach\n Describe your approach to solving the problem. \nBasic idea is to solve this problem is we are considering n bombs from 0 to n-1. We treat this indiv
# Approach\n<!-- Describe your approach to solving the problem. -->\nBasic idea is to solve this problem is we are considering n bombs from 0 to n-1. We treat this individuals bomb as node in the graph. If a bomb can reach to the other bombs it means if bomb radius can cover any other bomb then there should be directed edge between this bombs. We need to do this for each bomb and we created graph.\n\nNow the next question is how do we know that one bomb can cover the other bomn in it radius. So for two bomb if we want to find distance we use this equation:\n$$ d = \\sqrt{(x_2 - x_1)^2 + (y_2-y_1)^2}$$\n\nwe need to check that if distance is less then the radius of bomb then it can reach to the other bomb.\n\n$$\nd<=r,\n$$\n$$\nd^2  = (x_2 - x_1)^2 + (y_2-y_1)^2\n$$\n$$\nd^2  <= r^2  \n$$ if this condition is true it means bombs can detonate other bomb.\n\n# Code\n```\nclass Solution {\n    public int maximumDetonation(int[][] bombs) {\n        int n = bombs.length;\n\n        // Create the adjacency list representation of the graph\n        List<List<Integer>> adjList = createGraph(bombs);\n\n        // Array to track visited nodes during DFS\n        boolean[] vis = new boolean[n];\n\n        // Array to keep track of the detonation count\n        int[] count = new int[1];\n\n        // Variable to store the maximum detonation count\n        int maxValue = Integer.MIN_VALUE;\n\n        // Perform DFS starting from each node to find the detonation count\n        for(int node = 0; node < n; node++){\n            Arrays.fill(vis, false); // Reset the visited array for each DFS\n            count[0] = 0; // Reset the detonation count for each DFS\n            dfs(node, adjList, vis, count); // Perform DFS\n            maxValue = Math.max(maxValue, count[0]); // Update the maximum detonation count\n        }\n\n        return maxValue; // Return the maximum detonation count\n    }\n\n    // Depth-First Search (DFS) implementation\n    public void dfs(int node, List<List<Integer>> adjList, boolean[] vis, int count[]){\n        vis[node] = true; // Mark the current node as visited\n        count[0]++; // Increment the detonation count for the current node\n\n        // Iterate through the adjacent nodes of the current node\n        for(Integer adjNode : adjList.get(node)){\n            if(!vis[adjNode]){ // If the adjacent node is not visited\n                dfs(adjNode, adjList, vis, count); // Recursively perform DFS on the adjacent node\n            }\n        }\n    }\n\n    // Create the adjacency list representation of the graph\n    public List<List<Integer>> createGraph(int[][] bombs){\n        int n = bombs.length;\n        List<List<Integer>> adjList = new ArrayList<>(n);\n\n        // Iterate through each node in the graph\n        for(int node = 0; node < n; node++){\n            adjList.add(new ArrayList<>()); // Create an empty list for the current node\n            long x1 = bombs[node][0]; // x-coordinate of the current node\n            long y1 = bombs[node][1]; // y-coordinate of the current node\n            long r1 = bombs[node][2]; // radius of the current node\n\n            // Iterate through each other node in the graph\n            for(int otherNode = 0; otherNode < n; otherNode++){\n                if(node != otherNode){ // If the other node is not the current node\n                    long x2 = bombs[otherNode][0]; // x-coordinate of the other node\n                    long y2 = bombs[otherNode][1]; // y-coordinate of the other node\n\n                    long X = Math.abs(x1 - x2); // Absolute difference in x-coordinates\n                    long Y = Math.abs(y1 - y2); // Absolute difference in y-coordinates\n\n                    if(X * X + Y * Y <= r1 * r1){ // If the distance between the nodes is within the radius\n                        adjList.get(node).add(otherNode); // Add the other node to the adjacency list of the current node\n                    }\n                }\n            }\n        }\n\n        return adjList; // Return the adjacency list\n    }\n}\n\n```\n\n# Complexity\n### Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- The **createGraph** method iterates over each bomb and compares it to every other bomb to see if it is within the explosion radius, creating the adjacency list. Due to the two nested loops involved, O(N^2) comparisons are produced. As a result, the adjacency list generation takes O(N^2) time, where N is the total number of bombs.\n\n- **DFS traversal:** For each bomb in the graph, we do a DFS traversal in the main maximumDetonation procedure. We just make one trip to each node during each traverse. The total number of iterations required for the DFS traversal is O(N) since each node can have a maximum of N-1 connections (apart from those to itself).\n\n- Therefore, the overall time complexity of the solution is O(N^2 + N^2), which simplifies to **O(N^2)**.\n\n### Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n- The number of bombs, N, determines the solution\'s O(N) space complexity. This is because the connections between each bomb must be stored because we describe the graph as an adjacency list. The area needed would be inversely correlated to the number of explosives in the worst-case scenario, when all bombs are connected to one another.\n\n## Please upvote if you find it useful.\n\nif anything wrong please feel free to comment down.
['Array', 'Math', 'Depth-First Search', 'Graph', 'Java']