2
\$\begingroup\$

The array "scores" tells the total points for each person involved in a contest. So for example:

User A: 100 points
User B: 90 points
User C: 90 points
User D: 80 points
User E: 75 points
User F: 60 points

According to above scores we also have this ranking:

User A: #1
User B: #2  
User C: #2
User D: #3
User E: #4
User F: #5

This ranking method follows the Dense Ranking method.

Then we have a user named alice. If she gets 55 points, she will rank at position #6 (according to ranking above). If she scores 90 points, she will rank at position #2. And so on.

I actually have an array containing different "sessions" for alice. So having for example:
[55, 90]

This means that first time will alice be ranked at position #6. While second time she will be ranked at position #2.

I coded this, and it work. However, this does not seem to be very effective. For large datasets, with half million entries in the scores-array, it times out. This is the code:

const getPosition = (element, scores) => {
    scores.push(element);
    scores.sort(function (a,b) { return b-a; });
    return scores.indexOf(element)+1;
}

function climbingLeaderboard(scores, alice) {
    var uniqueSet = new Set(scores);
    scores = [...uniqueSet];
    var positions = [];
    let aliceIndex = 0;
    while(aliceIndex < alice.length){
        positions.push(getPosition(alice[aliceIndex], scores));
        aliceIndex++;
    }
    return positions;
}

function main() {
    const scores = [100, 90, 90, 80, 75, 60];
    const alice = [50, 65, 77, 90, 102];
    let result = climbingLeaderboard(scores, alice);
    console.log(result.join("\n") + "\n");
}

I guess the "sort"-function and/or searching for the element in the array with indexOf is the problem. But I could not find a way to make these two operations more efficient.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ You shouldn't be sorting the array multiple timtes over. Instead just sort the array without Alice once, and then use a binary search to find out where Alice's score should go. \$\endgroup\$ Jun 21 '20 at 15:20
  • \$\begingroup\$ @Countingstuff The array is already sorted by default. IN that case I would not need to sort. You are saying that I would need to make a loop and for each iteration, I would need to just put the score in the "right position" in the array? And also get back the index where to element was added? I tried to google this, but could not find that much. Would be great if you hade some link to share. \$\endgroup\$
    – oderfla
    Jun 21 '20 at 20:58
  • \$\begingroup\$ Note quite that, in fact there is no need to do insertions either. Please clarify a point for me and I will post an answer. Your solution with scores = [100, 100, 100, 100] and alice = [100, 100, 102, 101] gives 1, 1, 1, 2. Is this correct or should it be 2, 2, 1, 2? Or something else \$\endgroup\$ Jun 21 '20 at 21:35
  • \$\begingroup\$ Ok. It should give: 1, 1, 1, 2 \$\endgroup\$
    – oderfla
    Jun 21 '20 at 22:10
  • 1
    \$\begingroup\$ Sorry, I posted an answer but then I realise I'm still not sure about the expected output. For scores = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] and alice = [ 0, 0, 0, -1 ] your function gets 1,1,1,5. Is this correct? Should it not be 1,1,1,2? \$\endgroup\$ Jun 21 '20 at 23:41
3
\$\begingroup\$

The following function sort of agrees with your function. Except that for example your function given scores = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] and alice = [ 0, 0, 0, -1 ] gets 1,1,1,5, while I think it should be 1,1,1,2.

Anyway, it easily handles scores arrays of sizes 10^7 for scores and 10^5 for alice.

The idea is, we already know scores is sorted as per your comment. We can then go through the scores array. We sort the alices array while remembering the original order. Then we go through the scores array, we first look at the largest alice, once we hit an element >= it, it is time to note that down, we remember the score and whether it was a tie and the position it happened at. We continue traversing scores, now looking at the next biggest alice, etc.

At the end of this we know where each alice would be ranked in the original array. Now we just need to account for the rank increases that come from prior alices, basically the rule is, if you are alice 7, then you look at the previous scores from alices 1 to 6 which resulted in a rank increase, and count 1 each time their score was larger than yours. We can do this fairly quickly by maintaining a sorted array of the previous scores using a binary search to find where to insert the next element. Remembering to account for ties amongst Alices scores.

function binarySearch(array, targetValue) {
    if (array.length === 0) {
        return 0;
    }
    let min = 0;
    let max = array.length;
    let guess;

    while (max - min > 1) {
        guess = Math.floor((max + min) / 2);

        if (array[guess] > targetValue) {
            min = guess;
        } else {
            max = guess;
        }
    }

    return array[min] < targetValue ? min : min + 1;
}


function climbingLeaderboard(scores, alice) {
    if (alice.length === 0) {
        return [];
    }
    const sortedAliceWithIndex = alice.map((s, i) => [s, i]).sort(([a], [b]) => b - a);

    let aliceInd = 0;
    let currAlice = sortedAliceWithIndex[aliceInd][0];
    const ranks = [];
    let i = 0;
    let effectiveCount = 0;
    while (true) {
        const currScore = scores[i];
        if (currScore !== undefined && currScore > currAlice) {
            i++;
            if (!(scores[i] === scores[i - 1])) {
                effectiveCount++;
            }
            continue;
        }

        ranks.push([
            effectiveCount,
            sortedAliceWithIndex[aliceInd][1],
            currAlice === currScore,
            currAlice
        ]);
        aliceInd++;

        if (aliceInd >= alice.length) {
            break;
        }
        currAlice = sortedAliceWithIndex[aliceInd][0];
    }

    const inOriginalAliceOrder = ranks.sort(([, i1], [, i2]) => i1 - i2);

    const accountingForRanks = [];
    let rankIncreases = [];
    for (let [i, _, tie, score] of inOriginalAliceOrder) {
        let rankUp = binarySearch(rankIncreases, score);

        if (rankIncreases[rankUp - 1] === score) {
            accountingForRanks.push(i + rankUp);
        } else {
            accountingForRanks.push(i + rankUp + 1);
            if (!tie) {
                rankIncreases.splice(rankUp, 0, score);
            }
        }
    }
    return accountingForRanks;
}

The following runs in a couple of seconds for me.

function main() {
    let scores = new Array(10 ** 6);
    for (let i = 0; i < scores.length; i++) {
        scores[i] = 1 * Math.random();
    }
    scores.sort((a, b) => b - a);
    let alice = new Array(10 ** 5);
    for (let i = 0; i < alice.length; i++) {
        alice[i] = 2 * Math.random() - 1;
    }

    let result1 = climbingLeaderboard(scores, alice);

    console.log(result1);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.