Two Pointers
Es una tecnica (O patron tecnico) usada en problemas algoritmicos que utilizan una estructura de datos secuencial (arrays y listas por ejemplo). En esta tecnica se usan dos pointers (variables, referencias etc) para mantener en track indices de un array o posiciones de un string, que usualmente no son iguales.
Algunos problemas y aplicaciones tipicas de este patron serian:
- Comprobar si un string es un Palindromo
- Revertir una lista in-place
- Buscar un valor objetivo de entre una lista de valores disponibles (ordenada)
# Cuando se usa
Se usa cuando tienes que iterar sobre una coleccion de elementos y tienes que realizar comparaciones entre ellos.
- Tienes una estructura de datos lineal. String, arrays o linked lists, pj.
- Tienes que procesar datos en dos posiciones diferentes a traves de ella, simultaneamente
- Tienes que mover los punteros bajo ciertos criterios, en una o dos estructuras de datos a la vez
# Casos de Uso en el mundo Real
- Manejo de Memoria. El manejo de memoria utiliza la tecnica de dos punteros, teniendo uno al inicio de un bloque de memoria y otro al final, cuando un programa necesita de usar dichos recursos, el puntero de inicio se recorre y se obtiene una nueva longitud que es el nuevo bloque de memoria disponible.
# Problemas
- Valid Palindrome
- TwoSum
- ThreeSum
- Remove nth node from end of list
- Sort Colors
- Reverse Words in a String
- Valid Palindrome II