Patrón 2: Los dos punteros — Triunfando en la entrevista de código
Hola, bienvenido al segundo artículo de la serie: Patrones para triunfar en la entrevista de código. Donde tratamos de identificar los patrones que hay detrás de las preguntas de algoritmos usando ejemplos reales de entrevistas.
En el artículo pasado hablamos sobre la ventana deslizante. Y hoy toca el turno de Los dos punteros. Otro patrón muy útil para resolver problemas con listas/arreglos.
¿Cómo identificar un problema que usa los dos punteros? 🤓
Podemos identificar este patrón cuando el problema involucra una lista ordenada, hay un conjunto de elementos(pares, triples o incluso subarreglos) y hay un valor objetivo que encontrar o duplicados que remover.
Como siempre, para entender mejor utilizaremos un problema de ejemplo:
Dada una lista de enteros, regresa los índices de los dos números que sumen un valor específico.
Puedes asumir que sólo habrá una solución y que no puedes utilizar el mismo elemento dos veces.Las entradas del problema son:
números = [1, 2, 7, 11, 19]
suma = 9
----------------------------solución = [1, 2]
Nos piden encontrar los índices de dos de los números de la lista que sumen 9. Así que vamos a resolverlo. 👊
Solución por fuerza bruta
La solución más obvia para este problema es muy simple: sólo necesitamos iterar cada elemento x de nuestra lista de números y encontrar si hay algún otro valor que sea igual a suma — x
El problema con esta solución es que para cada elemento volvemos a iterar todos los números para ver si encontramos la suma que buscamos. En otras palabras, usamos un for anidado dentro de otro for, lo que nos deja con una complejidad de O(n^2)
Una manera más eficiente de resolver este problema es usando la técnica de los dos punteros, con la cual logramos tener una complejidad de O(n)
Paso 1: Crear dos punteros. Uno al principio de la lista y otro al final
Un puntero puede ser simplemente una variable que tome como valor un índice de la lista. Para nuestro ejemplo el puntero 1 tiene el valor del índice 0 y el puntero 2 el valor del índice 4.
Paso 2: Verificar si la suma de los dos valores es igual a nuestro objetivo
- Si la suma de los dos valores es igual al objetivo, entonces encontramos el par y sólo deberíamos devolver sus índices.
- Si la suma es mayor, entonces necesitamos una suma menor por lo que vamos a disminuir el puntero 2.
- Si la suma es menor, entonces necesitamos una suma mayor por lo que vamos a aumentar el puntero 1.
Recuerda que la única razón por la que si aumentamos o disminuimos los punteros nuestra suma aumenta o disminuye es porque la lista está ordenada.
La solución programada en python 🎉:
Explicación del código 🚀
El código básicamente es el algoritmo que explicamos arriba.
puntero_izquierdo = 0
puntero_derecho = len(numeros) - 1Asignamos nuestros dos punteros con el valor inicial y final de la lista.
while puntero_izquierdo < puntero_derecho:
suma_actual = numeros[puntero_izquierdo] +
numeros[puntero_derecho]Mientras que el puntero izquierdo sea menor al puntero derecho sumaremos los valores y revisaremos las 3 condiciones que mencionamos.
if suma_actual == suma:
return [puntero_izquierdo, puntero_derecho]Si la suma de los dos valores es igual al objetivo, entonces encontramos el par y sólo deberíamos devolver sus índices.
if suma > suma_actual:
puntero_izquierdo += 1Si la suma es menor, entonces necesitamos una suma mayor por lo que vamos a aumentar el puntero izquierdo.
else:
puntero_derecho -= 1Si la suma es mayor, entonces necesitamos una suma menor por lo que vamos a disminuir el puntero derecho.
return [-1, -1]Por último, en caso de que los punteros lleguen a estar en la misma posición, sabemos que no encontramos elementos que sumaran el objetivo por lo que devolvemos un valor cualquiera. ¡Y listo! 🤩
La práctica lo es todo
¡La única forma de perfeccionar cualquier habilidad es practicando! En el siguiente repositorio encontrarás una lista de problemas que te sugiero resolver.
Te recomiendo que le dediques 20–25 minutos a resolver cada uno. Si no lo logras resolver en este tiempo, puedes irte al branch soluciones donde encontrarás el problema resuelto, trata de entenderlo por a lo mucho 15 minutos para pasar al siguiente problema y al día siguiente o después de un tiempo considerable intentarlo de nuevo.
¿Tienes alguna duda, sugerencia u opinión? ¡No olvides dejarla en los comentarios!
Mis artículos son gratuitos pero siempre puedes apoyarme dejando apretado el botón de aplauso y regalarme 50 👏, eso me motiva a seguir escribiendo.
Puedes seguir la charla en Twitter, Github, LinkedIn, Instagram o mandarme un correo a alexmaguey1@gmail.com
¡Gracias por leer y hasta la próxima!
