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(nlog(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(nlog(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. –  tim Aug 20 at 20:28
@tim I think you can post that as your answer ;-) –  janos Aug 20 at 20:29
I thought about doing that, but it uses more time and space, as adding and clearing repeatedly to a list is expensive. Plus, 2 lightweight loops are usually better than 1 big one. –  mleyfman Aug 20 at 20:30
@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. –  tim Aug 20 at 20:33
I'll add it to my answer –  mleyfman Aug 20 at 20:34