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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Detonate the Maximum Bombs

Number: 2206

Difficulty: Medium

Paid? No

Companies: Google, Chime, Amazon

Problem Description

Given a list of bombs where each bomb is represented by its (x, y) coordinate and a radius, determine the maximum number of bombs that can be detonated if you start by detonating just one bomb. When a bomb explodes, it detonates all other bombs within its circular range, and these bombs can in turn trigger other bombs, forming a chain reaction.

Key Insights

  • Model the bombs as nodes in a directed graph.
  • There is a directed edge from bomb i to bomb j if bomb j lies within the explosion radius of bomb i.
  • Use DFS or BFS to simulate the chain reaction starting from each bomb.
  • Track visited bombs to avoid processing a bomb more than once during a chain reaction.
  • The final answer is the maximum number of bombs detonated from any initial bomb.

Space and Time Complexity

Time Complexity: O(n^2) for building the graph plus O(n) per DFS/BFS starting from each bomb, resulting in O(n^3) in the worst-case scenario. Given n ≤ 100, this is acceptable. Space Complexity: O(n^2) for storing the graph edges, and O(n) for the recursion/queue during the DFS/BFS.

Solution

We first build a graph where each bomb is a node. We add a directed edge from bomb i to bomb j if the Euclidean distance between them is within bomb i's explosion radius (using squared distances to avoid floating point operations). Afterwards, for each bomb, we simulate the chain reaction using DFS (or BFS) to count the total number of bombs that would detonate. The maximum count among all bombs is the answer.

Code Solutions

# Python solution with line-by-line comments

def max_detonated_bombs(bombs):
    # Number of bombs
    n = len(bombs)
    # Build graph: graph[i] holds list of bombs indices that bomb i can detonate
    graph = [[] for _ in range(n)]
    for i in range(n):
        x_i, y_i, r_i = bombs[i]
        for j in range(n):
            if i == j:
                continue
            x_j, y_j, _ = bombs[j]
            # Calculate the squared distance
            dx = x_i - x_j
            dy = y_i - y_j
            if dx * dx + dy * dy <= r_i * r_i:
                # Bomb i can detonate bomb j
                graph[i].append(j)

    # DFS helper function to count detonated bombs starting from a bomb index
    def dfs(start, visited):
        count = 1  # count the current bomb
        visited.add(start)
        for neighbor in graph[start]:
            if neighbor not in visited:
                count += dfs(neighbor, visited)
        return count

    max_count = 0
    # Try detonating each bomb as the starting bomb
    for i in range(n):
        visited = set()
        max_count = max(max_count, dfs(i, visited))
    return max_count

# Example usage:
bombs_example = [[2,1,3],[6,1,4]]
print(max_detonated_bombs(bombs_example))  # Expected output: 2
← Back to All Questions