Leetcode | Detonate the Maximum Bombs | Kotlin

devstromo · devstromo · commit 0d36fd7c2a69 · 2025-04-11T23:11:22.000-03:00
diff --git a/leetcode/src/main/kotlin/com/devstromo/medium/p2101/DESCRIPTION.md b/leetcode/src/main/kotlin/com/devstromo/medium/p2101/DESCRIPTION.md
@@ -0,0 +1,48 @@
+# 2101. Detonate the Maximum Bombs
+
+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`
diff --git a/leetcode/src/main/kotlin/com/devstromo/medium/p2101/SolutionKt.kt b/leetcode/src/main/kotlin/com/devstromo/medium/p2101/SolutionKt.kt
@@ -0,0 +1,44 @@
+package com.devstromo.medium.p2101
+
+class SolutionKt {
+    fun maximumDetonation(bombs: Array<IntArray>): Int {
+        val n = bombs.size
+        val graph = Array(n) { mutableListOf<Int>() }
+
+        // Build graph: directed edge from i to j if j is in i's blast radius
+        for (i in 0 until n) {
+            val (xi, yi, ri) = bombs[i]
+            for (j in 0 until n) {
+                if (i == j) continue
+                val (xj, yj) = bombs[j]
+                val dx = xi.toLong() - xj
+                val dy = yi.toLong() - yj
+                val r = ri.toLong()
+
+                if (dx * dx + dy * dy <= r * r) {
+                    graph[i].add(j)
+                }
+            }
+        }
+
+        var max = 0
+        for (i in 0 until n) {
+            val visited = BooleanArray(n)
+            val count = dfs(i, graph, visited)
+            max = maxOf(max, count)
+        }
+
+        return max
+    }
+
+    private fun dfs(current: Int, graph: Array<MutableList<Int>>, visited: BooleanArray): Int {
+        visited[current] = true
+        var count = 1
+        for (neighbor in graph[current]) {
+            if (!visited[neighbor]) {
+                count += dfs(neighbor, graph, visited)
+            }
+        }
+        return count
+    }
+}
diff --git a/leetcode/src/test/kotlin/com/devstromo/medium/p2101/SolutionKtUnitTest.kt b/leetcode/src/test/kotlin/com/devstromo/medium/p2101/SolutionKtUnitTest.kt
@@ -0,0 +1,49 @@
+package com.devstromo.medium.p2101
+
+import org.junit.jupiter.api.Assertions.assertEquals
+import org.junit.jupiter.api.Test
+
+class SolutionKtUnitTest {
+    private val solution = SolutionKt()
+
+    @Test
+    fun `Test Detonate the Maximum Bombs`() {
+        assertEquals(
+            2, solution.maximumDetonation(
+                arrayOf(
+                    intArrayOf(2, 1, 3),
+                    intArrayOf(6, 1, 4),
+                )
+            )
+        )
+        assertEquals(
+            1, solution.maximumDetonation(
+                arrayOf(
+                    intArrayOf(1, 1, 5),
+                    intArrayOf(10, 10, 5),
+                )
+            )
+        )
+        assertEquals(
+            5, solution.maximumDetonation(
+                arrayOf(
+                    intArrayOf(1, 2, 3),
+                    intArrayOf(2, 3, 1),
+                    intArrayOf(3, 4, 2),
+                    intArrayOf(4, 5, 3),
+                    intArrayOf(5, 6, 4)
+                )
+            )
+        )
+
+        assertEquals(
+            1,
+            solution.maximumDetonation(
+                arrayOf(
+                    intArrayOf(1, 1, 100000),
+                    intArrayOf(100000, 100000, 1)
+                )
+            )
+        )
+    }
+}
