Método de dos punteros

2.1 Definición del método de dos punteros.

Método de dos punteros — es una técnica utilizada para resolver diversas tareas en arrays y cadenas, donde se utilizan dos punteros (índices) que se mueven por los datos según unas reglas determinadas. Este método permite resolver eficientemente tareas relacionadas con la búsqueda de pares de elementos, subconjuntos que cumplen determinadas condiciones.

Este método implica el uso de dos punteros que, por lo general, se inicializan en extremos opuestos de la estructura de datos y se mueven uno hacia el otro o según una regla determinada. El método de dos punteros puede reducir significativamente la complejidad temporal del algoritmo en comparación con enfoques más ingenuos.

Principios básicos

1. Inicialización de dos punteros: Los punteros pueden establecerse al inicio y al final del array o cadena, o en diferentes índices según el problema.
2. Movimiento de los punteros: Los punteros se mueven según una regla determinada (por ejemplo, ambos punteros se mueven hacia el centro, o un puntero se mueve hacia adelante mientras el otro se mantiene en su lugar).
3. Verificación de la condición: En cada paso se verifica una condición que determina el movimiento futuro de los punteros o la terminación del algoritmo.

Complejidad temporal:

O(n) — en la mayoría de los casos, ya que ambos punteros recorren el array una o varias veces, pero no más de O(n) iteraciones en total.

Para algunos problemas, dependiendo de las condiciones y posiciones iniciales de los punteros, la complejidad temporal puede ser O(n log n) o O(n^2), pero esto es raro.

Ejemplos de problemas resueltos por el método de dos punteros:

2.2 Búsqueda de dos números en un array cuya suma sea igual a un número dado.

Problema:

Encontrar dos números en un array ordenado que sumen un número dado target.

Solución:

Inicializamos un puntero al inicio del array y el otro al final. Comprobamos la suma de los elementos bajo los punteros:

• Si la suma es igual a target, devolvemos los índices.
• Si la suma es menor que target, movemos el puntero izquierdo hacia la derecha.
• Si la suma es mayor que target, movemos el puntero derecho hacia la izquierda.

Complejidad temporal: O(n).

Ejemplo de código en Python:

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return left, right
        elif s < target:
            left += 1
        else:
            right -= 1
    return None
        

2.3 Verificación de palíndromo

Problema:

Verificar si una cadena es un palíndromo.

Solución:

Inicializamos punteros al inicio y al final de la cadena. Comparamos los caracteres bajo los punteros:

• Si los caracteres son iguales, movemos ambos punteros uno hacia el otro.
• Si los caracteres no son iguales, la cadena no es un palíndromo.

Complejidad temporal: O(n).

Ejemplo de código en Python:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
        

2.4 Eliminación de duplicados de un array ordenado

Problema:

Eliminar duplicados de un array ordenado.

Solución:

Usamos dos punteros, uno para la posición actual en el array resultante y otro para recorrer todos los elementos:

• Si el elemento actual no es igual al anterior, lo escribimos en el array resultante.

Complejidad temporal: O(n).

Ejemplo de código en Python:

def remove_duplicates(arr):
    if not arr:
        return 0
    write_index = 1
    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:
            arr[write_index] = arr[i]
            write_index += 1
    return write_index