I'm doing this challenge to assign dense rankings to a player's score compared to a leadingboard. My following code works, but takes too long to run (some tests on the site fail on timeout error).
I'm wondering what else can I optimize? Any ideas?
function climbingLeaderboard(scores, alice) {
const reducedScores = getReducedScores(scores)
let lastIdxHit = reducedScores.length - 1
return alice.map((a) => {
for (let i = lastIdxHit; i >= 0; i--) {
const rs = reducedScores[i]
if (a < rs.value) {
return rs.rank + 1
}
lastIdxHit = i - 1
}
return 1
})
}
function getReducedScores(scores) {
let rank = 0
return scores.reduce((acc, s) => {
if (last(acc) && last(acc).value === s) {
return acc
}
rank++
return acc.concat({ value: s, rank })
}, [])
}
function last(arr) {
return arr[arr.length - 1]
}
Your code performs full search of every alice[] value in scores to determine it's rank, so time complexity is quadratic O(n*m).
But both arrays are sorted scores is in descending order. alice are in ascending order.
We can exploit this fact to make linear search.
In this Python code the first part finds rank at the array end.
Then for every alice element we look for appropriate place, correcting rank when scores changes.
scores = [100, 100, 50, 40, 40, 20, 10]
alice = [5, 25, 50, 120]
#scores = [100, 90, 90, 80, 75, 60]
#alice = [50, 65, 77, 90, 102]
n = len(scores)
m = len(alice)
rank = 1
for i in range(1, len(scores)):
if scores[i] < scores[i-1]:
rank +=1
j = len(scores) - 1
for a in alice:
while j >= 0 and a >= scores[j]:
j -=1
if (j < 0) or (scores[j] > scores[j+1]):
rank -=1
print(rank+1)
output
6 4 2 1
#6 5 4 2 1
Both score index j and alice index i move in one direction only (forward and backward), so complexity is linear O(m+n)