Detonate the Maximum Bombs — LeetCode 2101 Python Solution
MediumDepth-First SearchBreadth-First SearchGraphGeometryArrayMath
- Problem
- #2101
- Pattern
- Breadth-First Search
- Reading time
- 5 min
- Source
- leetcode.com
The problem
You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt.
Example
- Input
- bombs = [[2,1,3],[6,1,4]]
- Output
- 2
- Explanation
- The above figure shows the positions and ranges of the 2 bombs.
Python solution
Python
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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n^3) |
| Space | O(n^2), where n is the number of bombs auxiliary |
Pattern: Breadth-First Search
Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 2101. Detonate the Maximum Bombs is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.
The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2101. Detonate the Maximum Bombs?
- LeetCode 2101. Detonate the Maximum Bombs is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2101. Detonate the Maximum Bombs?
- The Python solution on this page runs in O(n^3).
- What is the space complexity of LeetCode 2101. Detonate the Maximum Bombs?
- The Python solution on this page uses O(n^2), where n is the number of bombs auxiliary space.
- What topics does LeetCode 2101. Detonate the Maximum Bombs cover?
- LeetCode 2101. Detonate the Maximum Bombs is tagged Depth-First Search, Breadth-First Search, Graph, Geometry, Array and Math on LeetCode.