Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 8 down vote accepted

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) {
        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(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();
        }
        highestScoringPlayer.add(player);
    }
}    
share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.