We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Detonate the Maximum Bombs

Difficulty: Medium

Problem Description

You are given a list of bombs represented by a 2D integer array where each bomb has a location and a radius. When a bomb is detonated, it can trigger other bombs within its range. Your task is to determine the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb.

Key Insights

  • Each bomb can be represented as a circle defined by its center coordinates and radius.
  • A bomb will detonate another bomb if the distance between them is less than or equal to the sum of their radii.
  • The problem can be represented as a graph where bombs are nodes and edges represent the ability to trigger other bombs.

Space and Time Complexity

Time Complexity: O(N^2) - We need to check every pair of bombs to see if one can trigger another. Space Complexity: O(N) - To store the adjacency list for the bombs.

Solution

To solve this problem, we can use a graph traversal algorithm. We'll represent the bombs as nodes in a graph and create edges based on whether one bomb can trigger another. We can then perform a depth-first search (DFS) or breadth-first search (BFS) from each bomb to count how many bombs can be triggered starting from that bomb. The maximum count from all starting points will be our answer.

  1. Create an adjacency list to represent which bombs can trigger which other bombs.
  2. For each bomb, use DFS or BFS to explore and count all reachable bombs.
  3. Keep track of the maximum count of detonated bombs.

Code Solutions

def maxDetonatedBombs(bombs):
    from math import sqrt
    
    def canDetonate(b1, b2):
        x1, y1, r1 = b1
        x2, y2, _ = b2
        return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2) <= r1

    # Build the graph
    n = len(bombs)
    graph = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i != j and canDetonate(bombs[i], bombs[j]):
                graph[i].append(j)

    # DFS function to count detonated bombs
    def dfs(bomb_index, visited):
        visited.add(bomb_index)
        count = 1  # Count the current bomb
        for neighbor in graph[bomb_index]:
            if neighbor not in visited:
                count += dfs(neighbor, visited)
        return count

    max_bombs = 0
    for i in range(n):
        visited = set()
        max_bombs = max(max_bombs, dfs(i, visited))

    return max_bombs
← Back to All Questions