Find the rarest in a map

Question

Write a method rarest that accepts a map whose keys are strings and whose values are integers as a parameter and returns the integer value that occurs the fewest times in the map. If there is a tie, return the smaller integer value. If the map is empty, throw an exception.

For example, suppose the map contains mappings from students' names (strings) to their ages (integers). Your method would return the least frequently occurring age. Consider a map variable m containing the following key/value pairs:

{Alyssa=22, Char=25, Dan=25, Jeff=20, Kasey=20, Kim=20, Mogran=25, Ryan=25, Stef=22}

Three people are age 20 (Jeff, Kasey, and Kim), two people are age 22 (Alyssa and Stef), and four people are age 25 (Char, Dan, Mogran, and Ryan).

So a call of rarest(m) returns 22 because only two people are that age. If there is a tie (two or more rarest ages that occur the same number of times), return the youngest age among them. For example, if we added another pair of Kelly=22 to the map above, there would now be a tie of three people of age 20 (Jeff, Kasey, Kim) and three people of age 22 (Alyssa, Kelly, Stef). So a call of rarest(m) would now return 20 because 20 is the smaller of the rarest values.

Here is the link to the question.

public int rarest(Map<String, Integer> m)throws Exception{
    if(m.size() == 0){
      throw new Exception();//throwing an exception as per the question
    }else{
    Integer count = null;
    //Creating a TreeMap to get the lowest age.
    TreeMap<Integer, Integer> t = new TreeMap<Integer, Integer>();
    for(Map.Entry<String, Integer> me : m.entrySet()){
        if(t.containsKey(me.getValue())) {
            count = t.get(me.getValue());
            t.put(me.getValue(), count+1);
        }else {
            count = 1;
            t.put(me.getValue(), count);
        }
      }  
        
     //If there is tie I am comparing the frequencies   
     int freq = t.get(t.firstKey());

     TreeSet<Integer> val = new TreeSet<Integer>();

     for(Integer i : t.keySet()){
        if(freq > t.get(i) ){
            freq = t.get(i);
            val.add(i);
        } 
     }
        if(val.size() > 0){    
           return val.first();
        }else{
           return t.firstKey();
        } 
    }
}

It gives the correct results for the given test cases, but I feel there should be a better way to do this.

Answer 1

public int rarest(Map<String, Integer> m) throws Exception

1. Since this method does not require stateful information other than the method argument, you can mark it as static.
2. Is this method expected to throw a checked Exception? If not, you are better off removing the throws declaration, as it otherwise forces callers to catch on an Exception, which is ambiguously broad.
3. Ok, so you want to throw some kind of Exception when the method argument is empty (note: m.isEmpty() is preferred as it communicates the intent better). If that is the case, you should be throwing an unchecked runtime exception, such as IllegalArgumentException. Give a friendly description if required, e.g. throw new IllegalArgumentException("map cannot be empty").
4. Generally, it is better to use longer, descriptive variable names in Java. The only 'exception' since Java 8 seems to be in lambda declarations, but don't take this as the norm... I simply prefer terser variable names in lambda declarations as well.

(the following part is heavily inspired from my other answer to a recent, similar question)

if(t.containsKey(me.getValue())) {
    count = t.get(me.getValue());
    t.put(me.getValue(), count+1);
}else {
    count = 1;
    t.put(me.getValue(), count);
}

If you happen to be on Java 8, you can use Map.merge():

t.merge(me.getValue(), 1, (a, b) -> a + b);

What this means is to either add me.getValue() => 1 to t if it does not exist, or use the BiFunction lambda declaration to add the existing and new (i.e. 1) values.

Your current solution for iterating through the ordered keys of t is fine, but since you're interested to learn more about the Stream-based processing features of Java 8, here goes...

So, you roughly figured you need two steps to get your answer:

1. Count the number of occurrences for each age

   • You can apply a groupingBy() on m's values, using Collectors.counting() to populate the intermediate map's values:

     // assume map is the method argument
     Map<Integer, Long> temp = map.entrySet().stream()
         .collect(Collectors.groupingBy(Entry::getValue, Collectors.counting()))
     

2. Sort by the least values, then by the youngest age

   • From this intermediate map, you can stream the entries, sort by the values using a custom Comparator lambda declaration and then return the first entry, i.e. the rarest:

     temp.entrySet().stream()
         .sorted((e1, e2) -> { 
             int v = e1.getValue().compareTo(e2.getValue());
             return v != 0 ? v : e1.getKey().compareTo(e2.getKey());
         })
         .findFirst().map(Entry::getKey).get().intValue();
     

Putting it altogether, you will have a nice, compact rarest() method:

public static int rarest(Map<String, Integer> map) {
    return map.entrySet().stream()
            .collect(Collectors.groupingBy(Entry::getValue,
                    Collectors.counting()))
            .entrySet().stream()
            .sorted((e1, e2) -> { 
                int v = e1.getValue().compareTo(e2.getValue());
                return v != 0 ? v : e1.getKey().compareTo(e2.getKey());
            })
            .findFirst().map(Entry::getKey).get().intValue();
}

edit: Once again, @Misha's answer is a welcome improvement of mine, do take a look at that too!

Answer 2

This is more efficient than the accepted answer. min is O(1) memory and O(n) time while sorted is O(n) memory and O(n*log(n)) time:

import static java.util.Comparator.comparingLong;
import static java.util.Comparator.comparingInt;
import static java.util.stream.Collectors.counting;
import static java.util.stream.Collectors.groupingBy;


Comparator<Map.Entry<Integer, Long>> byRarity = comparingLong(Map.Entry::getValue);
Comparator<Map.Entry<Integer, Long>> byAge = comparingInt(Map.Entry::getKey);

int rarest = data.values().stream()
        .collect(groupingBy(x->x, counting()))
        .entrySet().stream()
        .min(byRarity.thenComparing(byAge))
        .get()        // or throw if map is empty
        .getKey();