Problem overview
The method topScorer receives scores, an object that maps each player's name to a score, and returns the name of the player with the highest score. If several players share that score, it returns the name that comes first alphabetically. There is always at least one player, and every score is a whole number from 0 to 100.
For {"Ana": 90, "Ben": 75, "Cara": 88} the answer is "Ana", because 90 is the highest. For {"Zoe": 82, "Ana": 82} both players have 82, so "Ana" wins the tie. For {"Max": 0} the only player wins with a score of 0.
Approach: keep the best player so far
Visit every player once and remember the best one seen. Two variables hold that memory: bestName and bestScore. A visited player replaces the best one in two cases: the score is higher, or the score is equal and the name comes first alphabetically.
The starting values matter. bestScore starts at -1, below any real score, so the first player always beats it, even a player with 0 points. Starting at 0 would leave a lone player with 0 points unable to replace the empty name.
The loop must not depend on the order in which the keys arrive. The tie rule is what makes that safe: whichever of two tied players is visited first, the alphabetically earlier name ends up stored.
Step by step
- Set up the best so far.
bestNameis an empty string andbestScoreis -1, both declared withletbecause they change. - Loop over the keys with
for (const name in scores).for...ingives the names, not the scores. - Read the score of the current name with
scores[name]into a constant calledscore. - Compare. Replace the best when
score > bestScore, or when the scores are equal andname < bestName. The tie check goes in parentheses so that it only counts when the scores are equal. - Store the new best: assign both
bestNameandbestScore. - Return
bestNameafter the loop, once every player has been compared.
The solution in TypeScript
class Solution {
topScorer(scores: { [key: string]: number }): string {
let bestName: string = "";
let bestScore: number = -1;
for (const name in scores) {
const score: number = scores[name];
if (score > bestScore || (score == bestScore && name < bestName)) {
bestName = name;
bestScore = score;
}
}
return bestName;
}
}
A few details about this code:
- The type of
scores.{ [key: string]: number }means any string key with a number value. Types are erased when the code compiles, so they check nothing at run time. - Comparing strings with
<. On two strings,<compares them character by character and is true when the left one comes earlier. For names that are a capital letter followed by lowercase letters, as in this lesson, that is alphabetical order. For example,"Ana" < "Zoe"istrue. - The empty string.
"" < "Ana"is alsotrue, but the tie check only runs when the scores are equal, and the first player never ties with -1. ==on numbers. It works here because both sides are numbers.===is the usual habit and gives the same answer.
Edge cases and common mistakes
- Starting
bestScoreat 0. For{"Max": 0}, the score 0 is not greater than 0, and the tie check fails too, because"Max" < ""isfalse. Nothing is stored and the method returns an empty string. Starting at -1 avoids this. - Forgetting the tie rule. With a plain
score > bestScore, the winner of a tie is whichever name the loop meets first. That is a property of the object's key order, not of the alphabet. - Returning the score. The method returns the name, a
string. - Using
for...of. A plain object is not iterable, so usefor...infor the keys.
Testing
Calling the method on the lesson's examples gives:
{"Ana": 90, "Ben": 75, "Cara": 88}givesAna.{"Zoe": 82, "Ana": 82}givesAna, and so does{"Ana": 82, "Zoe": 82}: the order of the keys doesn't matter.{"Max": 0}givesMax.
