Leetcode #2101: Detonate the Maximum Bombs
In this guide, we solve Leetcode #2101 Detonate the Maximum Bombs in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt.
Quick Facts
- Difficulty: Medium
- Premium: No
- Tags: Depth-First Search, Breadth-First Search, Graph, Geometry, Array, Math
Intuition
The data forms a graph, so we should explore nodes and edges systematically.
A traversal ensures we visit each node once while maintaining the needed state.
Approach
Build an adjacency list and traverse with BFS or DFS.
Aggregate results as you visit nodes.
Steps:
- Build the graph.
- Traverse with BFS/DFS.
- Accumulate the required output.
Example
Input: bombs = [[2,1,3],[6,1,4]]
Output: 2
Explanation:
The above figure shows the positions and ranges of the 2 bombs.
If we detonate the left bomb, the right bomb will not be affected.
But if we detonate the right bomb, both bombs will be detonated.
So the maximum bombs that can be detonated is max(1, 2) = 2.
Python Solution
class Solution:
def maximumDetonation(self, bombs: List[List[int]]) -> int:
n = len(bombs)
g = [[] for _ in range(n)]
for i in range(n - 1):
x1, y1, r1 = bombs[i]
for j in range(i + 1, n):
x2, y2, r2 = bombs[j]
dist = hypot(x1 - x2, y1 - y2)
if dist <= r1:
g[i].append(j)
if dist <= r2:
g[j].append(i)
ans = 0
for k in range(n):
vis = {k}
q = [k]
for i in q:
for j in g[i]:
if j not in vis:
vis.add(j)
q.append(j)
if len(vis) == n:
return n
ans = max(ans, len(vis))
return ans
Complexity
The time complexity is and the space complexity is , where is the number of bombs. The space complexity is , where is the number of bombs.
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.