HackerRank: Climbing the Leaderboard

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$

$n$ people on the
leaderboard. The score of each player i

$i$

$i$ is denoted by si

$s_i$

$s_i$. Alice plays for m

$m$

$m$
levels, and we denote her total score after passing each level j

$j$

$j$ as alicej

$alic{e}_j$

$alice_j$.
After completing each level, Alice wants to know her current rank.

You are given an array, scores

$scores$

$scores$, of monotonically decreasing leaderboard
scores, and another array, alice

$alice$

$alice$, of Alice’s cumulative scores for each
level of the game. You must print m

$m$

$m$ integers. The jth

$j^{th}$

$j^{th}$ integer should
indicate the current rank of alice after passing the jth

$j^{th}$

$j^{th}$ level.

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);
}

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)

$O(n^2)$.
If you rewrite this function to be O(n)

$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);
}