2101.detonate-the-maximum-bombs.md

2101. Detonate the Maximum Bombs

DFS

If bomb B is in the range of bomb A, then bomb B will be detonated when bomb A is detonated, there is an edge A -> B in the bomb graph. If bomb C is in the range of bomb B, then B -> C, we can detonate bomb A, and bomb B and C will be detonated.

A        B     C        D
*-----------|
         *--------|
               *----|

A -> B -> C

We can build a graph based on the range of bombs, then we can use DFS to find the maximum number of bombs that can be detonated (the number of nodes).

fun maximumDetonation(bombs: Array<IntArray>): Int {
    var maxDetonated = 0
    val graph = buildGraph(bombs)
    for (i in 0 until bombs.size) {
        val visited = HashSet<Int>()
        dfs(graph, i, visited)
        maxDetonated = maxOf(maxDetonated, visited.size)
    }
    return maxDetonated
}

private fun dfs(graph: HashMap<Int, HashSet<Int>>, index: Int, visited: HashSet<Int>) {
    if (visited.contains(index)) return
    visited.add(index)
    graph[index]?.forEach { adj ->
        dfs(graph, adj, visited)
    }
}

private fun buildGraph(bombs: Array<IntArray>): HashMap<Int, HashSet<Int>> {
    val graph = HashMap<Int, HashSet<Int>>()
    for (i in 0 until bombs.size) {
        if (i !in graph) graph[i] = HashSet<Int>()
        for (j in 0 until bombs.size) {
            if (i == j) continue
            if (inRange(bombs[i], bombs[j])) {
                graph[i]!!.add(j)
            }
        }
    }
    return graph
}

private fun inRange(from: IntArray, to: IntArray): Boolean {
    val distance = Math.sqrt(
        Math.pow(from[0] * 1.0 - to[0], 2.0) +
        Math.pow(from[1] * 1.0 - to[1], 2.0)
    )
    return distance <= from[2].toDouble()
}

• Time Complexity: O(n^2)

  • Building the graph: For each pair of bombs, we check if one can detonate the other. There are n bombs, so this is O(n^2) for the double loop in buildGraph().
  • For each bomb, we run a DFS. In the worst case, each DFS could visit all n bombs, and we do this for each bomb, so this is O(n^2) as well.

• Space Complexity: O(n^2)

  • The graph uses O(n^2) space in the worst case (if every bomb can detonate every other bomb).
  • The visited set in each DFS uses up to O(n) space.