Number Of Ways To Reconstruct A Tree LeetCode solution in Java

1
class Solution {
2
  public int checkWays(int[][] pairs) {
3
    int result = 1;
4

5
    // Create adjacency list
6
    Map<Integer, Set<Integer>> edges = new HashMap<>();
7
    for (int[] pair : pairs) {
8
      edges.computeIfAbsent(pair[0], x -> new HashSet<>()).add(pair[0]);
9
      edges.computeIfAbsent(pair[1], x -> new HashSet<>()).add(pair[1]);
10
      edges.get(pair[0]).add(pair[1]);
11
      edges.get(pair[1]).add(pair[0]);
12
    }
13

14
    // Sort the edge lists based on their size
15
    List<Map.Entry<Integer, Set<Integer>>> edgesList = new ArrayList(edges.entrySet());
16
    Collections.sort(edgesList, (a, b) -> b.getValue().size() - a.getValue().size());
17

18
    List<Map.Entry<Integer, Set<Integer>>> previous = new ArrayList<>();
19

20
    // Now from each of the edges find the ways to create the tree
21
    for (Map.Entry<Integer, Set<Integer>> cur : edgesList) {
22
      // get the current edge set
23
      Set<Integer> currentSet = cur.getValue();
24
      // find the parent for the current set from the previously computed edge
25
      Map.Entry<Integer, Set<Integer>> parent = find(previous, currentSet);
26
      // if the parent is null
27
      if (parent == null) {
28
        // if you the current set do not match with the edges size then there is no way, return 0
29
        if (currentSet.size() != edges.size()) return 0;
30
      } else {
31
        Set<Integer> parentSet = parent.getValue();
32
        // if the current set do not contain everything from the parent then also return 0
33
        if (!parentSet.containsAll(currentSet)) return 0;
34
        // if the parent contains everything from the current set then return more than one ways
35
        if (parentSet.equals(currentSet)) result = 2;
36
      }
37
      // add the computed edge to previous list
38
      previous.add(cur);
39
    }
40

41
    // only one way
42
    return result;
43
  }
44

45
  Map.Entry<Integer, Set<Integer>> find(
46
      List<Map.Entry<Integer, Set<Integer>>> previous, Set<Integer> currentSet) {
47
    int i = previous.size() - 1;
48
    while (i >= 0) {
49
      Map.Entry<Integer, Set<Integer>> entry = previous.get(i--);
50
      if (currentSet.contains(entry.getKey())) return entry;
51
    }
52
    return null;
53
  }
54
}