Detonate the Maximum Bombs - Practice Coding Problems

Detonate the Maximum Bombs - Problem

Array Math Depth-First Search Breadth-First Search Graph Geometry Medium

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.

Input & Output

Example 1 — Chain Reaction

$ Input: bombs = [[2,1,3],[6,1,4]]

› Output: 2

💡 Note: Starting with bomb 0 at (2,1) with radius 3: it can reach bomb 1 at (6,1) since distance = 4 ≤ radius 3. Wait, that's wrong. Distance is 4 but radius is 3, so bomb 0 cannot reach bomb 1. Starting with bomb 1 at (6,1) with radius 4: it can reach bomb 0 at (2,1) since distance = 4 ≤ radius 4. So maximum is 2 bombs when starting with bomb 1.

Example 2 — No Chain Reaction

$ Input: bombs = [[1,1,5],[10,10,5]]

› Output: 1

💡 Note: The two bombs are too far apart. Distance between (1,1) and (10,10) is √((10-1)² + (10-1)²) = √162 ≈ 12.7, which is greater than either bomb's radius of 5. No chain reaction possible, so maximum is 1.

Example 3 — Multiple Chain Reactions

$ Input: bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]

› Output: 5

💡 Note: Starting from the right bomb and working backwards, we can create a chain reaction that detonates all 5 bombs due to their overlapping ranges.

Constraints

1 ≤ bombs.length ≤ 100
bombs[i].length == 3
1 ≤ x_i, y_i, r_i ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Bombs with positions and explosion radius

Chain Reaction

Bombs detonate others within their range

Maximum Count

Find starting point that detonates most bombs

Key Takeaway

🎯 Key Insight: Model as directed graph where bombs can detonate others within their circular range

Asked in

G Google 8 a Amazon 5 f Meta 3 Apple 2

The key insight is to model this as a graph problem where bombs can detonate other bombs within their radius. Build a directed graph and use DFS/BFS to find the maximum reachable bombs from any starting point. Best approach is DFS with graph construction: Time O(n²), Space O(n²).

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Graph Construction	O(n² + n²)	O(n²)	Build directed graph of bomb relationships, then DFS from each starting bomb
Brute Force Simulation	O(n³)	O(n)	Try each bomb as starting point, simulate chain reaction with nested loops
BFS with Queue	O(n³)	O(n)	Use BFS to explore chain reactions level by level from each starting bomb

DFS with Graph Construction — Algorithm Steps

Build adjacency list of which bombs can detonate which
For each bomb, perform DFS to count reachable bombs
Return maximum count across all starting positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create edges for bombs that can detonate others

DFS Traverse

From each start, explore all reachable bombs

Count Maximum

Track highest count across all starting points

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int adj[1000][1000];
int adjSize[1000];
bool visited[1000];

int dfs(int start) {
    visited[start] = true;
    int count = 1;
    for (int i = 0; i < adjSize[start]; i++) {
        int neighbor = adj[start][i];
        if (!visited[neighbor]) {
            count += dfs(neighbor);
        }
    }
    return count;
}

int solution(int bombs[][3], int n) {
    // Build adjacency list
    for (int i = 0; i < n; i++) {
        adjSize[i] = 0;
        for (int j = 0; j < n; j++) {
            if (i != j) {
                long long dx = bombs[j][0] - bombs[i][0];
                long long dy = bombs[j][1] - bombs[i][1];
                long long distSq = dx * dx + dy * dy;
                long long radiusSq = (long long)bombs[i][2] * bombs[i][2];
                if (distSq <= radiusSq) {
                    adj[i][adjSize[i]++] = j;
                }
            }
        }
    }
    
    int maxCount = 0;
    for (int i = 0; i < n; i++) {
        memset(visited, false, sizeof(visited));
        int count = dfs(i);
        if (count > maxCount) {
            maxCount = count;
        }
    }
    
    return maxCount;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int bombs[1000][3];
    int n = 0;
    
    char *ptr = line;
    while (*ptr && n < 1000) {
        if (*ptr == '[') {
            ptr++;
            if (*ptr != '[') break;
            ptr++;
            sscanf(ptr, "%d,%d,%d", &bombs[n][0], &bombs[n][1], &bombs[n][2]);
            n++;
            while (*ptr && *ptr != ']') ptr++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(bombs, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² + n²)

O(n²) to build graph by checking all pairs, O(n²) for DFS from n starting points

⚠ Quadratic Growth

Space Complexity

O(n²)

Adjacency list can have up to n² edges in worst case

⚠ Quadratic Space

32.2K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Graph Construction — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler