Alice is playing an arcade game and wants to climb to the top of the leaderboard and wants to track her ranking. 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, the four players on the leaderboard have high scores of 100, 90, 90, and 80. Those players will have ranks 1, 2, 2, and 3, respectively. If Alice’s scores are 70, 80, and 105, her rankings after each game are 4, 3, and 1.
Complete the climbingLeaderboard function in the editor below. It should return an integer array where each element res[j] represents Alice’s rank after the jth game.
climbingLeaderboard has the following parameter(s):
- scores: an array of integers that represent leaderboard scores
- Alice: an array of integers that represent Alice’s scores
So if Alice will get [5, 25, 50, 120], then these scores will be with the next ranks [6, 4, 2, 1].
About Binary Search
Medium exercises always have some background. This exercise can be solved in a non-optimized way, but HackerRank won’t give you 100%. It will be a problem with complexity.
The answer is Binary Search. I will give you some markers which can help you to decide if Binary Search can help you in any exercise.
It can be a Binary Search If:
- You have a sorted sequence (from min to max or max to min)
- You need to find a place of some value in sequence or place of closest value in this sequence (search exercise)
This exercise can be solved with a linear algorithm with O(n) complexity. It is easy to understand what it is. Let say that 1 iteration gets 1 second. If your sequence has 1 million items it will have 1 million iterations and it will take 1 million seconds. But binary search gives us a log2(n) complexity, and this exercise can be solved with only 19,932 iterations instead of 1 million. And it is so cool for the complexity.
Binary Search is simple for understanding. If you have a sorted array from min to the max for example — [1, 2, 3, 4, 5, 6, 7, 8], and you need to find the index of number 7 then you can easily use binary search for this. At first, you need to find the mid-index of this sequence.
mid-index = array.count / 2 = 8 / 2 = 4.
Now we can check if the number on index 4 is greater or lower then our searched value. Okay, 7 is greater than 5, it means that we don’t need to check numbers from 0 to 4 indexes. We know that all numbers which stand left from number 5 are lower than 5. And it is a method of binary search. We need to get a mid-index of sequence and search only in the needed part of the sequence.
With an understanding of binary search, we can easily find the closest values of each Alice’s score with a small number of iterations. At first, we need to create a table of places that depend on the input table. After that, find the closest value to each score of Alice. And that’s all. With closest values, we can define the place of Alice with each of the input scores.