Skip to main content
Talentd

Detonate the Maximum Bombs - Solution & Explanation

MediumArrayMathDepth-First SearchBreadth-First Search15 min readAsked at: Amazon, Microsoft, Uber +4
Practice this problem

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. This area is in the shape of a circle with the center as the location of the bomb.

The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [xi, yi, ri]. xi and yi denote the X-coordinate and Y-coordinate of the location of the ith bomb, whereas ri denotes the radius of its range.

You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range. These bombs will further detonate the bombs that lie in their ranges.

Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb.

 

Example 1:

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.

Example 2:

Input: bombs = [[1,1,5],[10,10,5]]
Output: 1
Explanation:
Detonating either bomb will not detonate the other bomb, so the maximum number of bombs that can be detonated is 1.

Example 3:

Input: bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
Output: 5
Explanation:
The best bomb to detonate is bomb 0 because:
- Bomb 0 detonates bombs 1 and 2. The red circle denotes the range of bomb 0.
- Bomb 2 detonates bomb 3. The blue circle denotes the range of bomb 2.
- Bomb 3 detonates bomb 4. The green circle denotes the range of bomb 3.
Thus all 5 bombs are detonated.

 

Constraints:

  • 1 <= bombs.length <= 100
  • bombs[i].length == 3
  • 1 <= xi, yi, ri <= 105

Approach Overview

Problem Overview: You are given a list of bombs where each bomb has an (x, y) coordinate and a blast radius. If one bomb explodes, it detonates any other bomb inside its radius, potentially causing a chain reaction. The goal is to determine the maximum number of bombs that can explode if you choose the best bomb to detonate first.

Approach 1: Graph Representation with BFS (O(n²) time, O(n²) space)

Model the bombs as a directed graph. Each bomb is a node, and you add a directed edge from bomb i to bomb j if the distance between them is within the blast radius of i. The distance check uses geometry: (x1-x2)^2 + (y1-y2)^2 <= r^2. Building this adjacency list requires checking every pair of bombs, which costs O(n²). After constructing the graph, run a Breadth-First Search from every bomb to simulate the chain reaction and count how many nodes are reachable. Track the maximum visited count across all starting nodes.

BFS works well because the explosion spreads level by level across reachable bombs. A queue stores bombs that get triggered next, and a visited set prevents re-processing the same bomb. Each BFS traversal visits at most n nodes and edges, keeping the total runtime bounded by O(n²).

Approach 2: Graph Representation with DFS (O(n²) time, O(n²) space)

The same graph model can be explored using Depth-First Search. After constructing the adjacency list, start a DFS from each bomb and recursively trigger all bombs reachable through outgoing edges. Maintain a visited set during each traversal to avoid infinite loops and duplicate counts.

DFS explores the entire detonation chain by going as deep as possible before backtracking. Each traversal effectively simulates a full cascade starting from a single bomb. Because the graph contains at most n² edges from pairwise distance checks, the overall complexity remains O(n²) time and O(n²) space for the adjacency list.

The key insight is converting the geometric reachability condition into a directed graph problem. Once the connections are built, the problem reduces to counting reachable nodes using standard graph traversal. Problems combining arrays, geometry distance checks, and graph traversal frequently follow this pattern.

Recommended for interviews: Build the adjacency list and run BFS or DFS from every bomb. Interviewers expect you to recognize the graph structure and use traversal to simulate the chain reaction. Explaining the pairwise distance check shows understanding of the geometry constraint, while implementing BFS or DFS demonstrates strong graph fundamentals.

Approach 1: Graph Representation with BFS

Represent each bomb as a node in a graph. An edge exists from bomb i to bomb j if bomb i can detonate bomb j. The goal is to start from each bomb and use BFS to find how many bombs can be detonated. Return the maximum number of detonatable bombs starting from any single bomb.

This code constructs a graph with each bomb as a node and checks if a bomb can detonate another based on their respective ranges. BFS is used from each bomb to determine the total number of bombs that can be detonated, and the maximum among all is returned.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n^2), where n is the number of bombs, as we need to check each pair of bombs.
Space Complexity: O(n), for storing the adjacency list of the graph and the visited list.

Try this approach in the editor →

Approach 2: Graph Representation with DFS

Another approach to solve this problem is by using a DFS traversal instead of BFS. We use a similar graph representation where each bomb is a node and an edge exists if one bomb can detonate another. The maximum number of bombs that can be reached starting from each node (bomb) is determined using DFS.

This C++ implementation uses DFS to explore each detonation starting from every bomb and computes the maximum possible detonations. It uses a recursive function to delve deeper into the graph from each bomb until all reachable bombs are visited starting from a given bomb.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(n^2) for constructing the graph and performing DFS traversals.
Space Complexity: O(n) used in the recursion stack and the visited vector.

Try this approach in the editor →

Approach 3: BFS

We define an array g of length n, where g[i] represents the indices of all bombs that can be triggered by bomb i within its explosion range.

Next, we iterate over all bombs. For two bombs (x_1, y_1, r_1) and (x_2, y_2, r_2), we calculate the distance between them dist = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}. If dist leq r_1, then bomb i can trigger bomb j within its explosion range, so we add j to g[i]. If dist leq r_2, then bomb j can trigger bomb i within its explosion range, so we add i to g[j].

Next, we iterate over all bombs. For each bomb k, we use breadth-first search to calculate the indices of all bombs that can be triggered by bomb k within its explosion range and record them. If the number of these bombs equals n, then we can trigger all bombs and directly return n. Otherwise, we record the number of these bombs and return the maximum value.

The time complexity is O(n^3) and the space complexity is O(n^2), where n is the number of bombs.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Graph Representation with BFS

Time Complexity: O(n^2), where n is the number of bombs, as we need to check each pair of bombs.
Space Complexity: O(n), for storing the adjacency list of the graph and the visited list.

Graph Representation with DFS

Time Complexity: O(n^2) for constructing the graph and performing DFS traversals.
Space Complexity: O(n) used in the recursion stack and the visited vector.

BFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Graph + BFS TraversalO(n²)O(n²)General solution. Easy to visualize chain reactions level by level.
Graph + DFS TraversalO(n²)O(n²)Useful when recursion is preferred for exploring full detonation paths.

Video Solution

Detonate the Maximum Bombs - Leetcode 2101 - Python • NeetCodeIO • 18,646 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Detonate the Maximum Bombs easy or hard?
Detonate the Maximum Bombs is classified as a Medium problem. The challenge comes from recognizing that the chain reactions form a directed graph and then applying BFS or DFS correctly. Once the graph modeling step is clear, the implementation becomes straightforward.
How to solve Detonate the Maximum Bombs in O(n)?
An O(n) solution is not feasible because every bomb must potentially be compared with every other bomb to determine reachability. The geometric distance checks alone require O(n^2) comparisons. As a result, the optimal practical solution remains O(n^2) using graph construction and traversal.
What is the best approach for Detonate the Maximum Bombs?
The best approach models the bombs as a directed graph and runs BFS or DFS from every bomb. Create an edge from bomb i to bomb j if j lies within i's blast radius using the squared distance formula. After building the adjacency list in O(n^2), perform a traversal from each node to count how many bombs are triggered in the chain reaction.
What data structure is used in Detonate the Maximum Bombs?
The core data structure is a graph represented using an adjacency list. Each node represents a bomb, and directed edges represent detonation reach. A queue is used for BFS or a recursion stack for DFS, along with a visited set to track triggered bombs.
What is the time complexity of Detonate the Maximum Bombs?
The overall time complexity is O(n^2). You must compare every pair of bombs to determine if one can detonate the other, which costs O(n^2). Each BFS or DFS traversal processes at most n nodes and edges, keeping the total complexity within the same bound.
Detonate the Maximum Bombs Python or Java solution approach
Both Python and Java implementations typically build an adjacency list by checking squared distances between bomb coordinates. After constructing the graph, run BFS or DFS starting from every bomb and count how many bombs are reachable in the chain reaction. Track the maximum count across all starting points.
Is Detonate the Maximum Bombs asked at Google, Amazon, or Meta?
Graph traversal and reachability problems like this commonly appear in interviews at companies such as Amazon, Google, and Meta. The problem tests graph modeling, BFS/DFS traversal, and handling geometric distance calculations within arrays.

Ready to solve this problem?

Practice Detonate the Maximum Bombs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Max Area of Island

Next

Minesweeper