A solution of the O(n + m * log(n)) complexity has been implemented,
where n is the size of the scores array and m is the size of the alice array.
The solution consists of the 4 parts:
binarySearchInDescendingArray(scores, aliceScore) - a typical binary search for computing the index for the given aliceScore in the reverse-ordered scores array, the complexity is O(log(n)).
findPlaces(scores) - computes the places for the given scores, the complexity is O(n).
findPlace(scores, places, aliceScore) - computes the place for the given aliceScore, the complexity is just O(1), because the places and the index are already computed.
climbingLeaderboard(scores, alice) - computes the places for each Alice's score in the given alice array, the complexity is O(n + m * log(n)) appropriately.
O(n + m * log(n))
complexity has been implemented, wheren
is the size of thescores
array andm
is the size of thealice
array.binarySearchInDescendingArray(scores, aliceScore)
- a typical binary search for computing the index for the givenaliceScore
in the reverse-orderedscores
array, the complexity isO(log(n))
.findPlaces(scores)
- computes theplaces
for the givenscores
, the complexity isO(n)
.findPlace(scores, places, aliceScore)
- computes the place for the givenaliceScore
, the complexity is justO(1)
, because theplaces
and theindex
are already computed.climbingLeaderboard(scores, alice)
- computes the places for each Alice's score in the givenalice
array, the complexity isO(n + m * log(n))
appropriately.