Start learning free

LESSON 222 OF 667 · LOOPS WITH STRINGS, ARRAYS & DICTIONARIES

Top Scorer in C++: Largest Value in an unordered_map

Practice Read the full explanation

You get scores, an unordered_map from players' names to their scores. Return the name of the player with the highest score.

Several players may share the highest score. Then return the name that comes first in alphabetical order.

 

Example 1:

Input: scores = {"Ana": 90, "Ben": 75, "Cara": 88}
Output: "Ana"
Explanation: 90 is the highest score, and it is Ana's.

Example 2:

Input: scores = {"Zoe": 82, "Ana": 82}
Output: "Ana"
Explanation: Both have 82. "Ana" comes before "Zoe" in alphabetical order.

Example 3:

Input: scores = {"Max": 0}
Output: "Max"
Explanation: Max is the only player, so his score is the highest.

 

Constraints:

  • scores has at least one name.
  • Every score is a whole number from 0 to 100.
  • Each name is a capital letter followed by lowercase letters, like "Ana".
STEP 1 OF 5
    Ctrl + Enter to check

    C++ · LOOPS WITH STRINGS, ARRAYS & DICTIONARIES

    Top Scorer in C++, explained

    Problem overview

    The function topScorer gets scores, an unordered_map<string, int> from player names to scores, and returns the name of the player with the highest score. If several players share the highest score, it returns the name that comes first alphabetically. The map has at least one entry and every score is between 0 and 100.

    For {"Ana": 90, "Ben": 75, "Cara": 88} the answer is Ana. For {"Zoe": 82, "Ana": 82} both players tie, and Ana comes before Zoe. For {"Max": 0} the only player wins with a score of 0.

    Approach

    Keep the best player seen so far and compare every entry with it. This is the same "best so far" pattern used to find the largest number in a vector, with two differences. The value to compare is a map value, and a tie is settled by the key.

    A map has no fixed order, so the code can't say "the first player wins a tie". It has to compare the names explicitly, and then the result is the same whatever order the loop visits the entries in.

    Here is how the comparison works for two players with the same score, Zoe and Ana, both at 82. Whichever one the loop reaches first becomes the best, because 82 beats -1. When the other one arrives, the score is equal, so the name decides: if Ana is already the best, "Zoe" < "Ana" is false and nothing changes. If Zoe is the best, "Ana" < "Zoe" is true, so Ana takes over. Either way the function ends with Ana.

    Step by step

    1. Set up the best so far. bestName starts as an empty string and bestScore starts at -1. Every real score is at least 0, so the first player always beats -1.
    2. Visit every entry with for (auto& [name, score] : scores).
    3. Check whether this player is better: a higher score, or an equal score with a name that sorts earlier. On two string values, < is true when the left one comes first in alphabetical order.
    4. Take over the title. Store the name and the score in bestName and bestScore.
    5. Return bestName after the loop.

    The solution in C++

    class Solution {
public:
    string topScorer(unordered_map<string, int>& scores) {
        string bestName = "";
        int bestScore = -1;
        for (auto& [name, score] : scores) {
            if (score > bestScore || (score == bestScore && name < bestName)) {
                bestName = name;
                bestScore = score;
            }
        }
        return bestName;
    }
};

    A few details:

    • The map is passed by reference, so a big map isn't copied. The function only reads it.
    • && binds tighter than ||, so the parentheses around the tie check don't change the result. They make it clear that the name only matters when the scores are equal.
    • Names are compared character by character. All names here are a capital letter followed by lowercase letters, so this is alphabetical order.

    Edge cases and common mistakes

    • Starting bestScore at 0. A score of 0 is allowed. For {"Max": 0} the first player scores 0, which doesn't beat 0, and the tie check "Max" < "" is false, so the function returns an empty string instead of Max. Starting at -1 avoids it.
    • Relying on the loop order. An unordered_map can visit Zoe before Ana or after her. Only the explicit name comparison makes the tie result stable.
    • Returning the score. The function returns the name, not the number.
    • Ties at zero. With {"Max": 0, "Bo": 0} the function returns Bo.

    Testing

    • {"Ana": 90, "Ben": 75, "Cara": 88} gives Ana.
    • {"Zoe": 82, "Ana": 82} gives Ana.
    • {"Max": 0} gives Max.
    • {"Max": 0, "Bo": 0} gives Bo.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free