Climbing the Leaderboard: HackerranK, Terminated due to timeout 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)
  } 
}
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