Detonate the Maximum Bombs LeetCode solution in Java

1
class Solution {
2
  /*
3
  Make directed graph
4
  u -> v means, v is in the range of u
5
  check from which node maximum nodes can be reached and return the number of nodes reached
6
  */
7
  public int maximumDetonation(int[][] bombs) {
8
    Map<Integer, List<Integer>> graph = new HashMap<>();
9

10
    int n = bombs.length;
11
    for (int i = 0; i < n; i++) {
12
      graph.put(i, new ArrayList<>());
13
      for (int j = 0; j < n; j++) {
14
        if (i == j) continue;
15
        if (inRange(bombs[i], bombs[j])) graph.get(i).add(j);
16
      }
17
    }
18

19
    int max = 0;
20
    for (int i = 0; i < n; i++) {
21
      max = Math.max(max, dfs(i, graph, new HashSet<>()));
22
    }
23
    return max;
24
  }
25

26
  private boolean inRange(int[] u, int[] v) {
27
    // (x-a)^2 + (y-b)^2 = R^2 -> point (a, b) is at border
28
    // (x-a)^2 + (y-b)^2 < R^2 -> point (a, b) is inside the circle
29
    // (x-a)^2 + (y-b)^2 > R^2 -> point (a, b) is outside the circle
30
    return Math.pow(u[0] - v[0], 2) + Math.pow(u[1] - v[1], 2) <= Math.pow(u[2], 2);
31
  }
32

33
  private int dfs(int node, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
34
    if (visited.contains(node)) return 0;
35
    visited.add(node);
36
    int res = 0;
37
    for (int neigh : graph.get(node)) {
38
      res += dfs(neigh, graph, visited);
39
    }
40
    return res + 1;
41
  }
42
}