Sort Scores Pt 2

After spending some time working on our solution, despite feeling we could probably optimize further we felt good. So Stephanie Chiang and I decided to take a look at InterviewCake’s solution and compare our approach.

Interview Cake Solution:

function sortScores(unorderedScores, highestPossibleScore) {                                                   // Array of 0s at indices 0..highestPossibleScore                              
   const scoreCounts = new Array(highestPossibleScore + 1).fill(0);                           // Populate scoreCounts                                                    
   unorderedScores.forEach(score => {               
     scoreCounts[score]++;                           
   });                                                   
// Populate the final sorted array                           
   const sortedScores = [];                                                   // For each item in scoreCounts                           
   for (let score = highestPossibleScore; score >= 0; score--) {
     const count = scoreCounts[score];                             
     // For the number of times the item occurs                              
    for (let time = 0; time < count; time++) {  
      sortedScores.push(score);                             
      }                           
    }                                                   
   return sortedScores;                         
}

A key difference is that their approach involves using an array and its indices as a hashtable, whereas we used an object (and Object.keys to order the final result).

They begin by generating a table by filling an array w/ 0s for every number between 0 and the highest possible score.

const scoreCounts = new Array(highestPossibleScore + 1).fill(0);

Next, they loop through the unsorted scores and for each score they increment at that index in the table. This covers duplicate scores.

unorderedScores.forEach(score => {                             scoreCounts[score]++;                           
});

Nice! This was something we thought to handle in our solution as well, however we pushed duplicates to arrays.

Now that we know how many players got each score we need to sort and return these values. We’ll store that in a variable called sortedArr.

A loop is now run over our scoreCounts array starting at the index of highestPossibleScore (b/c we want our returned scores to be in descending order).

for (let score = highestPossibleScore; score >= 0; score--) {
  const count = scoreCounts[score];
  for (let time = 0; time < count; time++) { 
    sortedScores.push(score);                             
    }                           
}

If there is more than ‘0’ at a given index we will enter an interior loop.

The interior loop pushes the currentIndex to sortedArr until time equals count(how many people got a certain score).

The loops are nested, but because we ONLY enter the interior loop if a count is greater than 0, our runtime is still LogN.

Overall, neat! Going through this solution I feel added new tools to our arsenal writing future algorithms.