Start learning free

LESSON 264 OF 667 · PAIRS, SORTING & BUILT-INS

Leaderboard in C++: Sorting Pairs by Score, then Name

Practice Read the full explanation

You get a vector of players, players. Each player is a pair: a name and a score, like ("Ava", 30).

Return the names, from the highest score to the lowest.

Players with the same score go in alphabetical order of their names.

The starter code shows how your language holds a pair.

 

Example 1:

Input: players = [("Ava", 30), ("Ben", 25), ("Cy", 40)]
Output: ["Cy", "Ava", "Ben"]
Explanation: Cy has the most points, 40.
Then come Ava with 30 and Ben with 25.

Example 2:

Input: players = [("Mia", 50), ("Leo", 70), ("Ava", 50)]
Output: ["Leo", "Ava", "Mia"]
Explanation: Leo leads with 70.
Ava and Mia both have 50.
Ava comes first from A to Z.

Example 3:

Input: players = [("Zoe", 0)]
Output: ["Zoe"]
Explanation: Zoe is the only player.

 

Constraints:

  • players has 1 to 100 players.
  • Every score is a whole number from 0 to 1000.
  • Each name is a capital letter followed by lowercase letters, like "Ava".
  • No two players have the same name.
STEP 1 OF 6
    Ctrl + Enter to check

    C++ · PAIRS, SORTING & BUILT-INS

    Leaderboard in C++, explained

    Problem overview

    leaderboard receives a vector of players. Each player is a pair<string, int>: a name and a score, like {"Ava", 30}. It returns only the names, from the highest score to the lowest. Players with the same score go in alphabetical order of their names. No two players share a name.

    For [("Ava", 30), ("Ben", 25), ("Cy", 40)] the result is ["Cy", "Ava", "Ben"]. For [("Mia", 50), ("Leo", 70), ("Ava", 50)] it is ["Leo", "Ava", "Mia"]: Leo leads with 70, and Ava and Mia tie at 50, so Ava comes first. For [("Zoe", 0)] it is ["Zoe"].

    Approach: sort the pairs, then pull out the names

    The job has two parts. First, put the players in the right order. Then build a vector with just their names, in that order.

    For the ordering, give sort a lambda that says when player a goes before player b. In a pair, second is the score and first is the name. Rule one: if the scores differ, the higher score goes first, a.second > b.second. Rule two, for equal scores: the name that comes first from A to Z goes first, a.first < b.first.

    Step by step

    1. Sort players with a lambda of two const pair<string, int>& parameters.
    2. Rule one: if a.second != b.second, return a.second > b.second. The sign is "greater than" because high scores come first.
    3. Rule two: return a.first < b.first for players with equal scores.
    4. Create an empty vector<string> names to collect the result.
    5. Loop over the sorted players, unpacking each pair into auto [name, score].
    6. Add each name with push_back. The players are already in order, so the names come out in order.
    7. Return names after the loop.

    What the sort does to the second example

    The input is Mia 50, Leo 70, Ava 50. After the sort the vector holds these players:

    Leo 70
Ava 50
Mia 50

    Leo has the highest score, so rule one puts him first. Ava and Mia have the same score, so rule one says nothing about them (the scores don't differ) and the comparison falls through to rule two, which puts Ava before Mia. The loop then reads the names from top to bottom and builds ["Leo", "Ava", "Mia"].

    The reason for the if is that the lambda must give one clear answer for every pair of players. Without it, a single line such as return a.second > b.second; would be false in both directions for two equal scores, and the sort would be free to leave them in either order. The second line only runs when the first has nothing to say.

    The solution in C++

    class Solution {
public:
    vector<string> leaderboard(vector<pair<string, int>>& players) {
        sort(players.begin(), players.end(), [](const pair<string, int>& a, const pair<string, int>& b) {
            if (a.second != b.second) {
                return a.second > b.second;
            }
            return a.first < b.first;
        });
        vector<string> names;
        for (auto [name, score] : players) {
            names.push_back(name);
        }
        return names;
    }
};

    Details worth knowing:

    • auto [name, score] unpacks each pair into two variables with the pair's types. The loop doesn't use score; that is fine, because unused structured bindings are allowed.
    • Pairs have their own ordering. A plain sort(players.begin(), players.end()) compares first and then second: name first, score second, both ascending. That is not the order wanted here, which is why the lambda is needed.
    • The function sorts the caller's vector, because players is passed by reference.

    Another way to write the rules

    The two rules can be folded into one comparison of pairs, by negating the score so that a bigger score sorts first:

    sort(players.begin(), players.end(), [](const auto& a, const auto& b) {
    return make_pair(-a.second, a.first) < make_pair(-b.second, b.first);
});

    On the second example this gives Leo Ava Mia, like the version above. It is shorter, but the lesson's version with two plain rules is easier to read and to change.

    Edge cases and common mistakes

    • Wrong direction on the score. a.second < b.second puts the lowest score first.
    • Forgetting the name rule. With ties, the order of Ava and Mia would be left to chance.
    • Flipping the name rule. a.first > b.first would put Mia before Ava.
    • Returning the pairs or the scores. The result type is vector<string>: names only.
    • One player. [("Zoe", 0)] sorts trivially and returns ["Zoe"].

    Why sort first, then collect

    Sorting the pairs and only then dropping the scores keeps each name attached to its score while the order is decided. If you pulled the names out first, the scores would be gone and nothing would tell you which name goes where. The pair keeps them together until the order is final, and the loop at the end is a plain copy of the names in that order.

    The loop makes a copy of every pair, which is fine for at most 100 short players. For a large vector, for (const auto& [name, score] : players) reads the pairs in place without copying them. The two forms give the same names in the same order.

    Because no two players share a name, rule two always settles a tie between two different players. Two entries can never be fully equal, so the final order is the same on every run, which is what lets the lesson's tests expect one exact list of names.

    Testing

    • [("Ava", 30), ("Ben", 25), ("Cy", 40)] gives Cy Ava Ben.
    • [("Mia", 50), ("Leo", 70), ("Ava", 50)] gives Leo Ava Mia.
    • [("Zoe", 0)] gives Zoe.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free