¿Cómo optimizar algoritmos en arreglos y listas con la técnica de dos punteros?

La optimización de algoritmos mediante el recorrido de colecciones es una de las habilidades más valiosas al resolver problemas de diseño de software. En este artículo, analizamos la técnica de dos punteros, una estrategia lineal altamente eficiente.

La técnica de dos punteros (Two Pointers) es uno de los patrones de optimización de algoritmos más recurrentes y efectivos. Consiste en emplear dos o más índices para recorrer una estructura iterable de manera coordinada. Su verdadero poder radica en transformar soluciones de fuerza bruta con complejidad temporal cuadrática O(n^2) en elegantes algoritmos lineales de O(n), manteniendo un consumo de memoria constante de O(1).

Tabla de Contenidos

• Del Bucle Anidado al Recorrido Coordinado
• Variante A: Direcciones Opuestas (Extremos Opuestos)
  • ¿Cuándo se aplica?
  • Implementaciones prácticas en Go
  • La Intuición Matemática e Invariantes
• Variante B: Mismo Sentido (Puntero Rápido y Lento)
  • ¿Cuándo se aplica?
  • Implementaciones prácticas en Go
  • La Invariante del Prefijo Seguro
• Variante C: Ventana Deslizante (Sliding Window)
• Tabla Comparativa de Variantes
• Para no morir en el intento y consejos que no pediste
• Conclusión: El camino hacia la eficiencia lineal

Del Bucle Anidado al Recorrido Coordinado

Imagínate que estás ordenando una fila de libros por tamaño o buscando dos cartas en una baraja que sumen un valor específico. Si tuvieras que revisar cada libro contra todos los demás, tardarías una eternidad. Eso es exactamente lo que hace una solución de fuerza bruta con dos bucles anidados: para cada elemento, reinicia la búsqueda desde cero, incurriendo en un costo cuadrático de O(n^2).

En su lugar, es mucho más inteligente usar ambas manos de manera coordinada. Puedes deslizar una mano desde el libro más barato y otra desde el más caro (extremos opuestos), o bien mover una mano para leer y otra para escribir en una misma libreta a velocidades diferentes (mismo sentido). Esta coordinación para descartar opciones inútiles sin necesidad de visitarlas es la esencia de la técnica de dos punteros.

Al operar de manera coordinada, procesamos la estructura en un único recorrido lineal de O(n). Lo mejor de todo es que, al trabajar directamente sobre la estructura original (in-place), no dependemos de estructuras auxiliares como Hash Maps para recordar estados previos, conservando un consumo de memoria óptimo de O(1).

A continuación, analizaremos en detalle cómo y cuándo aplicar cada una de las variantes lógicas de este patrón.

Variante A: Direcciones Opuestas (Extremos Opuestos)

En esta modalidad, los punteros se inicializan en los extremos más lejanos de la colección (por ejemplo, left = 0 y right = n - 1) y avanzan de forma convergente hacia el centro hasta que se encuentran o se cruzan (left < right).

¿Cuándo se aplica?

Esta variante es la herramienta ideal cuando te enfrentas a dos escenarios específicos:

1. Validación de Simetría (Espejo): Cuando el problema exige validar si una estructura cumple con una propiedad simétrica (como verificar si un texto es idéntico de izquierda a derecha y de derecha a izquierda). En este caso, la colección no requiere estar ordenada.
2. Búsqueda de Pares en Estructuras Ordenadas (Monotonía): Cuando necesitas encontrar dos elementos que sumen un valor objetivo o satisfagan una inecuación. Aquí, el ordenamiento previo es un prerrequisito obligatorio, ya que la dirección del movimiento de los punteros depende directamente de la magnitud de los valores.

Implementaciones prácticas en Go

Para entender cómo se traduce esta lógica a código real, consideremos dos de los algoritmos más representativos de la variante.

Ejemplo 1: Verificación de palíndromos (Simetría)

Este algoritmo compara los extremos externos hacia el centro, deteniéndose inmediatamente si detecta una discrepancia.

package main

// esPalindromo valida si un string es igual al leerse al derecho y al revés.
func esPalindromo(s string) bool {
    runes := []rune(s)
    left, right := 0, len(runes)-1

    for left < right {
        if runes[left] != runes[right] {
            return false // Interrupción temprana ante asimetría
        }
        left++
        right--
    }
    return true
}

Ejemplo 2: Two Sum en un arreglo ordenado (Monotonía)

Aprovechando el orden ascendente, incrementamos la suma moviendo el izquierdo, o la reducimos moviendo el derecho.

package main

// twoSumOrdenado busca los índices de dos números que sumen exactamente el valor target.
func twoSumOrdenado(nums []int, target int) (int, int, bool) {
    left, right := 0, len(nums)-1

    for left < right {
        sumaActual := nums[left] + nums[right]
        if sumaActual == target {
            return left, right, true
        } else if sumaActual < target {
            left++ // Necesitamos una suma mayor, avanzamos el menor
        } else {
            right-- // Necesitamos una suma menor, retrocedemos el mayor
        }
    }
    return -1, -1, false
}

La Intuición Matemática e Invariantes

¿Por qué podemos ignorar miles de combinaciones en Two Sum ordenado sin evaluarlas explícitamente? La respuesta reside en la monotonía de la ordenación. Al estar ordenado de forma ascendente, sabemos matemáticamente que:

Si la suma $S = A[left] + A[right]$ es mayor al objetivo, entonces cualquier suma de $A[right]$ con elementos en el rango [left, right - 1] también será obligatoriamente mayor. Por ende, A[right] no puede formar parte de ninguna solución válida y es descartado de forma segura retrocediendo right--.

Formalmente, demostramos la validez del algoritmo mediante la Invariante de Bucle:

"Si existe una solución válida en los índices $(i, j)$ , entonces esta siempre se encontrará dentro de la ventana de búsqueda actual: $left \le i < j \le right$ ."

Al iniciar, la ventana abarca el arreglo completo. Al descartar un extremo que matemáticamente no puede combinar con ningún otro elemento activo, reducimos el rango garantizando que la invariante siga siendo verdadera. Si los punteros se cruzan sin encontrar la solución, la ventana se reduce a cero elementos, lo que demuestra rigurosamente que la solución no existe en la colección.

Una vez comprendido cómo convergen los extremos, podemos analizar el escenario donde ambos punteros avanzan hacia la misma dirección.

Variante B: Mismo Sentido (Puntero Rápido y Lento)

A diferencia de la variante de extremos opuestos, aquí ambos punteros comienzan en el mismo extremo de la colección y se desplazan de izquierda a derecha. Sin embargo, se diferencian en su velocidad de avance o en las condiciones bajo las cuales se mueven.

¿Cuándo se aplica?

Esta variante se utiliza en tres subtipos de problemas muy definidos:

1. Compactación o Filtrado In-Place: Cuando necesitas eliminar duplicados o filtrar elementos que cumplan una condición (ej. mover ceros al final). El puntero rápido inspecciona el arreglo y el lento marca la frontera donde debe escribirse el siguiente elemento válido.
2. Velocidad Relativa (Tortuga y Liebre): Utilizado principalmente en listas enlazadas para detectar ciclos (Algoritmo de Floyd) o encontrar el punto medio en una sola pasada. El puntero rápido avanza a velocidad 2X y el lento a 1X.
3. Desfase Fijo (Fixed Gap): Cuando necesitas acceder a una posición relativa al final (ej. el n-ésimo nodo final). Los punteros inician separados por una distancia constante N, y luego avanzan juntos a la misma velocidad.

Implementaciones prácticas en Go

Veamos cómo se implementa cada uno de estos tres subtipos prácticos.

Ejemplo 1: Eliminar duplicados in-place (Compactación)

El puntero lento (slow) solo avanza para escribir cuando el puntero rápido (fast) encuentra un valor nuevo diferente al último consolidado.

package main

// removeDuplicates compacta un arreglo ordenado in-place y retorna la nueva longitud.
func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    slow := 0
    for fast := 1; fast < len(nums); fast++ {
        if nums[fast] != nums[slow] {
            slow++
            nums[slow] = nums[fast] // Escribimos en la frontera segura
        }
    }
    return slow + 1
}

Ejemplo 2: Encontrar el punto medio de una lista enlazada (Velocidad Relativa)

Dado que el puntero rápido avanza el doble de rápido, cuando este llega al final, el puntero lento estará exactamente a la mitad del trayecto.

package main

type ListNode struct {
    Val  int
    Next *ListNode
}

// middleNode retorna el nodo central de una lista enlazada.
func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head

    // El rápido avanza dos pasos, el lento uno
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

Ejemplo 3: Eliminar el n-ésimo nodo desde el final (Desfase Fijo)

Primero distanciamos el puntero rápido N posiciones del puntero lento. Al mover ambos a la par, el lento se ubicará justo antes del nodo a eliminar cuando el rápido alcance el final.

package main

// removeNthFromEnd elimina el n-ésimo nodo empezando desde el final de la lista.
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    slow, fast := dummy, dummy

    // 1. Crear el desfase fijo de N elementos
    for i := 0; i <= n; i++ {
        if fast == nil {
            return head
        }
        fast = fast.Next
    }

    // 2. Avanzar juntos manteniendo la distancia constante
    for fast != nil {
        slow = slow.Next
        fast = fast.Next
    }

    // 3. Desconectar el nodo objetivo
    slow.Next = slow.Next.Next
    return dummy.Next
}

La Invariante del Prefijo Seguro

La corrección de las operaciones de compactación in-place se fundamenta en una invariante específica llamada Prefijo Seguro:

"Todos los elementos ubicados a la izquierda del puntero de escritura (slow) están garantizados a contener datos procesados en su estado final correcto y no serán modificados nuevamente."

Al garantizar esta propiedad en cada paso, podemos sobrescribir el arreglo original sin temor a destruir información útil no procesada, ya que el puntero de lectura (fast) siempre va por delante de la frontera de escritura (slow).

Una vez analizadas las variantes lineal y de velocidad relativa, cabe mencionar la tercera categoría, enfocada en subarreglos continuos de tamaño dinámico.

Variante C: Ventana Deslizante (Sliding Window)

Aunque a menudo se estudia como una técnica independiente, la Ventana Deslizante (Sliding Window) es una evolución directa de los dos punteros en el mismo sentido.

• Mecánica: Los dos punteros no representan lectura/escritura o velocidad, sino los límites de una "ventana" activa (start y end). El puntero end avanza hacia la derecha expandiendo la ventana para incorporar nuevos datos. Cuando la ventana activa viola una restricción de negocio (por ejemplo, supera una suma máxima o tiene demasiados caracteres únicos), el puntero start avanza para encoger la ventana hasta que vuelva a ser válida.
• Diferencia clave: A diferencia de la compactación, la ventana deslizante no modifica la estructura original; la utiliza para calcular propiedades acumulativas (como sumas máximas, promedios o subsecuencias) en rangos continuos del arreglo.

Tabla Comparativa de Variantes

Para seleccionar el patrón adecuado durante un diseño técnico, es útil contrastar sus requerimientos de recursos y comportamiento:

Para no morir en el intento y consejos que no pediste

• Cuidado con los errores de desbordamiento (Off-By-One): En la variante de extremos opuestos, la condición del ciclo debe ser cuidadosamente evaluada. Usar left < right evita que los punteros se crucen en el centro, lo cual es ideal para evaluar parejas de elementos. Sin embargo, si necesitas procesar el elemento central individual en un arreglo impar, la condición podría requerir left <= right.
• Riesgo de Nil Pointer Dereference en Listas Enlazadas: Al implementar la velocidad relativa (Tortuga y Liebre), el puntero rápido avanza dos pasos en cada iteración (fast.Next.Next). Si no validas rigurosamente que tanto fast como fast.Next no sean nulos antes de avanzar, tu aplicación fallará catastróficamente con un pánico en tiempo de ejecución.
• Destrucción de datos in-place: Recuerda que compactar o reordenar un arreglo in-place sobrescribe el contenido original. Si tu aplicación requiere conservar la entrada original intacta para otros procesos paralelos, debes realizar una copia explícita en memoria antes de aplicar la técnica.
• Sincronización Simétrica al Mover Ceros: Al compactar elementos inactivos (como en el ejercicio de "Move Zeroes"), es mandatorio inicializar ambos punteros en 0 (s = 0, f = 0). Si inicializas asimétricamente en f = 1 y el primer elemento del arreglo es un valor activo no nulo, el algoritmo realizará intercambios destructivos innecesarios que alterarán el orden relativo original del arreglo.

Conclusión: El camino hacia la eficiencia lineal

Dominar la técnica de dos punteros no consiste en memorizar algoritmos específicos, sino en desarrollar la intuición espacial y matemática para identificar cuándo la ordenación o la estructura física de los datos nos permite descartar combinaciones de forma segura. Ya sea convergiendo desde los extremos opuestos para validar simetría o encontrar sumas, compactando datos en un solo sentido gracias al prefijo seguro, o midiendo velocidades relativas para detectar ciclos en una lista enlazada, este patrón se consolida como uno de los recursos más potentes para optimizar la complejidad temporal a O(n) sin sacrificar memoria adicional.

El diseño óptimo de software exige reconocer estas invariantes lógicas. Al integrar esta estrategia en tu caja de herramientas, logras que tus implementaciones no solo resuelvan el problema propuesto, sino que lo hagan bajo los estándares más altos de eficiencia y legibilidad.