How to collect same maximum numbers keys as List in Java 8

Question

I want to collect the associated keys of List of maximum numbers from Map<String,Integer> in Java 8+

For example:

final Map<String, Integer> map = new HashMap<>();
map.put("first", 50);
map.put("second", 10);
map.put("third", 50);

here I want to return the List of keys associated with maximum values.

For the above example, expected output is [first,third]. Because these 2 keys having the same max value.

I tried with below approach, but able to get single max key only.

final String maxKey = map.entrySet()
    .stream()
    .max(Map.Entry.comparingByValue())
    .map(Map.Entry::getKey)
    .orElse(null);

final List<String> keysInDescending = map.entrySet()
    .stream()
    .sorted(Map.Entry.<String,Integer>comparingByValue().reversed())
    .map(Map.Entry::getKey)
    .collect(Collectors.toList());

System.out.println(maxKey); // third
System.out.println(keysInDescending); //[third, first, second]

But my expected output is [first, third]. How can we achieve it in Java 8+ versions?

Answer 1

Group by the values, giving a Map<Integer, List<String>>, then take the value of the biggest key

List<String> maxKeys = map.entrySet()
        .stream()
        .collect(groupingBy(Map.Entry::getValue, mapping(Map.Entry::getKey, toList())))
        .entrySet()
        .stream()
        .max(Map.Entry.<Integer, List<String>>comparingByKey())
        .orElseThrow().getValue();

That iterates twice, but the second time the map is smallest

---

Best performant solution still is one-iteration for-loop

List<String> maxKeys = new ArrayList<>();
int maxValue = Integer.MIN_VALUE;

for (Map.Entry<String, Integer> e : map.entrySet()) {
    if (e.getValue() < maxValue) continue;
    if (e.getValue() > maxValue) maxKeys.clear();
    maxValue = e.getValue();
    maxKeys.add(e.getKey());
}

Answer 2

Slight unclearness; take max value first.

    final Integer maxValue = map.values()
        .stream()
        .max(Function.identity())
        .map(Map.Entry::getKey)
        .orElse(Integer.MIN_VALUE);

    final List<String> keysInDescending = map.entrySet()
        .stream()
        .filter(e -> maxValue.equals(e.getValue()))
        .map(e -> e.getKey())
        //.sorted(Comparator.reverseOrder())
        .collect(Collectors.toList());

Sorting probably is not needed.

Answer 3

Easy solution with streams

Step 1 : get the maxValue

final Integer maxValue = map.values()
    .stream()
    .max(Comparator.naturalOrder())
    .orElse(null);

or more simply:

// But be aware of NoSuchElementException if the the map is empty.
final Integer maxValue = Collections.max(map.values());

Step 2 : get keys associated with this max value:

List<String> result = map.entrySet()
    .stream()
    .filter(e -> e.getValue().equals(maxValue))
    .map(Map.Entry::getKey)
    .collect(Collectors.toList());

Only one pass

OP asked if we can do it one pass. I really don't think it's necessary as you can't do better than O(n) and it's likely that a one pass solution could be slower (as you need to keep a list of the keys that you might not need).

With a for loop

Quite easy and clear

ArrayList<String> result = new ArrayList<>();
int max = Integer.MIN_VALUE;

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    Integer value = entry.getValue();
    if(value < max) continue;
    if(value > max){
        max = value;
        result = new ArrayList<>();
    } 
    // this applies in both > max and == max cases
    result.add(entry.getKey());
}

With streams

If we absolutely want to use streams, we can actually convert the code above to streams and we can use collect. But I really wouldn't suggest this approach as it makes everything more complicated. Also since the accumulator needs to keep both the keys and the max value, you need to create a private class to hold the data. So this is just for the sake of the exercise/brain teaser.

List<String> result = map.entrySet()
        .stream()
        .collect(MaxData::supply, MaxData::accumulate, MaxData::combine)
        .keys;

And the accumulator class:

 public static class MaxData {
        int max;
        List<String> keys;

        private MaxData(int max, List<String> keys) {
            this.max = max;
            this.keys = keys;
        }

        public static MaxData supply() {
            return new MaxData(Integer.MIN_VALUE, null);
        }

        public void accumulate(Map.Entry<String, Integer> entry) {
            Integer entryValue = entry.getValue();
            if (entryValue > max) {
                max = entryValue;
                keys = new ArrayList<>();
                keys.add(entry.getKey());
            } else if (entryValue == max) {
                keys.add(entry.getKey());
            }
            // last case is entryValue < max, we keep the current max
        }

        public void combine(MaxData other) {
            if (other.max > max){
               max = other.max;
               keys = other.keys;
            } else if(other.max == max) {
                keys.addAll(other.keys);
            }
            // last case is entryValue < max, we keep the current max
        }
    }