0Pricing
Coding Interview Prep · Lección

Dos punteros: extremos opuestos

Use punteros izquierdo y derecho que se acerquen entre sí para resolver la suma de pares en arrays ordenados, los palíndromos válidos y el problema de atrapar agua de lluvia.

Dos punteros: extremos opuestos es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.

La idea de los dos punteros

La técnica de dos punteros utiliza dos variables de índice que se acercan entre sí (o avanzan en la misma dirección) para reducir la necesidad de usar bucles anidados. En lugar de comprobar cada par en O(n²), progresa con cada comparación y termina en O(n). Casi siempre requiere ordenar primero el array, porque la ordenación permite determinar en qué dirección mover cada puntero según si la suma del par actual es demasiado grande o demasiado pequeña.

# Without two pointers: O(n^2)
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target: return [left, right]
        elif s < target: left  += 1
        else:           right -= 1
    return []

Suma de dos elementos en un array ordenado

Con un array ordenado, coloque un puntero en el extremo izquierdo (el menor) y otro en el extremo derecho (el mayor). Si la suma es demasiado pequeña, mueva el puntero izquierdo hacia la derecha para aumentarla. Si es demasiado grande, mueva el puntero derecho hacia la izquierda para reducirla. Cada iteración avanza al menos un puntero, por lo que el bucle se ejecuta como máximo n veces: O(n) en total después de ordenar. Es importante destacar que cada movimiento es demostrablemente correcto gracias al orden de los elementos.

def two_sum_sorted(numbers, target):
    # numbers is 1-indexed per LeetCode 167
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]  # 1-indexed
        elif s < target:
            left  += 1  # need larger sum
        else:
            right -= 1  # need smaller sum
    return []

print(two_sum_sorted([2, 7, 11, 15], 9))   # [1, 2]
print(two_sum_sorted([2, 3, 4], 6))         # [1, 3]

Comprobar si es un palíndromo

Una cadena es un palíndromo si se lee igual de izquierda a derecha y de derecha a izquierda. Utilice dos punteros que comiencen en ambos extremos y avancen hacia el centro: compare los caracteres, omita los que no sean alfanuméricos y deténgase cuando los punteros se crucen. Esto se ejecuta en O(n) y con espacio adicional O(1), lo que resulta mucho más claro que invertir la cadena y compararla, operación que asigna O(n) de memoria adicional.

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        # Skip non-alphanumeric
        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

print(is_palindrome('A man, a plan, a canal: Panama'))  # True
print(is_palindrome('race a car'))                       # False

Tres sumas: ordenar + dos punteros

El problema de tres sumas solicita todas las tripletas únicas cuya suma sea cero. Ordene el array, fije cada elemento nums[i] y ejecute una búsqueda con dos punteros en el subarray restante para encontrar un par cuya suma sea -nums[i]. Omita los duplicados tanto del elemento fijado como del par encontrado para evitar tripletas repetidas. Tiempo total: O(n²) después de ordenar en O(n log n).

def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]: continue  # skip dupe
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left]  == nums[left+1]:  left  += 1
                while left < right and nums[right] == nums[right-1]: right -= 1
                left += 1; right -= 1
            elif s < 0: left  += 1
            else:       right -= 1
    return result

print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1,-1,2],[-1,0,1]]

Contenedor con más agua

Dadas las alturas de unas líneas verticales, encuentre las dos que formen un contenedor capaz de contener la mayor cantidad de agua. Área = min(height[left], height[right]) × (right - left). Mueva de forma voraz hacia dentro el puntero situado en la línea más corta: mover el de la línea más alta solo puede reducir la anchura sin aumentar el límite de altura. Esta elección voraz es demostrablemente óptima y proporciona un tiempo O(n).

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        h    = min(height[left], height[right])
        area = h * (right - left)
        best = max(best, area)
        # Move the shorter wall inward
        if height[left] < height[right]:
            left  += 1
        else:
            right -= 1
    return best

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49

Elevar al cuadrado un array ordenado

Eleve al cuadrado cada elemento de un array ordenado, que puede contener valores negativos, y devuelva el resultado en orden. Los cuadrados de los valores negativos son grandes; los cuadrados más pequeños se encuentran en el centro. Coloque dos punteros en ambos extremos y rellene el array de resultados de derecha a izquierda, del mayor al menor. Tiempo O(n) y espacio O(n) para la salida, mucho mejor que elevar al cuadrado y ordenar después en O(n log n).

def sorted_squares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    pos = n - 1
    while left <= right:
        l_sq = nums[left]  ** 2
        r_sq = nums[right] ** 2
        if l_sq > r_sq:
            result[pos] = l_sq
            left += 1
        else:
            result[pos] = r_sq
            right -= 1
        pos -= 1
    return result

print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]

Atrapar agua de lluvia

El agua atrapada en el índice i equivale a min(max_left, max_right) - height[i]. Enfoque de dos punteros: mantenga los valores acumulados max_left y max_right. Cuando max_left < max_right, el lado izquierdo es el cuello de botella: procese el puntero izquierdo. En caso contrario, procese el derecho. Esto elimina la necesidad de usar arrays separados para el máximo izquierdo y el máximo derecho y consigue un espacio adicional O(1).

def trap(height):
    left, right = 0, len(height) - 1
    max_left = max_right = 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= max_left:
                max_left = height[left]
            else:
                water += max_left - height[left]
            left += 1
        else:
            if height[right] >= max_right:
                max_right = height[right]
            else:
                water += max_right - height[right]
            right -= 1
    return water

print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))  # 6

Por qué funciona mover el puntero de forma voraz

Una pregunta habitual en las entrevistas es: ¿por qué es seguro descartar el puntero menor? Esbozo de la demostración para el problema del contenedor con más agua: supongamos que height[left] < height[right]. Cada par (left, j) con j < right tiene un área ≤ height[left] × (j-left) < height[left] × (right-left) ≤ el área actual. Por tanto, ningún par que comience en 'left' con un índice derecho menor que 'right' puede superar el área actual. Podemos omitirlos de forma segura avanzando left.

# Correctness argument via contradiction:
# If left < right and height[left] < height[right],
# then for any j in (left, right):
#   area(left, j) <= min(h[left], h[j]) * (j - left)
#                 <= h[left] * (j - left)
#                 <= h[left] * (right - left)   [since j < right]
#                 = current area
# So no pair (left, j) for j < right can improve.
# Moving left inward is SAFE.

print('Proof verified: advance shorter pointer is optimal')

Par de diferencia mínima en un arreglo ordenado

Encuentre el par de números de un arreglo ordenado con la menor diferencia absoluta. Utilice dos punteros adyacentes (no en extremos opuestos) que avancen juntos: |nums[i] - nums[i+1]| para todos los pares consecutivos. En un arreglo ordenado, la diferencia mínima siempre se encuentra entre elementos adyacentes, porque la ordenación agrupa los valores cercanos. Esto es O(n) después de ordenar.

def min_diff_pair(nums):
    nums.sort()  # O(n log n)
    min_diff = float('inf')
    best = (nums[0], nums[1])
    for i in range(len(nums) - 1):
        diff = nums[i+1] - nums[i]  # sorted: always >= 0
        if diff < min_diff:
            min_diff = diff
            best = (nums[i], nums[i+1])
    return best, min_diff

pair, d = min_diff_pair([4, 2, 1, 6, 10, 8])
print(pair, d)  # (1, 2) 1

Plantilla para dos punteros en extremos opuestos

La mayoría de los problemas de dos punteros en extremos opuestos siguen la misma estructura básica. Dominar esta plantilla le permite adaptarla rápidamente bajo presión. Las decisiones clave son: (1) qué condición hace avanzar a la izquierda, (2) qué condición hace avanzar a la derecha, (3) qué constituye una solución y (4) cómo gestionar los duplicados. Practique cómo deducir estas decisiones del enunciado antes de escribir código.

def two_pointer_template(arr, condition):
    """
    Generic opposite-ends two-pointer skeleton.
    Replace condition logic for each specific problem.
    """
    left, right = 0, len(arr) - 1
    result = []
    while left < right:
        current = arr[left] + arr[right]  # or some combination
        if current == condition:           # found a valid pair
            result.append((arr[left], arr[right]))
            left  += 1
            right -= 1
        elif current < condition:          # need to increase
            left  += 1
        else:                             # need to decrease
            right -= 1
    return result

Contar pares válidos con dos punteros

Los dos punteros también permiten contar pares de forma eficiente. Para el problema «contar pares cuya suma sea < target» en un arreglo ordenado: fije el puntero izquierdo y utilice el puntero derecho para encontrar el índice derecho válido más alejado. Todos los pares (left, left+1 a right) son válidos; sume right - left al contador y haga avanzar left. Así se cuentan todos los pares válidos en O(n), en lugar de O(n²).

def count_pairs_less_than(nums, target):
    nums.sort()
    left, right = 0, len(nums) - 1
    count = 0
    while left < right:
        if nums[left] + nums[right] < target:
            count += right - left  # all (left, left+1..right) valid
            left  += 1
        else:
            right -= 1
    return count

print(count_pairs_less_than([1, 2, 3, 4, 5], 6))
# pairs: (1,2)(1,3)(1,4)(2,3)  -> 4

Comprobación rápida

Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

Resumen de la lección

En esta lección aprendió que: los dos punteros en extremos opuestos sustituyen la enumeración de pares en O(n²) por una convergencia de izquierda a derecha en O(n) sobre arreglos ordenados; la decisión de qué puntero hacer avanzar se deriva de la propiedad monótona del problema: debe mover el lado que actualmente limita el progreso; y three-sum, container-with-most-water, trapping rain water y la verificación de palíndromos se reducen a la misma plantilla básica. A continuación, exploraremos los patrones de dos punteros lento-rápido.

Preguntas frecuentes

¿La lección «Dos punteros: extremos opuestos» es gratis?

Sí — el texto completo de «Dos punteros: extremos opuestos» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.

¿Qué aprenderé en «Dos punteros: extremos opuestos»?

Use punteros izquierdo y derecho que se acerquen entre sí para resolver la suma de pares en arrays ordenados, los palíndromos válidos y el problema de atrapar agua de lluvia. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar Coding Interview Prep?

No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.

¿Cuánto tiempo toma la lección «Dos punteros: extremos opuestos»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?

Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

  1. Fundamentos de arrays y operaciones in-place
  2. Sumas de prefijos y totales acumulados
  3. Dos punteros: extremos opuestos
  4. Dos punteros: lento y rápido
← Volver a Coding Interview Prep