Leetcode 2101: Detonate the Maximum Bombs
You are given a list of bombs represented by a 2D array ‘bombs’ where each bomb is described by three integers: [xi, yi, ri]. xi and yi denote the X and Y coordinates of the bomb, while ri is its blast radius. Your task is to find the maximum number of bombs that can be detonated by initiating a detonation of one bomb.
Problem
Approach
Steps
Complexity
Input: The input consists of a 2D integer array 'bombs' where each element represents a bomb. Each bomb is defined by three integers: the X-coordinate, Y-coordinate, and blast radius of the bomb.
Example: bombs = [[1, 1, 3], [4, 1, 3]]
Constraints:
• 1 <= bombs.length <= 100
• bombs[i].length == 3
• 1 <= xi, yi, ri <= 10^5
Output: Return the maximum number of bombs that can be detonated by initiating the detonation of one bomb.
Example: Output: 2
Constraints:
Goal: The goal is to calculate the maximum number of bombs that can be detonated starting from any bomb, considering the chain reaction that may happen.
Steps:
• 1. For each bomb, calculate the range of bombs that it can detonate based on its blast radius.
• 2. Perform a DFS (Depth-First Search) to find how many bombs can be detonated if the current bomb is detonated.
• 3. Track the maximum number of detonated bombs for all possible starting bombs.
Goal: The constraints are set to ensure the problem can be solved in a reasonable time frame.
Steps:
• 1 <= bombs.length <= 100
• bombs[i].length == 3
• 1 <= xi, yi, ri <= 10^5
Assumptions:
• All bombs have circular blast ranges.
• A bomb can only detonate another bomb if it lies within its blast radius.
• Input: Input: bombs = [[1, 1, 3], [4, 1, 3]]
• Explanation: If you detonate the first bomb, it will only detonate itself. If you detonate the second bomb, both bombs will detonate because their blast radii overlap.
Approach: The approach to solving this problem involves calculating the bombs affected by detonating any given bomb and tracking the maximum chain reaction.
Observations:
• The problem essentially boils down to a graph traversal problem where bombs are connected based on their blast ranges.
• By modeling the bombs as nodes in a graph, with edges representing detonations, we can perform a DFS to find the maximum chain reaction.
Steps:
• 1. Construct a graph where each node represents a bomb.
• 2. For each bomb, check if it lies within the range of another bomb.
• 3. Perform DFS from each bomb to count the total detonated bombs, and track the maximum count.
Empty Inputs:
• Handle the case where the input array is empty (though the problem guarantees at least 1 bomb).
Large Inputs:
• Ensure that the solution handles up to 100 bombs efficiently.
Special Values:
• Handle cases where bombs are far apart or have no overlapping ranges.
Constraints:
• The constraints ensure that the problem can be solved in O(n^2) time, given that n <= 100.
class Solution {
#define ll long long int
public:
int maximumDetonation(vector<vector<int>>& bombs) {
int n = bombs.size();
vector<vector<int>> gph(n);
for(int i = 0; i < n; i++) {
ll x1 = bombs[i][0];
ll y1 = bombs[i][1];
ll r1 = bombs[i][2];
for(int j = 0; j < n; j++) {
if(i != j) {
ll x2 = abs(x1 - bombs[j][0]);
ll y2 = abs(y1 - bombs[j][1]);
if(x2 * x2 + y2 * y2 <= r1 * r1) {
gph[i].push_back(j);
}
}
}
}
int ans = INT_MIN;
for(int i = 0; i < n; i++) {
int c = 0;
vector<bool> vistd(n, false);
dfs(gph, vistd, c, i);
ans = max(ans, c);
}
return ans;
}
void dfs(vector<vector<int>> &gph, vector<bool> &vstd, int &c, int i) {
if(vstd[i]) return;
vstd[i] = true;
c++;
for(int j: gph[i])
if(!vstd[j])
dfs(gph, vstd, c, j);
}
1 : Code Initialization
class Solution {
Declares the Solution class that contains the solution method.
2 : Code Setup
#define ll long long int
Defines 'll' as a shorthand for long long integer type to handle large numbers.
3 : Access Control
public:
Specifies the public access modifier for methods that follow, making them accessible outside the class.
4 : Function Declaration
int maximumDetonation(vector<vector<int>>& bombs) {
Declares the 'maximumDetonation' function which takes a 2D vector of bomb coordinates and returns the maximum number of detonations.
5 : Variable Declaration
int n = bombs.size();
Initializes the variable 'n' to the number of bombs in the input vector.
6 : Graph Setup
vector<vector<int>> gph(n);
Creates a graph represented by an adjacency list where each bomb's connections are stored.
7 : Graph Construction
for(int i = 0; i < n; i++) {
Starts a loop to iterate through each bomb to build the graph of connections based on detonation range.
8 : Bomb Coordinate Extraction
ll x1 = bombs[i][0];
Extracts the x-coordinate of the ith bomb.
9 : Bomb Coordinate Extraction
ll y1 = bombs[i][1];
Extracts the y-coordinate of the ith bomb.
10 : Bomb Radius Extraction
ll r1 = bombs[i][2];
Extracts the radius of detonation for the ith bomb.
11 : Connection Checking
for(int j = 0; j < n; j++) {
Starts a loop to check for potential connections between the ith bomb and all other bombs.
12 : Condition Check
if(i != j) {
Ensures that the bomb is not checking itself for a connection.
13 : Distance Calculation
ll x2 = abs(x1 - bombs[j][0]);
Calculates the horizontal distance between the two bombs.
14 : Distance Calculation
ll y2 = abs(y1 - bombs[j][1]);
Calculates the vertical distance between the two bombs.
15 : Condition Check
if(x2 * x2 + y2 * y2 <= r1 * r1) {
Checks if the second bomb lies within the detonation radius of the first bomb.
16 : Graph Update
gph[i].push_back(j);
Adds the second bomb as a neighbor in the graph of the first bomb, indicating a potential detonation.
17 : Variable Initialization
int ans = INT_MIN;
Initializes the variable 'ans' to store the maximum detonation count, starting with a very low value.
18 : Loop for Result Calculation
for(int i = 0; i < n; i++) {
Starts a loop to process each bomb and calculate its potential detonation result.
19 : Counter Initialization
int c = 0;
Initializes a counter variable 'c' to count the number of detonations for the current bomb.
20 : Visited Flags Initialization
vector<bool> vistd(n, false);
Initializes a vector to track which bombs have been visited during the DFS traversal.
21 : DFS Call
dfs(gph, vistd, c, i);
Calls the depth-first search function to explore all detonations that start from the ith bomb.
22 : Result Update
ans = max(ans, c);
Updates the maximum detonation result 'ans' based on the count 'c' for the current bomb.
23 : Return Statement
return ans;
Returns the maximum number of detonations from the function.
24 : DFS Function Declaration
void dfs(vector<vector<int>> &gph, vector<bool> &vstd, int &c, int i) {
Declares the depth-first search function that explores all reachable bombs from a starting bomb.
25 : Base Case Check
if(vstd[i]) return;
Checks if the bomb has already been visited, and if so, returns to avoid redundant processing.
26 : Mark as Visited
vstd[i] = true;
Marks the current bomb as visited to prevent revisiting it.
27 : Increment Counter
c++;
Increments the detonation counter for the current bomb.
28 : DFS Recursive Call
for(int j: gph[i])
Loops over all bombs that can be detonated from the current bomb.
29 : Recursive DFS Call
if(!vstd[j])
dfs(gph, vstd, c, j);
Recursively calls DFS for each unvisited bomb connected to the current bomb.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: In the worst case, we need to check the blast range for each pair of bombs, leading to O(n^2) time complexity.
Best Case: O(n)
Worst Case: O(n^2)
Description: We store a graph representation of the bomb interactions, which takes O(n^2) space in the worst case.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus