Sesión 05: Cracking the Coding Interview (Capítulo 1, Parte 3) — Técnica de Dos Punteros (Two Pointers Pattern)#

Navegación rápida:

• ← Sesión 04: Hash Maps y Frecuencia
• Sesión 06: Strings Avanzados y Compresión →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 50-65 minutos.
• Código fuente compilado y probado: practica-rust/dia_05.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

El patrón de dos punteros es una de las técnicas de optimización más elegantes de la ingeniería de software: sustituye bucles anidados O(N²) por un único recorrido lineal O(N) en memoria contigua sin asignar memoria auxiliar (O(1) espacio). Consulta el Glosario Maestro.

Punteros Convergentes (Opposite Direction Pointers)#

• (a) En palabras simples (intuición): Dos personas paradas en los extremos opuestos de un puente angosto que caminan hacia el centro. Se detienen en el momento exacto en que se cruzan o se dan la mano.
• (b) Definición técnica paso a paso: Técnica donde dos variables de índice (left y right) se inicializan en los extremos opuestos de un arreglo ($0$ y N-1) y avanzan en direcciones contrarias (left += 1, right -= 1) bajo una condición de parada estricta while left < right.
• (c) Cómo funciona en Rust (memoria y tipos): En Rust, como los índices son usize, decrementar right requiere cautela para evitar pánicos por underflow si right llega a 0. Se utiliza idiomáticamente right = right.saturating_sub(1).
• (d) Error típico de Junior: Usar bucles anidados para buscar parejas en listas ordenadas en lugar de aprovechar la monotonicidad con punteros convergentes.

Punteros de Lectura y Escritura (Fast & Slow / Read & Write Pointers)#

• (a) En palabras simples (intuición): Un inspector de calidad (read_idx) que camina rápido revisando cada pieza de una cinta transportadora, y un obrero (write_idx) que solo coloca en la caja las piezas aprobadas que no estén repetidas.
• (b) Definición técnica paso a paso: Técnica in-place donde ambos punteros se mueven en la misma dirección (de izquierda a derecha), pero a ritmos diferentes. read_idx itera sobre todos los elementos de entrada, mientras write_idx mantiene la frontera del subarreglo filtrado y válido.
• (c) Cómo funciona en Rust (memoria y tipos): Opera sobre un slice mutable &mut [T]. El borrow checker garantiza que somos el único hilo modificando la memoria en ese instante, permitiendo sobreescribir slots de memoria en tiempo O(1) sin realocar el vector.
• (d) Error típico de Junior: Usar vec.remove(i) dentro de un bucle para borrar duplicados, lo cual desplaza todos los elementos hacia la izquierda en cada borrado (O(N) por borrado) resultando en una degradación catastrófica a O(N²).

Resta Saturada (saturating_sub)#

• (a) En palabras simples (intuición): Un velocímetro que al frenar nunca baja de 0 km/h; si intentas restar velocidad a 0, se queda clavado en 0 en lugar de romperse.
• (b) Definición técnica paso a paso: Operación aritmética de Rust provista para tipos enteros sin signo (usize, u32, etc.). Si el resultado de la resta a - b es negativo, en vez de producir un pánico por subdesbordamiento, retorna el valor mínimo del tipo ($0$).
• (c) Cómo funciona en Rust (memoria y tipos): Se compila directamente a una instrucción de hardware de saturación condicional o sustracción con branchless conditional move (sub + cmov), sin sobrecosto de ejecución.
• (d) Error típico de Junior: Escribir right -= 1; en un bucle donde una condición interna previa pudo haber dejado a right en $0$, provocando un cierre inesperado del programa en producción.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Matemática de Two Sum sobre Arreglos Ordenados (Monotonicidad)#

Imagina que tenemos un arreglo ordenado en orden ascendente:

Colocamos:

• left = 0 (el menor elemento de todo el arreglo).
• right = N - 1 (el mayor elemento de todo el arreglo).

Calculamos la suma actual: S = nums[left] + nums[right]. Surgen exactamente tres posibilidades exhaustivas y mutuamente excluyentes:

1. S == target: - Hemos encontrado el par solución de forma exacta.
2. S < target: - La suma actual es demasiado pequeña. - Como el arreglo está ordenado, combinar left con cualquier otro elemento a la izquierda de right (es decir, con números más pequeños que nums[right]) daría una suma todavía menor. - Por lo tanto, el elemento nums[left] es matemáticamente incapaz de formar una pareja válida con ningún elemento restante. - Acción no negociable: Descartamos nums[left] y avanzamos left += 1 para buscar un número mayor.
3. S > target: - La suma actual es demasiado grande. - Combinar right con cualquier otro número a la derecha de left daría una suma aún más grande. - Por lo tanto, nums[right] es incapaz de formar una suma válida con ningún elemento restante. - Acción no negociable: Descartamos nums[right] y retrocedemos right -= 1 para buscar un número menor.

En cada paso individual, descartamos definitivamente un elemento del arreglo. Como hay N elementos, el algoritmo termina con garantía matemática en a lo sumo N pasos: Complejidad Temporal O(N) y Espacial O(1).

3. Visualización Paso a Paso y Gráfica de Memoria en Rust#

Flujo de Decisión de Two Sum Ordenado#

Consulta la arquitectura visual en los diagramas del sistema:

• Gráfico SVG: ![Visualización del Día 05 y Memoria en Rust](../diagrams/sesiones/dia_05.svg)
• Enlace al código fuente Mermaid: Fuente Mermaid

flowchart TD
    A["left = 0, right = arr.len() - 1"] --> B{"left < right"}
    B -->|No| NF["Retornar None (No existe pareja)"]
    B -->|Sí| C["sum = arr[left] + arr[right]"]
    C --> D{"sum vs target"}
    D -->|sum == target| FOUND["Retornar Some((left, right))"]
    D -->|sum > target| DEC["right -= 1 (reducir suma)"]
    D -->|sum < target| INC["left += 1 (aumentar suma)"]
    DEC --> B
    INC --> B

Visualización Cuadro por Cuadro de Memoria: Eliminación de Duplicados In-Place#

Entrada: let mut nums = [1, 1, 2, 2, 3];

ESTADO INICIAL:
write_idx = 1 (el elemento en índice 0 siempre es único)
Índices:       0    1    2    3    4
Valores:     [ 1,   1,   2,   2,   3 ]
               ^    ^
        write-1    read

PASO 1 (read_idx = 1):
- nums[1] (1) == nums[write_idx - 1] (1). ¡Duplicado detectado!
- No se escribe nada. write_idx se mantiene en 1.

PASO 2 (read_idx = 2):
- nums[2] (2) != nums[write_idx - 1] (1). ¡Nuevo valor único encontrado!
- nums[write_idx] = nums[2] -> nums[1] = 2.
- write_idx incrementa a 2.
Arreglo en Stack: [ 1,  2,  2,  2,  3 ]
                        ^
                    write_idx

PASO 3 (read_idx = 3):
- nums[3] (2) == nums[write_idx - 1] (2). ¡Duplicado detectado!
- write_idx se mantiene en 2.

PASO 4 (read_idx = 4):
- nums[4] (3) != nums[write_idx - 1] (2). ¡Nuevo valor único encontrado!
- nums[write_idx] = nums[4] -> nums[2] = 3.
- write_idx incrementa a 3.
Arreglo final en Stack: [ 1,  2,  3,  2,  3 ]
Subarreglo único válido: &nums[..3] == [1, 2, 3]. Retorna longitud k = 3.

4. Implementación Canónica en Rust + Comparativa con Python#

Implementación en Rust (practica-rust/dia_05.rs)#

//! Implementación canónica de algoritmos con Dos Punteros en Rust.
//! Compilable y verificable con `rustc --test`.

/// LeetCode 125: Palíndromo válido con dos punteros convergentes ignorando no-alfanuméricos.
pub fn is_valid_palindrome(s: &str) -> bool {
    let bytes = s.as_bytes();
    if bytes.is_empty() {
        return true;
    }

    let mut left = 0;
    let mut right = bytes.len() - 1;

    while left < right {
        while left < right && !bytes[left].is_ascii_alphanumeric() {
            left += 1;
        }
        while left < right && !bytes[right].is_ascii_alphanumeric() {
            right = right.saturating_sub(1);
        }

        if left < right {
            let cl = bytes[left].to_ascii_lowercase();
            let cr = bytes[right].to_ascii_lowercase();

            if cl != cr {
                return false;
            }

            left += 1;
            right = right.saturating_sub(1);
        }
    }

    true
}

/// LeetCode 26: Eliminación de duplicados in-place con punteros de lectura y escritura.
pub fn remove_duplicates_sorted(nums: &mut [i32]) -> usize {
    if nums.is_empty() {
        return 0;
    }

    let mut write_idx = 1;

    for read_idx in 1..nums.len() {
        if nums[read_idx] != nums[write_idx - 1] {
            nums[write_idx] = nums[read_idx];
            write_idx += 1;
        }
    }

    write_idx
}

/// LeetCode 167: Two Sum II sobre arreglo ordenado en O(N) tiempo y O(1) espacio.
pub fn two_sum_sorted(numbers: &[i32], target: i32) -> Option<(usize, usize)> {
    if numbers.len() < 2 {
        return None;
    }

    let mut left = 0;
    let mut right = numbers.len() - 1;

    while left < right {
        let sum = numbers[left] + numbers[right];

        if sum == target {
            return Some((left, right));
        } else if sum < target {
            left += 1;
        } else {
            right = right.saturating_sub(1);
        }
    }

    None
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_is_valid_palindrome() {
        assert!(is_valid_palindrome("A man, a plan, a canal: Panama"));
        assert!(!is_valid_palindrome("race a car"));
        assert!(is_valid_palindrome(" "));
        assert!(!is_valid_palindrome("0P"));
    }

    #[test]
    fn test_remove_duplicates_sorted() {
        let mut nums = [1, 1, 2];
        let k = remove_duplicates_sorted(&mut nums);
        assert_eq!(k, 2);
        assert_eq!(&nums[..k], &[1, 2]);
    }

    #[test]
    fn test_two_sum_sorted() {
        let numbers = [2, 7, 11, 15];
        assert_eq!(two_sum_sorted(&numbers, 9), Some((0, 1)));
    }
}

Implementación Canónica en Python (practica/dia_05_two_pointers.py)#

from typing import List, Optional, Tuple

def is_valid_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

def remove_duplicates_sorted(nums: List[int]) -> int:
    if not nums:
        return 0
    write_idx = 1
    for read_idx in range(1, len(nums)):
        if nums[read_idx] != nums[write_idx - 1]:
            nums[write_idx] = nums[read_idx]
            write_idx += 1
    return write_idx

5. Las 3 Trampas Clásicas en Entrevistas#

1. Olvidar la Condición left < right en Bucles Internos: - Al filtrar caracteres no alfanuméricos con while !bytes[left].is_ascii_alphanumeric(), es imperativo incluir while left < right && .... De lo contrario, para una cadena compuesta solo de espacios o signos (" "), left avanzará más allá del final del slice, provocando un pánico por violación de límites.
2. Subdesbordamiento de usize al Decrementar right: - En Python, right -= 1 cuando right == 0 produce -1. En Rust, 0usize - 1 aborta el programa en debug. Siempre usa .saturating_sub(1).
3. No Reconocer la Condición de Entrada Ordenada: - Dos Punteros Convergentes solo funciona si los datos son monótonos (ordenados). Si te entregan un arreglo desordenado para Two Sum y no puedes alterar el orden de los índices de salida, debes usar la solución de Hash Map de la Sesión 04.

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Puente a LeetCode y Práctica de Código#

1. LeetCode 125 — Valid Palindrome (Easy): - Resuelve con dos punteros convergentes sobre &[u8].
2. LeetCode 26 — Remove Duplicates from Sorted Array (Easy): - Compactación in-place con write_idx y read_idx.
3. LeetCode 167 — Two Sum II - Input Array Is Sorted (Medium): - Monotonicidad con dos punteros convergentes.
4. LeetCode 15 — 3Sum (Medium): - Bucle exterior más dos punteros convergentes.

Navegación:

• ← Volver a Sesión 04: Hash Maps y Frecuencia
• Avanzar a Sesión 06: Strings Avanzados y Compresión →