How to retrieve the key with a maximum value in a TreeMap in Java?

Question

I have a tree map declared as follows:

TreeMap<Integer, Integer> tree = new TreeMap<Integer, Integer>();

How do I retrieve the key with the maximum value. Is there an O(1) way of achieving this. I know that maximum and minimum keys can be retrieved from a TreeMap in O(1) time as follows:

int maxKey = tree.lastEntry().getKey();
int minKey = tree.firstEntry().getKey();

Thanks for help.

Answer 1

The collection is not sorted by value so the only way is brute force O(n) unless there is another collection with say the reverse map available.

Map<Integer, Integer>map = new TreeMap<>();
int max = map.values().stream().max(Integer::compare).get();

Answer 2

O(1) complexity is not possible with TreeMap. you need to create one more map which uses value of first map as keys. or use BiMap

public TreeBiMap implements Map {
   private Map<Integer, Integer> map;
   private Map<Integer, Integer> reverseMap;
   public TreeBiMap() {
     map = new TreeMap<>();
     reverseMap = new TreeMap<>();
   }

   public void put(Integer key, Integer value) {
      map.put(key, value);
      reverseMap.put(value, key);
   }

   public Integer getMaxValue() {
      return reverseMap.lastEntry().getKey()
   }

}