How to efficiently find the Lowest Key of the Highest Value in a map with a constraint that it can contain duplicate Values?

Question

My doubt was raised because of this particular question:

https://www.hackerrank.com/challenges/migratory-birds/problem?h_r=next-challenge&h_v=zen&h_r=next-challenge&h_v=zen&h_r=next-challenge&h_v=zen

I know that it can be easily solved by:

1. Store the frequency in Map
2. Initialize two temp variables a,b

3. Start a loop

    - Store the current max value & key to a,b
    - If we find similar value: store the lowest key pair to b.
   

4. Return b value

* But I don't want to do this. I want to solve the problem with Map using Streams *

Input arr contains 11 values, 1 2 2 2 3 4 5 5 4 3 4

Output should be 2

Explanation 1

The different types of birds occur in the following frequencies:

• Type 1: 1
• Type 2: 3
• Type 3: 2
• Type 4: 3
• Type 5: 2

Two types have a frequency of 3, and the lower of those is type 2

I tried the below code which actually worked and I don't know how. I used a max function expecting that i will get an error because i have two Values with max value 3 from my example.

But Take a look at the migratoryBirds() function where I used Collections.max , the query returned me the map entry with lowest key of the highest value.

import java.io.*;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Stream;

import static java.util.stream.Collectors.toList;

public class Solution{

    // Complete the migratoryBirds function below.
    static int migratoryBirds(List<Integer> arr) {
        Map<Integer,Integer> map = new HashMap<>();
        int temp=0;
        for(int val : arr){
            if(map.containsKey(val)){
                temp=map.get(val);
                map.put(val,temp+1);
            }else{
                map.put(val,1);
            }
        }
        Map.Entry<Integer,Integer> maxEntry = Collections.max(map.entrySet(),
                (e1, e2) -> e1.getValue().compareTo(e2.getValue()));
        return maxEntry.getKey();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int arrCount = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                .map(Integer::parseInt)
                .collect(toList());

        int result = migratoryBirds(arr);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Can anyone explain me why i got the expected result and suggest a proper alternate way for it using Map Streams.

Sorry if my question is weird, I love to look at all possible ways.

Answer 1

What you can possibly make use of is :

int minKeyWithMaxValueEntry = map.entrySet()
        .stream()
        .collect(Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey, 
                Integer::min, TreeMap::new))
        .lastEntry()
        .getValue();

to elaborate the collect operation:

• It stores the values from your initial Map entries as keys, correspondingly for each key in your entry is transformed into a value of resultant Map.

• Since there could be multiple keys with the same values, the merge function Integer::min chooses the minimum among them.

• All of this is stored in TreeMap to ensure that the resultant Map is sorted comparing its keys.

• Out of this the last entry (for maximum value in the initial Map) is selected and the value from the final Map is stored as the output.