Problem

Below is my solution to Climbing the Leaderboard on HackerRank:

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

$n$people on the

$i$

leaderboard. The score of each player iis denoted by si

${s}_{i}$. Alice plays for m

$m$$j$

levels, and we denote her total score after passing each level jas alicej

$alic{e}_{j}$.

After completing each level, Alice wants to know her current rank.You are given an array, scores

$scores$, of

$alice$monotonically decreasingleaderboard

scores, and another array, alice, of Alice’s cumulative scores for each

$m$

level of the game. You must print mintegers. The jth

${j}^{th}$integer should

${j}^{th}$

indicate the current rank of alice after passing the jthlevel.

For example, when scores

$scores$is:

```
100 100 50 40 40 20 10
```

And alice

$alice$is:

```
5 25 50 120
```

The rankings for each score of Alice are 6, 4, 2, 1.

My code below works for most test cases,

except the last few where it times out.

```
function dedupe(arr, n) {
const result = [];
for(let i = 0; i < n; i++) {
if(!result.includes(arr[i])) {
result.push(arr[i]);
}
}
return result;
}
const cache = {};
function binarySearchRankings(input, keySearch, min, max) {
if(keySearch > input[0]) {
return 1;
}
if(cache[keySearch]) {
return cache[keySearch];
}
let mid = 0;
while(min <= max) {
mid = Math.ceil((min + max) / 2);
if(keySearch === input[mid]) {
const result = ++mid;
cache[keySearch] = result;
return result;
} else if(keySearch >= input[mid]) {
max = mid - 1;
} else {
min = mid + 1;
}
}
if(keySearch <= input[mid]) {
cache[keySearch] = mid + 2;
return mid + 2;
}
if(keySearch > input[mid]) {
cache[keySearch] = mid + 1;
return mid + 1;
}
return mid;
}
const deduped = dedupe(scores, n);
for(var i = 0; i < m; i++) {
const a = binarySearchRankings(deduped, alice[i], 0, deduped.length -1);
console.log(a);
}
```

Solution

### Performance

It’s the `dedupe`

implementation that drags the performance of your solution down.

It’s because `Array.prototype.includes()`

does a linear search,

so your implementation becomes O(n2)

.

If you rewrite this function to be O(n)

,

the solution will pass all tests.

### Using arrays

The `dedupe`

function takes as parameters an array and its size.

The size parameter is unnecessary and potentially confusing,

because you can always access that with `.length`

.

### Binary search

A common practice when implementing binary search over a list is to return the index of a value if it is found,

otherwise return a negative value from which the insertion point can be computed using the formula `-1 -ret`

.

It would be cleaner to implement `binarySearch(arr, value, low, high)`

in

a way to follow this common contract,

and another `rank`

function that would use the result of `binarySearch`

to compute the correct rank.

Also, the implementation is a bit complicated.

Simpler techniques exist, and the cache is not needed either.

Consider this, for example:

```
function binarySearch(arr, value, lowIndex, highIndex) {
if (lowIndex > highIndex) {
return -(lowIndex + 1);
}
let midIndex = lowIndex + Math.trunc((highIndex - lowIndex) / 2);
if (value == arr[midIndex]) {
return midIndex;
}
if (value > arr[midIndex]) {
return binarySearch(arr, value, lowIndex, midIndex - 1);
}
return binarySearch(arr, value, midIndex + 1, highIndex);
}
```