Climbing the Leaderboard: HackerranK, Terminated due to timeout

Question

I have implemented my solution and I thought it was pretty efficient and passes most of the cases but seems like it fails some of the test cases when the input size is very large. I basically push every item from the Alice's array to our array and sort it.I'd appreciate if somebody tell me how I could increase the efficiency get rid of the timeout error.

Alice is playing an arcade game and wants to climb to the top of the leaderboard. Can you help her track her ranking as she beats each level? The game uses Dense Ranking, so its leaderboard works like this:

The player with the highest score is ranked number 1 on the leaderboard. Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number. For example, four players have the scores 100, 90, 90, and 80. Those players will have ranks 1, 2, 2, and 3, respectively.

When Alice starts playing, there are already n people on the leaderboard. The score of each player i is denoted by si. Alice plays for m levels, and we denote her total score after passing each level j as alicej. After completing each level, Alice wants to know her current rank.

You are given an array, scores, of monotonically decreasing leaderboard scores, and another array, alice, of Alice's cumulative scores for each level of the game. You must print m integers. The jth integer should indicate the current rank of alice after passing the jth level.

To illustrate;

Score is :100 100 50 40 40 20 10

Alice is: 5 25 50 120

The output is going to be;

6,4,2,1

My implementation:

function ladder(arr1,arr2){
  while(arr2.length){
    let i=0
    let rank=1
    let score=arr2.shift()
    arr1.push(score)
    arr1.sort(function(a,b){
      return b-a
    })
    while(arr1[i]!==score){
      if(arr1[i]!==arr1[i+1]){
        rank++
      }      

      i++
    }
    console.log(rank)
  } 
}

Answer 1

There are some important inefficient elements in the posted implementation.

Inserting into a sorted array

To insert Alice's next score into the array of sorted scores, the posted appends Alice's score at the end and then sorts the array. What's the typical time complexity of sorting an array?

\$O(n \log n)\$

Is it possible to do better?

When you have a list of sorted values, you can use binary search to find the position to insert a value so that the list stays sorted.

The general idea of binary search goes something like this: pick the middle position m of the array. Is it bigger than the value? Then pick the middle position between 0 and m. Or else if the value was smaller, then pick the middle between m and the end of the array. Follow the same logic, in each step dividing the interval to check by 2, quickly converging on the target position.

What would be the time complexity to find that position using binary search?

\$O(\log n)\$

That's a lot faster than \$O(n \log n)\$.

By the way, since Alice's score only increases, the range of values to search for the correct position shrinks, so the fast solution just keeps getting faster for finding the higher scores.

By the way, once you found the right position, do you actually need to insert into the array?

No, in this particular challenge, you could just overwrite the position with the new value.

Why is that even a question, why not just insert the value and be done with it?

Inserting a value into an array typically requires copying the values that come after the insertion position, which is expensive. Depending on the programming language and how arrays work, a reallocation of the entire array (copying all elements) may also happen, which is even more expensive.

And keep in mind that we have to do this m times, where m is the number of scores of Alice.

What is the overall time complexity of the solution with sorting?

\$O(m n \log n)\$

What is the overall time complexity when we replace sorting with binary search? (Without shrinking the search range, to keep the theory simple.)

\$O(m \log n)\$

If we take into account the shrinking of the search range, then we can achieve a performance faster than \$O(m + n)\$.

Processing the two lists together

An alternative linear time solution is possible if we process the two lists together:

• Compute the ranks of the leaderboard (see the next section of my answer)
• Iterate over the scores of Alice, in increasing order
• From the end of the leaderboard, find the next score that is greater than or equal to Alice's current score
  • If that score is equal to Alice's, then Alice's rank is the same as of that score
  • Otherwise (the score is greater than Alice's), Alice's rank is 1 + the rank of that score
• Repeat for all scores of Alice. Note that when looking for the next leaderboard score, you can continue from the position of the last one found, do not restart from the end

This algorithm visits all elements of the two arrays once, performing a constant number of operations for each. What is the overall time complexity?

\$O(m + n)\$

This is not as good as using binary search that can skip many leaderboard scores at once, but probably fast enough for this exercise, and simpler to implement.

Computing the rank

The current implementation recomputes the ranks up until Alice's position for every single position. That's unnecessary. You could compute the ranks just once up front, and store in an array. Then, once you know Alice's position, you could use the index of that position to find the rank directly.

Style

It's recommended to declare variables right before you need them. For example i and rank are declared too early, when they are only used after the sorting step. The reason to delay declaration as much as possible is to reduce the possibility of mistakes: a variable is not defined yet, a use by mistake is likely going to crash badly and so you discover the problem early. Otherwise it may get overlooked.

---

A common convention to improve readability is to add spaces around operators, after commas, before ( and after ), for example:

function ladder(arr1, arr2) {
  while (arr2.length) {
    let i = 0

Answer 2

janos provided some excellent feedback, so I'll focus on how to make the code faster. Unfortunately, I'm not a javascript coder, but the algorithm still follows a general pattern.

Since the input arrays are sorted, and the game uses a dense ranking, we can calulate the unique scores in \$O(n)\$. Then we simply parse the scores that Alice had, and compare them to the unique scores, performing a kind of merge. This should be \$O(n+m)\$ in the worst case, but performs better the more people share their scores.

The function itself is quite simple:

function ladderFast(scores, points) {
    let lastScore = 0;
    let uniqueScores = [];
    while (scores.length) {
        let tempScore = scores.pop();
        if (tempScore != lastScore) {
            lastScore = tempScore;
            uniqueScores.push(tempScore);
        }
    }
    let index = 0;
    points.forEach(function(element) {
        while (element >= uniqueScores[index]) {
            index++;
        }
        console.log(uniqueScores.length - index + 1);
    });
}

From the example you gave, this code runs about 10 times faster than the code you provided, and should scale even better for larger inputs.

Answer 3

Based on the answers in the above I have implemented my solution. After I have done it, I checked and it is pretty similar to the @maxb 's solution since he also used @janos's algorithm. Please let me know if there is anything to be modified, this one is passed in hackerrank.

let uniqueScore=[scores[0]]

for (let i=1;i<scores.length;i++) {
  if (scores[i]!==uniqueScore[uniqueScore.length-1]) {
    uniqueScore.push(scores[i])
  }
}

let index=uniqueScore.length-1
for (let i=0;i<alice.length;i++) {
  while (alice[i]>=uniqueScore[index]) {
    index--
  }
  console.log(index+2)
}