Optimize performance for dense ranking algo

Question

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]
}

user_844416 · Answer

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)

user_5902313 · Answer

Some of the key points to keep in mind to optimize your data structure and algorithms using javascript, is to:

Avoid using prototype functions as much as possible when using javascripts.
Find alternatives to making unnecessary large storage.
Skip some repeating steps by breaking through loops when they are no longer needed.

Keeping the above in mind, here is what my solution would look like.

    function climbingLeaderboard(scores: number[], alice: number[]): number[] {
        var rankings : number[] = [];
        var positions: number = 0;
        
        for (var index = 0; index < scores.length; index++) {
            if (index === 0 || scores[index] < scores[index - 1]) {
                positions++;
            }
        }
        
        let startingIndex = scores.length - 1;
        for(var jndex = 0; jndex < alice.length; jndex++) {
            for(var index = startingIndex; index >= 0; index--) {
                if (scores[index] >= scores[index - 1]) {
                    continue;
                }
                
                if (alice[jndex] < scores[index]) {
                    startingIndex = index;
                    break;
                }
                
                if (alice[jndex] >= scores[index]) {
                    positions--;
                }
            }
            rankings[rankings.length] = positions + 1;
        }
        return rankings;
    }

Optimize performance for dense ranking algo

2 Answers