2101. Detonate the Maximum Bombs

#graph #bfs #dfs #geometry

Problem

Detonate the Maximum Bombs - LeetCodeLeetCode

Intuition

We need to break the problem into two parts

• Building graph

• Performing traversal(BFS/DFS) to find number of bombs that can be detonated

Here the detonated means the point (x, y) should lie inside the blast radius

Time Complexity

Time complexity: $O(n^2)$

• Building graph -> $O(n^2)$

• Traversal of graph -> $O(n^2)$

Total Time Complexity = Building graph + Traversal of graph

= $O(n^2)$ + $O(n^2)$ = 2 * $O(n^2)$ = $O(n^2)$

Space Complexity

Space complexity: O(n)

• Space taken by Hashmap for storing neighbours =

• Hashset to make traversal are O(n)

Total Space Complexity = HashMap + Hashset

= $O(n)$ + $O(n)$ = 2 * $O(n)$ = $O(n)$

Solution

class Solution {
    public int maximumDetonation(int[][] bombs) {
        // n -> number of bombs / bombs.length
        // Time complexity: O(n^2)
        // The time complexity for building graph and performing traversal(both DFS and BFS) is 
        // O(n^2), so it is 
        // O(n^2) (buildgraph) + O(n^2) (perform traversal) = 2 * O(n^2) = O(n^2)
        // Space complexity: O(n)
        // Space taken by Hashmap for storing neighbors and hashset to make traversal are O(n)
        // So it is O(n) (buildgraph) + O(n) (traversal) = 2 * O(n) = O(n)
        Map<Integer, List<Integer>> map = buildGraph(bombs);

        int maxCount = 0;
        for(int startBomb = 0;startBomb < bombs.length;startBomb++) {
            // int count = bombsThatCanBeDetonated(startBomb, map); // BFS implementation
            int count = dfs(startBomb, map, new HashSet<>()); // DFS implementation
            maxCount = Math.max(maxCount, count);

        }
        return maxCount;
    }

    private Map<Integer, List<Integer>> buildGraph(int[][] bombs) {
        Map<Integer, List<Integer>> map = new HashMap<>();

        for(int i=0;i<bombs.length;i++) {
            List<Integer> neighbors = new ArrayList<>();
            
            long x = bombs[i][0];
            long y = bombs[i][1];
            long r = bombs[i][2];

            for(int j=0;j<bombs.length;j++) {
                if(i != j) {
                    long dx = x - bombs[j][0];
                    long dy = y - bombs[j][1];

                    // Using Eucledian distance to find if the "j" bomb is in the blast
                    // range of "i" bomb
                    if((dx*dx) + (dy*dy) <= r*r) {
                        neighbors.add(j);
                    }
                }    
            }
            map.put(i, neighbors);
        }
        return map;
    }

    private int dfs(int bomb, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
        // Mark the current bomb visited
        visited.add(bomb);
        int count = 1; // Initialise the count to 1 for current bomb

        // Traverse through the graph
        for (int neighbor : graph.get(bomb)) { 
            if (!visited.contains(neighbor)) { // If the neighbor is not visited/processed
                count += dfs(neighbor, graph, visited); // Add to the count of neighbor
            }
        }

        return count;
    }

    private int bombsThatCanBeDetonated(int startBomb, Map<Integer, List<Integer>> graph) {
        Deque<Integer> queue = new ArrayDeque<>(); 
        queue.offer(startBomb);
        Set<Integer> reachable = new HashSet<>();
        reachable.add(startBomb); // The current bomb is reachable by itself, so it is added

        // Standard BFS implementation
        while(!queue.isEmpty()) {
            int size = queue.size();

           for(int i=0;i<size;i++) {
                int bomb = queue.poll();

                for(int neighbor: graph.get(bomb)) {
                    if(!reachable.contains(neighbor)) {
                        queue.add(neighbor); // Adding to queue for processing
                        reachable.add(neighbor); // Adding to reachable to know if its in range
                    }
                }
            }
        }
        return reachable.size();
    }
}