How to get Top N values based on repetition from a list in Java

I am trying to get Top N values based on repetition from a list in Java.

Example: Find Top 2 values
<BR>[ "strawberries", "orange", "apple", "mango", "grapes", "pineapple", "mango", "strawberries", "mango", "apple"]

Result:<BR>
["mango"] //mango repeated 3 times<BR>
["strawberries", "apple"] // "strawberries", "apple" repeated 2 times each

I have written below code to acheive this

private static List<List<String>> getTop(int n, List<String> values) {
Map<String, Long> valueCountMap = values.stream()
.collect(groupingBy(x -> x, counting()));
final Map<String, Long> sortedByCount = valueCountMap.entrySet()
.stream()
.sorted(Map.Entry.<String, Long>comparingByValue().reversed())
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (x, y) -> y, LinkedHashMap::new));
List<List<String>> topNValues = new ArrayList<>();
long prevValue = -1;
for (Map.Entry<String, Long> e : sortedByCount.entrySet()) {
if (prevValue == -1 || prevValue != e.getValue()) {
if (topNValues.size() == n) {
break;
}
prevValue = e.getValue();
List<String> keys = new ArrayList<>();
keys.add(e.getKey());
topNValues.add(keys);
} else if (prevValue == e.getValue()) {
List<String> keys = topNValues.get(topNValues.size() - 1);
keys.add(e.getKey());
}
}
return topNValues;
}

I want to know if there is a better way of implementing this. Both performance and implementation wise.

Try this.

private static List<List<String>> getTop(int n, List<String> values) {
return values.stream()
.collect(Collectors.groupingBy(s -> s, Collectors.counting()))
.entrySet().stream()
.collect(Collectors.groupingBy(Entry::getValue,
TreeMap::new,
Collectors.mapping(Entry::getKey, Collectors.toList())))
.descendingMap().values().stream()
.limit(n)
.collect(Collectors.toList());
}

Input

[strawberries, orange, apple, mango, grapes, pineapple, mango, strawberries, mango, apple]

Result of first .collect().

{orange=1, apple=2, pineapple=1, strawberries=2, grapes=1, mango=3}

Result of second .collect().

{1=[orange, pineapple, grapes], 2=[apple, strawberries], 3=[mango]}

Result of .descendingMap()

{3=[mango], 2=[apple, strawberries], 1=[orange, pineapple, grapes]}

Result of last .collect()

[[mango], [apple, strawberries]]

What you seem to be looking for is really a List<Set<String>> as an output. A simplification to is possible if you have ranked entries based on the counting you've performed to start off with:

private static List<Set<String>> getTopN(int n, List<String> values) {
Map<String, Long> valueCountMap = values.stream()
.collect(Collectors.groupingBy(x -> x, Collectors.counting()));
Map<Long, Set<String>> rankedEntries = values.stream()
.collect(Collectors.groupingBy(valueCountMap::get, Collectors.toSet()));
return rankedEntries.entrySet().stream()
.sorted(Map.Entry.<Long, Set<String>>comparingByKey().reversed())
.limit(n)
.map(Map.Entry::getValue)
.collect(Collectors.toList());
}

In terms of performance, you already have a decent algorithm to obtain the result. In the above solution for a input of N elements, this would iterate N times for counting, then N times performs a lookup on the frequency map and later iterate rankedEntries which is always < N, so you would end up with the complexity of O(N) overall.