# Finding the Players with the highest score

Posted on

Problem

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?

Solution

This is a terrible approach. Sorting the list (an O(nlog(n)

$O\left(n\mathrm{log}\left(n\right)$

$O(n log(n)$) step) and then iterating through it (an O(n)

$O\left(n\right)$

$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)

$O\left(n\right)$

$O(n)$, which is better than your O(nlog(n))

$O\left(n\mathrm{log}\left(n\right)\right)$

$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();
}