Start learning free

LESSON 269 OF 677 · TUPLES, SORTING & BUILT-INS

Leaderboard in Scala: Sorting Pairs by Score Then Name

Practice Read the full explanation

You get an ArrayBuffer 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 5
    Ctrl + Enter to check

    SCALA · TUPLES, SORTING & BUILT-INS

    Leaderboard in Scala, explained

    Problem overview

    leaderboard gets an ArrayBuffer[(String, Int)] called players. Each player is a pair of a name and a score, like ("Ava", 30). It returns the names only, 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, and scores run from 0 to 1000.

    • [("Ava", 30), ("Ben", 25), ("Cy", 40)] gives ["Cy", "Ava", "Ben"].
    • [("Mia", 50), ("Leo", 70), ("Ava", 50)] gives ["Leo", "Ava", "Mia"]: Ava and Mia both have 50, and Ava comes first.
    • [("Zoe", 0)] gives ["Zoe"].

    Approach

    There are two orders to combine: scores from high to low, and names from A to Z. sortBy sorts from small to large, so a key of (score, name) would put low scores first. The trick is to negate the score. A score of 70 becomes -70, which is smaller than -50, so the highest score sorts first. The name stays as it is, so ties go from A to Z.

    The key is the tuple (-player._2, player._1). Tuples compare position by position: the negated score first, and the name only when the scores are equal. Negation works because scores are whole numbers from 0 to 1000, far from the limits of Int.

    After sorting, the pairs are in the right order. The answer needs only the names, so a loop copies them out in that order.

    The keys for the second example

    Here is the key sortBy builds for each player in [("Mia", 50), ("Leo", 70), ("Ava", 50)]:

    Mia -> (-50,Mia)
Leo -> (-70,Leo)
Ava -> (-50,Ava)

    -70 is the smallest key, so Leo comes first. The other two share -50, so their names decide, and Ava comes before Mia. The sorted pairs are (Leo,70), (Ava,50), (Mia,50), and the loop turns them into the names.

    Step by step

    1. Make ordered with players.sortBy(player => (-player._2, player._1)).
    2. Create an empty ArrayBuffer[String] named names.
    3. Loop over ordered and unpack each pair into (name, score).
    4. Inside the loop, add name to names with +=.
    5. After the loop, return names.

    The solution in Scala

    class Solution {
    def leaderboard(players: ArrayBuffer[(String, Int)]): ArrayBuffer[String] = {
        val ordered = players.sortBy(player => (-player._2, player._1))
        val names = ArrayBuffer[String]()
        for ((name, score) <- ordered) {
            names += name
        }
        return names
    }
}

    Notes on the Scala:

    • player._2 is the score and player._1 is the name. The pair is not changed by sortBy, only moved.
    • In for ((name, score) <- ordered) the pair is unpacked as in val (name, score) = pair. The loop never uses score, which is fine in Scala.
    • names += name adds to the end of the buffer.

    Another way

    The names can be extracted with map instead of a loop: players.sortBy(player => (-player._2, player._1)).map(p => p._1) gives ArrayBuffer(Leo, Ava, Mia) for the second example. Another option is sortWith, which takes a function that says whether the first item goes before the second: players.sortWith((a, b) => if (a._2 != b._2) a._2 > b._2 else a._1 < b._1). It gives the same order, but the tuple key says the same thing in one short expression. The lesson's version uses the loop so you practice unpacking a pair.

    Testing

    [("Ava", 30), ("Ben", 25), ("Cy", 40)]    ArrayBuffer(Cy, Ava, Ben)
[("Mia", 50), ("Leo", 70), ("Ava", 50)]   ArrayBuffer(Leo, Ava, Mia)
[("Zoe", 0)]                              ArrayBuffer(Zoe)

    Common mistakes

    • Forgetting the minus sign. With the key (player._2, player._1), the list sorts from the lowest score up. For Ava 30, Ben 30, Cy 40 that gives ArrayBuffer(Ava, Ben, Cy), but the right answer is Cy, Ava, Ben.
    • Negating the name. You can't put a minus sign on a string. Only the number is negated.
    • Returning pairs. The function returns names, so the loop copies only name.
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free