Finding the Players with the highest score

Question

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();
        highestScoringPlayers.add(highestScoringPlayer);

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

        return highestScoringPlayers;
    }
}

public class PlayersSortedByScoreTest {
    @Test
    public void testSortingByScore() {
        Collection<Player> players = new HashSet<>();
        players.add(new Player("Alice", 3));
        players.add(new Player("Bob", 1));
        players.add(new Player("Mike", 3));

        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?

Answer 1

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) {
        highestScoringPlayers.add(player);
    }
}
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();
        }
        highestScoringPlayer.add(player);
    }
}