Leaders in an Array

+10

Recibes un arreglo de enteros nums. Un elemento es un líder cuando es mayor o igual que todos los elementos que están a su derecha. El último elemento no tiene nada a su derecha, así que siempre es un líder. Devuelve todos los líderes, en el orden en que aparecen en nums de izquierda a derecha.

Función

leaders(nums: integer-array) → integer-array

numsinteger-array: el arreglo de enteros que se va a buscar
Devuelveinteger-array: los líderes de nums, de izquierda a derecha

Restricciones

1 ≤ nums.length ≤ 25000
-10⁹ ≤ nums[i] ≤ 10⁹

Ejemplos

Entrada: nums = [12, 5, 9, 3, 6, 2]
Salida: [12, 9, 6, 2]
Explicación: 2 es el último, así que va primero. 6 vence al 2 que le sigue, 9 vence a 3, 6 y 2, y 12 vence a todo. 5 pierde contra 9 y 3 pierde contra 6, así que la respuesta es [12, 9, 6, 2].

Para ir más allá

Si los valores llegan de uno en uno y después de cada uno debes informar de los líderes hasta el momento, ¿cómo actualizas la lista en tiempo amortizado O(1) por valor?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Al leer de izquierda a derecha, cada elemento requiere volver a recorrer su sufijo. Recorre desde la derecha en su lugar: lo único que necesitas saber sobre el sufijo es su valor máximo, y basta con una variable para guardarlo. Así, una comprobación O(n²) se convierte en una sola pasada.

Comprueba todo lo que está a la derecha

Correcto, pero no termina con las pruebas más grandes

Intuición

Aplica la definición: para cada índice i, recorre los elementos posteriores y detente en el primero que sea estrictamente mayor que nums[i]. Si el recorrido llega al final, nums[i] es un líder. Compruebas los índices de izquierda a derecha, así que los líderes aparecen en orden. En [12, 5, 9, 3, 6, 2], el 5 se detiene en el 9 y el 3 se detiene en el 6.

El costo está en los recorridos que llegan hasta el final. Con 24,999 valores iguales seguidos de uno mayor, cada elemento recorre casi todo el arreglo: aproximadamente 25,000 × 25,000 / 2, más de 3 × 10^8 comparaciones.

Algoritmo

Crea una lista de resultados vacía.
Para cada índice i, recorre j desde i + 1 hasta el final.
Si algún nums[j] es mayor que nums[i], detente: nums[i] no es un líder.
Si no existe tal j, añade nums[i] al resultado.
Devuelve el resultado.

def leaders(nums):
    n = len(nums)
    result = []
    for i in range(n):
        is_leader = True
        for j in range(i + 1, n):
            if nums[j] > nums[i]:  # a bigger value on the right rules it out
                is_leader = False
                break
        if is_leader:
            result.append(nums[i])
    return result

Una pasada desde la derecha con un máximo acumulado

Intuición

Ser al menos tan grande como todos los elementos de la derecha equivale a ser al menos tan grande como su máximo. Al recorrer de derecha a izquierda, puedes mantener ese máximo actualizado. El último elemento lidera y establece el máximo. Cada elemento a su izquierda lidera cuando es al menos igual al máximo y, después, se convierte en el nuevo máximo; de lo contrario, hay un valor mayor a su derecha.

En [12, 5, 9, 3, 6, 2]: 2 lidera, después 6, después 9 y después 12, mientras que 3 y 5 quedan por debajo del máximo. Encontraste [2, 6, 9, 12]; invertido, ese es el resultado.

Cada elemento se compara una vez: tiempo O(n) y espacio adicional O(1), aparte del resultado. La versión en R marca los elementos líderes en un vector logical(n), por lo que su espacio adicional es O(n).

Algoritmo

Pon el último elemento en el resultado y establece best con ese valor.
Desplaza i desde el penúltimo índice hasta 0.
Si nums[i] ≥ best, añade nums[i] al resultado y establece best con ese valor.
Invierte el resultado para que los líderes se lean de izquierda a derecha y devuélvelo.

def leaders(nums):
    n = len(nums)
    best = nums[n - 1]  # the largest value to the right of the current index
    found = [best]      # the last element is always a leader
    for i in range(n - 2, -1, -1):
        if nums[i] >= best:
            best = nums[i]
            found.append(nums[i])
    found.reverse()  # collected right to left, returned left to right
    return found

Errores comunes y casos límite

Usar > en lugar de ≥ frente al máximo actual. En [4, 7, 7, 1, 7], todos los 7 son líderes, pero una comparación estricta conserva solo el último.
Empezar el máximo en 0 en lugar de hacerlo con el último elemento. [-1, -5] debe devolver ambos, pero un máximo de 0 los descarta.
Devolver los líderes en el orden en que los encontraste, [2, 6, 9, 12] en lugar de [12, 9, 6, 2].
Añadir dos veces el último elemento al empezar el bucle en el último índice después de haberlo añadido ya al resultado.
Comparar cada elemento solo con su vecino. En [5, 3, 9], 5 supera al 3 que tiene al lado, pero el 9 hace que la respuesta sea [9].

Preguntas frecuentes3

¿Cuál es la complejidad temporal de encontrar líderes en un arreglo?

O(n) con una sola pasada desde la derecha, porque cada elemento se compara una vez con el máximo acumulado. Comprobar cada elemento con todos los que están a su derecha cuesta O(n²) en el peor de los casos, por ejemplo, cuando todos los valores son iguales.

¿El último elemento siempre es un líder?

Sí. Un líder debe ser al menos tan grande como cada elemento a su derecha, y el último elemento no tiene ninguno, así que la condición se cumple sin que haya nada que comprobar.

¿Los valores iguales cuentan como líderes?

Aquí, sí: un líder debe ser mayor o igual que todos los elementos a su derecha, así que en [4, 7, 7, 1, 7] los tres 7 son líderes. Algunas versiones exigen que sea estrictamente mayor; en ese caso, compara con >, y solo el último de los valores empatados es líder.

def leaders(nums):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

nums = [12, 5, 9, 3, 6, 2]

Salida Esperada

[12, 9, 6, 2]