Prompt: Given a list of bombs, find the maximum number of bombs that can be triggered from triggering one bomb. Please note that one bomb can trigger another bomb if the second bomb is within the first bomb’s blast radius. The bombs in the list are stored like bombs[i] = [x_i,y_i,r_i] where x_i & y_i are the x & y coordinates of the i-th bomb and r_i is the blast radius of the i-th bomb.

Example:

Solution: After reading this problem, there are two components that need to be solved. The first question is “How do we figure out when one bomb is within the radius of another bomb?” The second question is “What is the maximum number of bombs that can be set off by a single initial bomb?”

Let’s try to solve the first question. A simple solution is to find the distance between two specified bombs. For example, if we have bomb 1 and bomb 2 and we know that bomb 1’s blast radius is 5m. If the distance between bomb 1 and bomb 2 is less than or equal to 5m, then bomb 1 can trigger bomb 2. If the distance between bomb 1 and bomb 2 is more than 5m, then bomb 1 cannot trigger bomb 2.

Moving on to the second problem, we have to figure out a way to find the maximum bombs exploded from a single bomb. Imagine that we have clusters of bombs and each cluster is fairly far apart. We can assume that all bombs within a cluster will explode from a single bomb in the same cluster but bombs from a specific cluster cannot trigger bombs from another cluster. With this assumption in mind, we can think of the problem as finding the total detonation for each cluster and then comparing which cluster has the most detonation. We can do this by using a hash map to store all bombs that are within the blast radius of each specific bomb. Then, we can use a DFS function to pass through all bombs connected by their blast radius and memory set to remember all visited bombs so we don’t have infinite loops. The runtime would be O(n) because are passing through all the bombs.