Solución: Climbing the Leaderboard

Climbing the leaderboard.md

Solución: Climbing the Leaderboard

URL: https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem

Lo había intentado antes y me había trabado siempre en el mismo lugar: timeout con inputs grandes. Probé casi las mismas "optimizaciones" que antes ("cache", pseudo búsqueda binaria) pero siempre daba timeout. Finalmente me inspiré: las posiciones en la tabla equivalen al índice del array de puntajes ordenado de manera decreciente, más uno.

TL;DR: el problema no era complejo, solamente había que eliminar los puntajes duplicados para tener rápidamente la tabla de puntajes "calculada", o calculable.

function climbingLeaderboard(ranked, player) {
    ranked.sort((a, b) => b - a);
    ranked = ranked.filter((value, index) => index > 0 ? (value !== ranked[index - 1]) : true);
    
    const rankedLength = ranked.length;
    
    const cache = {};

    return player.map(score => {
        if (cache[score]) {
            return cache[score];
        }
        
        if (score > ranked[0]) {
            cache[score] = 1;
            return cache[score];
        }
        
        if (score < ranked[rankedLength - 1]) {
            cache[score] = rankedLength + 1;
            
            return cache[score];
        }
        
        let start = 0;
        let middle = Math.round(rankedLength / 2);
        
        while (ranked[middle] > score) {
            start = middle;
            middle += Math.round(middle / 2);
        }
        
        for (let i = start; i < rankedLength; i++) {
            if (ranked[i] <= score) {
                cache[score] = i + 1;
                
                return cache[score];
            }
        }
    });
}

En limpio, el algoritmo sería así:

function climbingLeaderboard(ranked, player) {
    ranked.sort((a, b) => b - a);
    ranked = ranked.filter((value, index) => index > 0 ? (value !== ranked[index - 1]) : true);
    
    const rankedLength = ranked.length;

    return player.map(score => {
        if (score > ranked[0]) {
            return 1;
        }
        
        if (score < ranked[rankedLength - 1]) {
            return rankedLength + 1;
        }
        
        for (let i = 0; i < rankedLength; i++) {
            if (ranked[i] <= score) {
                return i + 1;
            }
        }
    });
}

Si bien es relativamente eficiente, requiere de las optimizaciones de la versión anterior para pasar todos los inputs sin timeout.