Finding the Players with the highest score

Given a list of Players with score, I want to find the ones with the highest score. There can be multiple players with the same score. I'm doing it like this now:

class Player {
final String name;
final int score;

Player(String name, int score) {
this.name = name;
this.score = score;
}
}

class PlayerComparatorByScore implements Comparator<Player> {
@Override
public int compare(Player o1, Player o2) {
return -Integer.compare(o1.score, o2.score);
}
}

class PlayerUtil {
static Collection<Player> getHighestScoringPlayers(Collection<Player> players) {
List<Player> sortedPlayers = new ArrayList<>(players);
Collections.sort(sortedPlayers, new PlayerComparatorByScore());

Set<Player> highestScoringPlayers = new HashSet<>();
Iterator<Player> iterator = sortedPlayers.iterator();
Player highestScoringPlayer = iterator.next();

while (iterator.hasNext()) {
Player player = iterator.next();
if (player.score == highestScoringPlayer.score) {
} else {
break;
}
}

return highestScoringPlayers;
}
}

@Test
public void testSortingByScore() {
Collection<Player> players = new HashSet<>();

Collection<Player> highestScoringPlayers = PlayerUtil.getHighestScoringPlayers(players);

assertEquals(2, highestScoringPlayers.size());
assertEquals(3, highestScoringPlayers.iterator().next().score);
}
}


So this is pretty awkward... Is there a better way?

This is a terrible approach. Sorting the list (an $O(n \log(n)$) step) and then iterating through it (an $O(n)$ operation) to collect the highest scoring players is simply inefficient.

Instead, just iterate through the list in this way:

List<Player> playersList = new ArrayList<>(players);
Set<Player> highestScoringPlayers = new HashSet<>();
int maxScore = Integer.MIN_VALUE;
for (Player player : playersList) {
maxScore = Math.max(maxScore, player.score)
}
for (Player player : playersList) {
if (player.score == maxScore) {
}
}
return highestScoringPlayers;


This uses 2 loops and the minimal amount of space (just enough for the original list and the highest scorers) and so is $O(n)$, which is better than your $O(n \log(n))$ solution.

If you would like to only use 1 loop, at the cost of some additional overhead here is the code:

List<Player> playersList = new ArrayList<>(players);
Set<Player> highestScoringPlayers = new HashSet<>();
int maxScore = Integer.MIN_VALUE;
for (Player player : playersList) {
if (player.score >= maxScore) {
if (player.score > maxScore) {
maxScore = player.score;
highestScoringPlayer.clear();
}

• good solution. but isn't iterating through the list twice unnecessary? You could just add players to highestScoringPlayers if their score is the same as maxScore and clear the list and add the player if it is higher.
• @janos nah, it's not that big of a change^^ @mleyfman you could just create a new one via highestScoringPlayers = new HashSet<>();. You don't do it that often, I doubt it's more expensive than traversing the list twice. But even adding and clearing it: there are probably only a couple of players in the list at a given time, so I think it would be worth it.