Problem of The Day: Detonate the Maximum Bombs

Problem Statement

leetcode problem link

DFS Approach [Accepted]

class Solution:
    def isPointInCircle(self, center_x, center_y, x, y, radius):
        d = (x - center_x)**2 + (y - center_y)**2
        r = radius**2
        return d <= r

    def dfs(self, i, graph, visited):
        visited.add(i)
        for nei in graph[i]:
            if nei not in visited:
                self.dfs(nei, graph, visited)
        return len(visited)



    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        N = len(bombs)
        res = 0
        graph = {i: [] for i in range(N)}
        for i in range(N):
            for j in range(N):
                if i != j:
                    x1, y1, r1 = bombs[i]
                    x2, y2, r2 = bombs[j]
                    if self.isPointInCircle(x1, y1, x2, y2, r1):
                        graph[i].append(j)

        for i in range(N):
            visited = set()
            res = max(res, self.dfs(i, graph, visited))

        return res

Editorial

Approach 1: Depth-First Search, Recursive

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        graph = collections.defaultdict(list)
        n = len(bombs)

        # Build the graph
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                xi, yi, ri = bombs[i]
                xj, yj, _ = bombs[j]

                # Create a path from node i to node j, if bomb i detonates bomb j.
                if ri ** 2 >= (xi - xj) ** 2 + (yi - yj) ** 2:
                    graph[i].append(j)

        # DFS to get the number of nodes reachable from a given node cur
        def dfs(cur, visited):
            visited.add(cur)
            for neib in graph[cur]:
                if neib not in visited:
                    dfs(neib, visited)
            return len(visited)

        answer = 0
        for i in range(n):
            visited = set()
            answer = max(answer, dfs(i, visited))

        return answer

Approach 2: Depth-First Search, Iterative

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        graph = collections.defaultdict(list)
        n = len(bombs)

        # Build the graph
        for i in range(n):
            for j in range(n):
                xi, yi, ri = bombs[i]
                xj, yj, _ = bombs[j]

                # Create a path from i to j, if bomb i detonates bomb j.
                if ri ** 2 >= (xi - xj) ** 2 + (yi - yj) ** 2:
                    graph[i].append(j)

        def dfs(i):
            stack = [i]
            visited = set([i])
            while stack:
                cur = stack.pop()
                for neib in graph[cur]:
                    if neib not in visited:
                        visited.add(neib)
                        stack.append(neib)
            return len(visited)

        answer = 0
        for i in range(n):
            answer = max(answer, dfs(i))

        return answer