< Back





2101. Detonate the Maximum Bombs

Given an array of bombs, specified [x, y, r] where (x, y) is the position of the bomb on a 2D plane
and r is the blast radius, we need to determine the maximum number of bombs we can detonate if we
detonated 1 bomb. Pretty tricky but fun problem. Intuitively, we're going to use DFS to detonate
each bomb, traversing their "edges" - bombs that are exploded by the current bomb based on blast
radius.

The biggest trick to this question is pre-processing the input to create a graph. We create edges
between the bombs by using the Python math.dist() function to calcualte the Euclidean distance
between the two bombs - if the radius of the exploding bomb is greater than or equal to the distance
between the two bombs, we create an edge between the two bombs.

We then use DFS like we always do for every bomb in the input, maximizing the number of bombs we
can detonate.

The solution is as follows:


  from collections import defaultdict
  from math import dist

  class Solution:
      def maximumDetonation(self, bombs: List[List[int]]) -> int:
          n = len(bombs)
          graph = defaultdict(list)

          def dfs(start: int) -> int:
              seen = {start}
              stack = [start]

              while stack:
                  bomb = stack.pop()

                  for neighbor in graph[bomb]:
                      if neighbor not in seen:
                          seen.add(neighbor)
                          stack.append(neighbor)

              return len(seen)

          for i in range(n):
              for j in range(n):
                  x, y, r = bombs[i]
                  l, m, _ = bombs[j]

                  if r >= dist((x, y), (l, m)):
                      graph[i].append(j)

          ans = float("-inf")
          for k in range(n):
              ans = max(ans, dfs(k))

          return ans


_ Time Complexity:

  O(n^3) - The time complexity of DFS is O(V + E), and we execute DFS O(n) times.

_ Space Complexity:

  O(n^2) - We create a graph of the edges between the bombs.