List<Set<String>> groupInstancesBasedOnSharedPartition(Map<String, Set<String>> partitionToInstances) {
    int maxId = 0;
    TreeMap<Integer, Set<String>> instanceGroups = new TreeMap<>();
    Map<String, Integer> instanceNameToGroupId = new HashMap<>();
    TreeMap<Integer, Set<String>> orderedPartitionToInstances = new TreeMap<>();
    for (Map.Entry<String, Set<String>> ent : partitionToInstances.entrySet()) {
      orderedPartitionToInstances.put(Integer.parseInt(ent.getKey()), ent.getValue());
    }

    for (Map.Entry<Integer, Set<String>> ent : orderedPartitionToInstances.entrySet()) {
      Set<Integer> groupIds = new HashSet<>();
      for (String instanceName : ent.getValue()) {
        if (!instanceNameToGroupId.containsKey(instanceName)) {
          instanceNameToGroupId.put(instanceName, maxId++);
          instanceGroups.put(instanceNameToGroupId.get(instanceName),
              new HashSet<>(Collections.singleton(instanceName)));
        }
        groupIds.add(instanceNameToGroupId.get(instanceName));
      }
      if (groupIds.size() != 1) {
        // Merge groups
        List<Integer> idList = new ArrayList<>(groupIds);
        int mergeTo = idList.get(0);
        for (int i = 1; i < idList.size(); i++) {
          instanceGroups.get(mergeTo).addAll(instanceGroups.get(idList.get(i)));
          for (String instanceName : instanceGroups.get(idList.get(i))) {
            instanceNameToGroupId.put(instanceName, mergeTo);
          }
          instanceGroups.remove(idList.get(i));
        }
      }
    }
    return new ArrayList<>(instanceGroups.values());
  }
Partitions has multiple replicas that are assigned to multiple instances. Therefore instances share partitions with
each other. This method would group all the instances that share any partition with each other and return those groups.

For example, given such partition placement
{
  "partition1": {"host1", "host2", "host3"},
  "partition2": {"host4", "host5", "host6"},
  "partition3": {"host1", "host4", "host6"},
  "partition4": {"host10", "host11", "host12"},
}
we know that host1 to host6 shared some partitions and should be placed in the same group and host10 to host12 share
some partitions and should be a group. Instances in different groups never share partitions with each other.
@param partitionToInstances A map from partition id to a list of instances this partition is assigned to
@return A list of instance group. Each item of this list is a group of instances that share partitions with each other
but never share partitions outside this group.
ambry-clustermap/src/main/java/com/github/ambry/clustermap/HelixBootstrapUpgradeUtil.java