Entrevista técnica: Usar Quickselect para encontrar el k-ésimo elemento más grande con duplicados

Planteamiento y alcance

Dado un arreglo de enteros no ordenado nums y 1 ≤ k ≤ nums.length, devuelve el k-ésimo elemento en orden no creciente. Los duplicados ocupan posiciones separadas: el segundo valor más grande en [5, 5, 4] es 5, no el segundo valor distinto. El tiempo promedio objetivo es O(n) con O(1) de espacio adicional cuando se permite mutar el arreglo; declara esa suposición antes de codificar.

Lo que el entrevistador está evaluando

Una respuesta sólida mapea el “k-ésimo más grande” al índice ascendente target = n-k, luego explica que la partición solo necesita establecer un límite alrededor del pivote; el otro lado nunca necesita ser ordenado. Maneja duplicados, k=1, k=n, entradas ordenadas y la diferencia entre la complejidad promedio aleatorizada y una garantía de peor caso.

Aclaraciones antes de codificar

1. ¿Se puede modificar la entrada? La partición in situ requiere O(1) de espacio adicional; preservarla requiere una copia O(n).
2. ¿Se trata de la k-ésima posición o del k-ésimo valor distinto? El conteo por posición es el planteamiento habitual; la selección de elementos distintos necesita un manejo diferente de duplicados.
3. ¿Llegan los datos como un flujo continuo (stream)? Quickselect es para un arreglo materializado; un min-heap de tamaño k ofrece un procesamiento de O(n log k) para un flujo continuo.
4. ¿Es obligatorio un límite determinista para el peor caso? Quickselect aleatorizado tiene un promedio de O(n); se necesita mediana de medianas o una garantía de biblioteca para afirmar un peor caso estricto.

Solución recomendada y derivación

Usa una partición de tres vías en valores menores, iguales y mayores que el pivote. Para el índice ascendente convertido target, continúa con el intervalo izquierdo cuando el objetivo se encuentra a la izquierda de lt, el intervalo derecho cuando se encuentra a la derecha de gt, y devuelve el pivote cuando se encuentra en [lt, gt]. La franja de iguales hace que una entrada con todos los elementos iguales termine en una sola pasada en lugar de descartar repetidamente un elemento.

import random

def kth_largest(nums: list[int], k: int) -> int:
    if not 1 <= k <= len(nums):
        raise ValueError("k out of range")
    target = len(nums) - k
    left, right = 0, len(nums) - 1
    while left <= right:
        pivot = nums[random.randint(left, right)]
        lt, i, gt = left, left, right
        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1; i += 1
            elif nums[i] > pivot:
                nums[i], nums[gt] = nums[gt], nums[i]
                gt -= 1
            else:
                i += 1
        if target < lt:
            right = lt - 1
        elif target > gt:
            left = gt + 1
        else:
            return pivot
    raise RuntimeError("unreachable")

Cada iteración recorre su intervalo actual una vez. Si el pivote reduce el intervalo en una fracción constante, T(n)=T(cn)+O(n) produce un promedio de O(n); seleccionar repetidamente un extremo sigue dando O(n²) en el peor caso. La forma iterativa evita la profundidad de recursión y usa O(1) de espacio adicional.

Alternativas y compensaciones

El ordenamiento completo es el más fácil de verificar, cuesta O(n log n) y es razonable cuando el arreglo es pequeño o se necesita un orden completo más adelante. Un min-heap de tamaño k preserva la entrada y cuesta O(n log k) de tiempo y O(k) de espacio, lo cual se adapta a flujos continuos o cuando k es mucho menor que n. std::nth_element en C++ expone la misma semántica de partición con complejidad lineal promedio; no ordena ninguno de los lados de la posición seleccionada.

Modos de falla, casos límite y contraejemplos

• Escribir target = k-1 encuentra el k-ésimo valor más pequeño, invirtiendo el orden solicitado.
• Una partición de dos vías que descarta solo un elemento igual puede tomar O(n²) en [7, 7, 7, ...]; la partición de tres vías consume la franja de iguales de una sola vez.
• Elegir siempre el último elemento puede degradarse en entradas ordenadas y ordenadas inversamente. La aleatorización reduce la probabilidad, no el límite asintótico del peor caso.
• El “k-ésimo más grande distinto” no puede reutilizar la condición de parada sin contar o eliminar la franja de iguales.
• Rechaza un arreglo vacío, k=0 o k>n en el límite en lugar de permitir que un error de índice oculte un planteamiento inválido.

Pruebas y lista de verificación

Compara casos aleatorizados con sorted(nums)[-k]; incluye valores todos iguales, negativos y duplicados, k=1, k=n, entrada ordenada y entrada ordenada inversamente. Cuando se permite la mutación, valida el resultado en lugar del orden completo del arreglo. Fija la semilla aleatoria para la reproducibilidad y registra los conteos de comparaciones a medida que n crece; una ejecución afortunada no es una prueba de complejidad.

Preguntas de seguimiento

¿Cómo se puede garantizar un peor caso lineal?

Elige un pivote de mediana de medianas para que cada ronda elimine una fracción fija, dando un tiempo de peor caso de O(n). Sus constantes son más altas, por lo que el código de producción suele elegir la selección aleatorizada o una implementación de la biblioteca estándar.

¿Cómo lo cambias al k-ésimo más pequeño?

Usa target = k-1 manteniendo la partición ascendente. Mantener la formulación del más grande como target=n-k suele ser más claro que invertir el arreglo.

¿Cómo soportas inserciones y muchas consultas de rango?

Quickselect de una sola pasada vuelve a escanear en cada consulta. Para un k fijo, mantén un min-heap de tamaño k; para consultas de rango arbitrarias, considera un árbol balanceado aumentado con tamaños de subárbol y elige según la proporción de actualizaciones a consultas.