Detonate the Maximum Bombs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def dfs(self, i, al, detonated):
        if not detonated[i]:
            detonated[i] = True
            for j in al[i]:
                self.dfs(j, al, detonated)
        return detonated.count(True)

    def maximumDetonation(self, bs):
        res = 0
        sz = len(bs)
        al = [[] for _ in range(sz)]

        for i in range(sz):
            x, y = bs[i][0], bs[i][1]
            r2 = bs[i][2] ** 2
            for j in range(sz):
                if (x - bs[j][0]) ** 2 + (y - bs[j][1]) ** 2 <= r2:
                    al[i].append(j)

        for i in range(sz):
            if res < sz:
                res = max(self.dfs(i, al, [False] * 100), res)
        return res

10 Prerequisite LeetCode Problems

This is about finding the maximal impact one bomb can have by potentially triggering other bombs within its range. You need to know how to traverse or inspect multiple nodes in a graph. Here are 10 simpler problems to understand how to approach this problem:

  1. “Flood Fill” (LeetCode 733): A problem about changing the color of an image, which can be solved with breadth-first search (BFS) or depth-first search (DFS).

  2. “Number of Islands” (LeetCode 200): A problem about finding the number of connected components in a binary matrix, solvable with DFS or BFS.

  3. “Max Area of Island” (LeetCode 695): Similar to the previous problem but now with the goal to find the biggest connected component.

  4. “Is Graph Bipartite?” (LeetCode 785): Another problem that involves traversing a graph in a certain way.

  5. “Pacific Atlantic Water Flow” (LeetCode 417): A more complicated problem involving graph traversal.

  6. “Number of Connected Components in an Undirected Graph” (LeetCode 323): This problem focuses on counting connected components.

  7. “Surrounded Regions” (LeetCode 130): This problem is about flipping the values of certain nodes in a graph, given some conditions.

  8. “Friend Circles” (LeetCode 547): This problem is about finding connected components in a graph.

  9. “01 Matrix” (LeetCode 542): In this problem, you are asked to find the distance from every cell to its nearest zero.

  10. “Find the Town Judge” (LeetCode 997): This problem is about analyzing a graph of trust relationships between people.

“Detonate the Maximum Bombs” also involves understanding geometric concepts and range overlap.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        def is_connected(a,b):
            x1, y1, r1 = bombs[a]
            x2, y2, r2 = bombs[b]
            dist = math.sqrt((x1-x2)**2 + (y1-y2)**2)
            return dist <= r1

        conn = collections.defaultdict(list)
        for i in range(len(bombs)):
            for j in range(len(bombs)):
                if i != j:
                    if is_connected(i,j):
                        conn[i].append(j)

                    
        def dfs(node):
            if node in visited:
                return 0

            visited.add(node)            
            ans = 1

            if node in conn:
                for child in conn[node]:
                    if child in visited:
                        continue
                    ans += dfs(child)

            return ans

        maxCount = 1
        for node in conn:
            visited = set()
            maxCount = max(maxCount, dfs(node))
        return maxCount

Problem Classification

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 <= 10^5

Identifying Problem Isomorphism

The problem “Maximum Detonation of Bombs” can be mapped to “Finding the Maximum Connected Component in an Undirected Graph.”

Reasoning:

  • In the “Maximum Detonation of Bombs,” we’re trying to find the maximum number of bombs that can be detonated by detonating only one bomb. The connectivity of the bombs (i.e., whether one bomb can detonate another) can be represented as an undirected graph where each bomb is a node and there is an edge between two nodes if one bomb can detonate the other.

  • The problem of “Finding the Maximum Connected Component in an Undirected Graph” deals with finding the largest connected component (i.e., the largest group of nodes that are all directly or indirectly connected to each other) in an undirected graph.

These two problems are isomorphic because they both involve finding the maximum connected component in an undirected graph, albeit in different contexts. The concept of finding the largest connected component is the core of both problems, and the algorithms to solve them are the same.

Among the two, “Finding the Maximum Connected Component in an Undirected Graph” is simpler, as it deals directly with the graph and doesn’t require the additional step of representing the bombs and their detonation relationships as a graph.

Language Agnostic Coding Drills

  1. Defining a class and a method: This code includes a class Solution and a method maximumDetonation. These are fundamental concepts in object-oriented programming.

  2. Working with lists and list indexing: In Python, a list is an ordered collection of items. The method maximumDetonation accepts a list of lists as an argument, and the nested lists are accessed via their indices.

  3. Defining helper function within a function: The is_connected function is defined within the maximumDetonation method. Understanding function scopes is crucial here.

  4. Performing mathematical calculations: The is_connected function performs various calculations using the Pythagorean theorem and comparison operators.

  5. Understanding the dictionary and defaultdict: The defaultdict is a dictionary subclass that provides a default value for a nonexistent key, which is utilized here to create an adjacency list conn.

  6. Nested looping: The code uses nested for loops to iterate over the bombs list.

  7. Conditional Statements: The code uses an if statement to check whether i is not equal to j, and whether is_connected(i,j) returns True.

  8. Understanding recursive functions: The dfs function is a typical implementation of Depth First Search, a common algorithm in graph theory. This function is recursive, meaning it calls itself in its execution.

  9. Working with sets: Sets in Python are unordered collections of unique elements. The variable visited is a set used to track visited nodes in the graph.

  10. Updating variables: The maxCount variable is updated inside the loop to always contain the maximum count of detonations.

Arranging these units in increasing order of difficulty would result in the following order:

  1. Defining a class and a method
  2. Working with lists and list indexing
  3. Performing mathematical calculations
  4. Conditional Statements
  5. Updating variables
  6. Defining helper function within a function
  7. Understanding the dictionary and defaultdict
  8. Nested looping
  9. Working with sets
  10. Understanding recursive functions

Targeted Drills in Python

Drill 1: Define a class with a method.

1
2
3

class Drill1:
    def hello_world(self):
        return "Hello, world!"

Drill 2: Working with lists and list indexing.

1
2
3

# create a list and access its elements
drill2 = ["apple", "banana", "cherry"]
print(drill2[1])  # output: banana

Drill 3: Performing mathematical calculations.

1
2
3
4
5

# calculate the hypotenuse of a right triangle
a = 3
b = 4
hypotenuse = (a**2 + b**2)**0.5
print(hypotenuse)  # output: 5.0

Drill 4: Conditional Statements

1
2
3
4
5
6

# use an if-else statement to check if a number is odd or even
num = 10
if num % 2 == 0:
    print("Even")
else:
    print("Odd")

Drill 5: Updating variables

1
2
3
4

# increment a variable
count = 0
count += 1
print(count)  # output: 1

Drill 6: Defining helper function within a function

1
2
3
4
5
6

def outer_function(x):
    def inner_function(y):
        return y**2
    return inner_function(x) + 2*x + 1

print(outer_function(5))  # output: 36

Drill 7: Understanding the dictionary and defaultdict

1
2
3
4
5
6

from collections import defaultdict
# count the frequency of characters in a string
char_freq = defaultdict(int)
for char in "hello":
    char_freq[char] += 1
print(char_freq)  # output: defaultdict(<class 'int'>, {'h': 1, 'e': 1, 'l': 2, 'o': 1})

Drill 8: Nested looping

1
2
3
4
5
6

# print a 2D array
array_2D = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for row in array_2D:
    for element in row:
        print(element, end=" ")
    print()

Drill 9: Working with sets

1
2
3
4

# create a set and add an element
drill9 = set()
drill9.add("apple")
print(drill9)  # output: {'apple'}

Drill 10: Understanding recursive functions

1
2
3
4
5
6
7
8

# calculate factorial using recursion
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))  # output: 120