I’m stuck on the Leaderboard Climbing problem on Hackerrank. I’ve tried using binary search and caching, but I’m still failing test cases 6 and 8. Here’s what I’ve got so far:
function updateLeaderboard(scores, playerScores) {
scores = Array.from(new Set(scores));
let memo = {};
return playerScores.map(score => {
if (memo[score]) return memo[score];
let start = 0;
let end = scores.length - 1;
while (start <= end) {
let mid = start + Math.floor((end - start) / 2);
if (scores[mid] === score) {
memo[score] = mid + 1;
return mid + 1;
} else if (scores[mid] < score) {
end = mid - 1;
} else {
start = mid + 1;
}
}
memo[score] = start + 1;
return start + 1;
});
}
I tried using a for loop instead of map earlier, but that made all my tests fail. Any ideas on how to improve this? Thanks in advance for your help!
hey mike, i tried this problem too. have u considered using a while loop instead of map? it might be faster. also, try sorting the scores in descending order first. that could help with those tricky test cases. good luck man!
I’ve tackled this problem before, and I can share some insights that might help. Your approach using binary search and memoization is on the right track, but there’s room for optimization.
One thing I noticed is that you’re creating a new Set and Array from the scores each time the function is called. This can be inefficient for large datasets. Instead, try sorting the scores array in descending order once at the beginning and remove duplicates. This way, you’re working with a pre-processed array.
Also, consider using a more efficient data structure for memoization, like a Map instead of a plain object. Maps have better performance for frequent additions and lookups.
Lastly, make sure you’re handling edge cases correctly, like when a player’s score is higher than the highest score in the leaderboard or lower than the lowest score. These edge cases can sometimes cause issues with binary search implementations.
If you’re still having trouble after these adjustments, it might be worth looking into the time complexity of your solution. Hackerrank sometimes has very large test cases that require more optimized approaches.
I’ve encountered similar issues with this challenge. One optimization you might consider is reversing the scores array before performing the binary search. This allows you to find the correct position more efficiently, especially for high scores.
Additionally, you could try a two-pointer approach instead of binary search. Start from both ends of the sorted scores array and move inwards. This can be faster in some cases and might help with those failing test cases.
Another potential improvement is to handle duplicate scores more effectively. Instead of using a Set, you could maintain a separate array of unique scores and their counts. This way, you can quickly determine a player’s rank without iterating through all duplicate scores.
Lastly, ensure your solution handles edge cases correctly, such as when a player’s score is higher than all existing scores or lower than the lowest score. These scenarios can sometimes cause unexpected behavior in binary search implementations.