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.

Erund

Use the values as your key (if the values are distinct) in your TreeMap and then do as you want! – Araxes

Minimum and maximum keys can be retrieved in O(1) in a TreeMap? Really? How? – Contour

@WasiAhmad The values are not distinct in the TreeMap – Erund

Yes, as mentioned in the question, max and min keys can be retrieved from the TreeMap in O(1). This is the advantage over using a data structure like HashMap or HashSet. – Erund

@JoeC looking up any value including the min/max is O(log N) but retrieving what it is, is O(1) – Monika

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();

Monika

I thought there was a way of doing this in O(1). Thanks anyways. – Erund

@SpiderMan You need another TreeMap/TreeSet of the values to do that. – Monika

But when using a second TreeMap, be careful there aren't duplicates in the values... you will lose keys. – Selfsustaining

@DrewWills this is only a problem when you remove a value. If the values are the same maximum value it doesn't matter but when you remove a value, you need to know if it is the last occurrence of that value or not. – Monika

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()
   }

}

Resale

An example implementation or links would be useful. Thanks @MukeshKumar – Erund

Answer 3

As others have said, you basically have to iterator each map entry and find the entry with the largest value.

---

Note that in your post you made a mistake.

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();

I think the time complexity should be O(lgn).

The source code of getLastEntry:

/**
     * Returns the last Entry in the TreeMap (according to the TreeMap's
     * key-sort function).  Returns null if the TreeMap is empty.
     */
    final Entry<K,V> getLastEntry() {
        Entry<K,V> p = root;
        if (p != null)
            while (p.right != null)
                p = p.right;
        return p;
    }

Also refer to this post in SO

Bookbinder

Answer 4

The answer provided by @PeterLawrey answers the question fair enough. If you are looking for a simpler implementation, here it is:

TreeMap<Integer, Integer> tree = new TreeMap<Integer, Integer>();
// populate the tree with values
Map.Entry<Integer, Integer> maxEntry = null;
for(Map.Entry<Integer, Integer> entry : tree.entrySet()){
   if(maxEntry == null || entry.getValue().compareTo(maxEntry.getValue()) > 0)
      maxEntry = entry;
}

System.out.println("The key with maximum value is : " + maxEntry.getKey());

Erund

Answer 5

Do you depend on using a TreeMap/do you fill it yourself? I ran into a similar situation and extended the TreeMap by the missing functionality:

public class TreeMapInteger<T> extends TreeMap<Integer,T> {

    private static final long serialVersionUID = -1193822925120665963L;

    private int minKey = Integer.MAX_VALUE;
    private int maxKey = Integer.MIN_VALUE;

    @Override
    public T put(Integer key, T value) {

        if(key > maxKey) {
            maxKey = key;
        }

        if(key < minKey) {
            minKey = key;
        }

        return super.put(key, value);

    }

    public int getMaxKey() {
        return maxKey;
    }

    public int getMinKey() {
        return minKey;
    }

}

This won't decrease the complexity but depending on when and how your Map is filled having the values prepared for you when you need them might be preferable.

Propertied

Answer 6

As TreeMap in java implement a Red-Black tree(A self-balancing binary search tree). As its a balanced binary search tree in core, max key and min key can in accessed in O(log n) time.

max = map.lastEntry().getKey();
min = map.firstEntry().getKey();

Embranchment