Question 51122 in Javascript Question posted in
A very good W3school tutorial can be found here.

Improving code performance: Time limit exceeded – Javascript

I wrote a solution for the HackerRank task "Climbing the Leaderboard" where you have an descending array (ranked) with existing scores and an ascending array of the player’s scores (player) and you are supposed to give back an array with the ranking of the player using the dense ranking.

My solution seems to be correct (no test cases have a wrong answer) but too slow. For 3 test cases I receive: Time limit exceeded.

I have already tried to make the implementation more efficient by:

  • breaking out of the for loop and add the ones once the player reached the first ranking (player is ascending, so all following rankings will be 1 as well)
  • using a pointer to avoid checking unnecessary values (since player is ascending and ranked descending)
    but it’s still not fast enough. Could someone give me advice on how to make my code faster? Also it’s kind of long. I am sure there is a shorter way to write it.

I am happy for any information on how to improve my solution.

const oneVector = n => [...Array(n)].map((x, i) => 1);

function climbingLeaderboard(ranked, player) {
  // Write your code here

  ranked = [...new Set(ranked)];
  let pointer;
  let ranking = [];
  let isFinished;
  let nextIndex;

  for (let i = 0; i < player.length; i++) {
    if (ranking[ranking.length - 1] === 1) {
      break;
    }
    pointer = nextIndex || ranked.length - 1;
    isFinished = false;
    // smaller than the smallest value
    if (i === 0 && player[i] < ranked[ranked.length - 1]) {
      ranking.push(ranked.length + 1);
      ranked = [...ranked, player[i]];
      isFinished = true;
      nextIndex = ranked.length;
    }
    //  bigger than the biggest value
    else if (player[i] > ranked[0]) {
      ranking.push(1);
      ranked = [player[i], ...ranked];
      isFinished = true;
      nextIndex = 0;
    }
    // exactly the first value
    else if (player[i] === ranked[0]) {
      ranking.push(1);
      isFinished = true;
      nextIndex = 0;
    }

    while (!isFinished) {
      // exactly the value
      if (player[i] === ranked[pointer]) {
        ranking.push(pointer + 1);
        isFinished = true;
        nextIndex = pointer;
      }
      // between values
      else if (player[i] > ranked[pointer] && player[i] < ranked[pointer - 1]) {
        ranking.push(pointer + 1);
        ranked = [
          ...ranked.slice(0, pointer),
          player[i],
          ...ranked.slice(pointer),
        ];
        isFinished = true;
        nextIndex = pointer;
      } else {
        pointer -= 1;
      }
    }
  }
  if (ranking.length < player.length) {
    ranking = [...ranking, ...oneVector(player.length - ranking.length)];
  }

  return ranking;
}
Tags:

2

Answers


  1. 0

    Try this approach:

    function climbingLeaderboard(ranked, player) {
  // Remove duplicates from the ranked array
  ranked = [...new Set(ranked)];

  // Initialize variables
  const numPlayers = player.length;
  const numRanked = ranked.length;
  const result = new Array(numPlayers);
  let playerIndex = numPlayers - 1;
  let rankedIndex = 0;

  // Binary search for player rankings
  while (playerIndex >= 0) {
    const playerScore = player[playerIndex];

    if (rankedIndex === numRanked || playerScore >= ranked[rankedIndex]) {
      result[playerIndex] = rankedIndex + 1;
      playerIndex--;
    } else {
      rankedIndex = binarySearch(ranked, playerScore, rankedIndex, numRanked);
    }

    // Exit early if all players have been ranked
    if (rankedIndex === -1) {
      break;
    }
  }

  // Set remaining player rankings to the lowest possible ranking
  while (playerIndex >= 0) {
    result[playerIndex] = 1;
    playerIndex--;
  }

  return result;
}

// Binary search for the index to insert a new score
function binarySearch(arr, val, start, end) {
  let left = start;
  let right = end - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === val) {
      return mid;
    } else if (arr[mid] < val) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return left;
}

    This should be way faster

    Login or Signup to reply.
  2. 0

    Your

    ranked = [...ranked, player[i]];

    completely recreates the array, so it’s O(N), making your whole solution, I guess, O(N*N) failing on big N

    Use ranked.push, ranked.unshift and runked.splice to add/remove items from start/end/middle or array, theese are O(1)

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search