findMax.java

public int findMax(int n, int[] arr) {
  // let freqMap be a map where the keys are the elements in arr
  // and the values are its frequency or the number of occurences in arr
  
  List<Integer> list = new ArrayList<>();
  for (int i = 1; i <= n; i++) {
    if (!freqMap.contains(i)) continue;
    
    for (int count = 0; count < freqMap.get(i); count++) {
      list.add(i);
    }
  }
  while (list.size() < n) {
    list.add(n);
  }
  list.set(0, 1);
  for (int i = 0; i < n - 1; i++) {
    if (list.get(i + 1) - list.get(i) > 1)
	list.set(i + 1, list.get(i) + 1);
  }
  return list.get(n - 1);
}