HackerRank: Climbing the Leaderboard

Question

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\$ people on the leaderboard. The score of each player \$i\$ is denoted by \$s_i\$. Alice plays for \$m\$ levels, and we denote her total score after passing each level \$j\$ as \$alice_j\$. 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 \$j^{th}\$ integer should indicate the current rank of alice after passing the \$j^{th}\$ level.

For example, when \$scores\$ is:

100 100 50 40 40 20 10

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

Answer 1

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(n^2)\$. 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);
}