# 02.06.2023 [2101. Detonate the Maximum Bombs]

02.06.2023

2101. Detonate the Maximum Bombs medium
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/233

Problem TLDR

Count detonated bombs by chain within each radius.

Intuition

A bomb will only detonate if its center within the radius of another.

For example, A can detonate B, but not otherwise.

Let’s build a graph, who’s who can detonate.

Approach

Build a graph, the do DFS trying to start from each node.

Complexity

• Time complexity:
  O(n^3), each of the n DFS will take n^2

• Space complexity:
  O(n^2)

Code

fun maximumDetonation(bombs: Array<IntArray>): Int {
    val fromTo = mutableMapOf<Int, MutableList<Int>>()
        for (i in 0..bombs.lastIndex) {
            val bomb1 = bombs[i]
            val rr = bomb1[2] * bomb1[2].toLong()
            val edges = fromTo.getOrPut(i) { mutableListOf() }
            for (j in 0..bombs.lastIndex) {
                if (i == j) continue
                val bomb2 = bombs[j]
                val dx = (bomb1[0] - bomb2[0]).toLong()
                val dy = (bomb1[1] - bomb2[1]).toLong()
                if (dx * dx + dy * dy <= rr) edges += j
            }
        }
        fun dfs(curr: Int, visited: HashSet<Int> = HashSet()): Int {
            return if (visited.add(curr)) {
                1 + (fromTo[curr]?.sumBy { dfs(it, visited) } ?:0)
            } else 0
        }
        var max = 1
        for (i in 0..bombs.lastIndex) max = maxOf(max, dfs(i))
        return max
    }