Minimum Score After Removals on a Tree LeetCode solution in Java

1
class Solution {
2
  public int minimumScore(int[] nums, int[][] edges) {
3

4
    // 1.) Compute the adjacency table. Contains all paths, (including to root, must be filtered out
5
    // later).
6
    Map<Integer, List<Integer>> adjGraph = computeAdjGraph(edges);
7

8
    // 2.) Know compute the total Xors of each node DFS style.
9
    Map<Integer, Integer> xorMap = new HashMap<>();
10
    computeNodeXorDfs(0, -1, nums, xorMap, adjGraph);
11
    int rootXor = xorMap.get(0);
12

13
    // 3.) Before computing all XORs in O(N^2) fashion, we want to compute a list of nodes of
14
    // ascendant, descendant relationships.
15
    // Here we have to chose a SET instead of a list -> else we will run into TLS, obviously there
16
    // are some duplicates.
17
    Map<Integer, Set<Integer>> descendants = new HashMap<>();
18
    Set<Integer> rootChildren = computeDescendants(0, -1, descendants, adjGraph);
19

20
    // 4.) We can check now the parent <-> child relationships.
21
    // Compute each node under the root (not the root itself) for the following conditions:
22
    // node_i is parent of node_j
23
    // rootXor = total ^ node_i (removing node_i from total)
24
    // xor1 = node_i^ node_j (removing node_j from node_i)
25
    // xor2 = node_j
26
    // node_j is parent of node_i
27
    // rootXor = total ^ node_j (removing node_j from total)
28
    // xor1 = node_j^ node_i (removing node_i from node_j)
29
    // xor2 = node_i
30
    // node_j & node_i belong to different parents.
31
    // rootXor = total ^ node_j^ nodE_i (removing node_i & node_j from total)
32
    // xor1 = node_i
33
    // xor2 = node_j
34

35
    int minScore = Integer.MAX_VALUE;
36

37
    for (int i = 1; i < adjGraph.keySet().size(); i++) {
38
      for (int j = i + 1; j < adjGraph.keySet().size(); j++) {
39
        // Is node_i parent of node_j
40
        if (descendants.get(i).contains(j)) {
41
          int rootXor1 = rootXor ^ xorMap.get(i);
42
          int xor1 = xorMap.get(i) ^ xorMap.get(j);
43
          int xor2 = xorMap.get(j);
44
          int maxValue = Math.max(rootXor1, Math.max(xor1, xor2));
45
          int minValue = Math.min(rootXor1, Math.min(xor1, xor2));
46
          minScore = Math.min(minScore, maxValue - minValue);
47
        } else if (descendants.get(j).contains(i)) {
48
          int rootXor1 = rootXor ^ xorMap.get(j);
49
          int xor1 = xorMap.get(j) ^ xorMap.get(i);
50
          int xor2 = xorMap.get(i);
51
          int maxValue = Math.max(rootXor1, Math.max(xor1, xor2));
52
          int minValue = Math.min(rootXor1, Math.min(xor1, xor2));
53
          minScore = Math.min(minScore, maxValue - minValue);
54
        } else {
55
          int rootXor1 = rootXor ^ (xorMap.get(i) ^ xorMap.get(j));
56
          int xor1 = xorMap.get(i);
57
          int xor2 = xorMap.get(j);
58
          int maxValue = Math.max(rootXor1, Math.max(xor1, xor2));
59
          int minValue = Math.min(rootXor1, Math.min(xor1, xor2));
60
          minScore = Math.min(minScore, maxValue - minValue);
61
        }
62
      }
63
    }
64

65
    return minScore;
66
  }
67

68
  Set<Integer> computeDescendants(
69
      int src,
70
      int parent,
71
      Map<Integer, Set<Integer>> descendants,
72
      Map<Integer, List<Integer>> adjGraph) {
73

74
    Set<Integer> childrenOfNode = new HashSet<>();
75

76
    for (int child : adjGraph.get(src)) {
77
      if (child != parent) {
78
        // add the child node
79
        childrenOfNode.add(child);
80
        // add all its children.
81
        childrenOfNode.addAll(computeDescendants(child, src, descendants, adjGraph));
82
      }
83
    }
84

85
    descendants.put(src, childrenOfNode);
86
    return childrenOfNode;
87
  }
88

89
  int computeNodeXorDfs(
90
      int src,
91
      int parent,
92
      int[] nums,
93
      Map<Integer, Integer> xorMap,
94
      Map<Integer, List<Integer>> adjGraph) {
95

96
    int srcXor = nums[src];
97

98
    for (int child : adjGraph.get(src)) {
99
      if (child != parent) srcXor ^= computeNodeXorDfs(child, src, nums, xorMap, adjGraph);
100
    }
101

102
    xorMap.put(src, srcXor);
103
    return srcXor;
104
  }
105

106
  Map<Integer, List<Integer>> computeAdjGraph(int[][] edges) {
107

108
    Map<Integer, List<Integer>> adjGraph = new HashMap<>();
109

110
    for (int[] edge : edges) {
111
      int v1 = edge[0];
112
      int v2 = edge[1];
113

114
      if (!adjGraph.containsKey(v1)) {
115
        adjGraph.put(v1, new ArrayList<>());
116
      }
117

118
      if (!adjGraph.containsKey(v2)) {
119
        adjGraph.put(v2, new ArrayList<>());
120
      }
121
      adjGraph.get(v1).add(v2);
122
      adjGraph.get(v2).add(v1);
123
    }
124
    return adjGraph;
125
  }
126
}