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

Sanjay Pradeep

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:

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

Start a loop

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

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.

Naman

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.

Collected from the Internet

Please contact [email protected] to delete if infringement.