Semanas 4 y 5 Two Pointers Sliding Window y Stack

Semanas 4 y 5: Two Pointers, Sliding Window y Stack

Objetivo

Reconocer problemas donde conviene mover límites, mantener ventanas válidas o usar una pila para conservar candidatos pendientes.

Problemas Completados

Problema	Patrón	Función	Tests
Valid Palindrome	Two pointers	valid_palindrome	3
Two Sum II	Two pointers en arreglo ordenado	two_sum_sorted	2
3Sum	Ordenamiento + two pointers	three_sum	3
Container With Most Water	Two pointers	max_area	3
Remove Duplicates from Sorted Array	Writer pointer	remove_duplicates_sorted	2
Move Zeroes	Writer pointer estable	move_zeroes	2
Squares of a Sorted Array	Extremos por valor absoluto	sorted_squares	2
Best Time to Buy and Sell Stock	Ventana de decisión	max_profit	3
Longest Substring Without Repeating Characters	Sliding window variable	length_of_longest_substring	3
Minimum Window Substring	Sliding window con conteos	min_window	3
Valid Parentheses	Stack	valid_parentheses	3
Daily Temperatures	Stack monotónico decreciente	daily_temperatures	3
Largest Rectangle in Histogram	Stack monotónico creciente	largest_rectangle_area	3

Ideas Clave

Two Pointers

Útil cuando se puede recorrer desde ambos extremos o cuando ordenar permite mover límites con intención.

Invariantes:

• En valid_palindrome, los punteros ignoran caracteres no alfanuméricos.
• En two_sum_sorted, mover el puntero izquierdo aumenta la suma y mover el derecho la reduce.
• En three_sum, el índice fijo no se repite y los punteros saltan duplicados.
• En max_area, se mueve el lado de menor altura porque limita el área actual.
• En writer pointer, write marca la próxima posición compacta sin romper el orden relativo.
• En cuadrados ordenados, el mayor valor absoluto vive en uno de los extremos.

Sliding Window

Útil cuando buscamos la mejor subcadena o subarreglo contiguo bajo una condición.

Tipos:

• Ventana de decisión: mantener el mejor punto de compra.
• Ventana variable sin repetidos: mover left después del último carácter repetido.
• Ventana mínima con conteos: expandir hasta cubrir y contraer mientras siga siendo válida.

Stack

Útil cuando el problema depende del último elemento pendiente.

Casos:

• valid_parentheses: la pila guarda cierres esperados.
• daily_temperatures: la pila guarda índices sin día más cálido.
• largest_rectangle_area: la pila guarda barras en orden creciente.

Errores Comunes

• No saltar duplicados en three_sum.
• Mover el puntero incorrecto en max_area.
• Perder estabilidad al mover ceros o compactar duplicados.
• Llenar cuadrados de izquierda a derecha y romper el orden final.
• Confundir ventana fija con ventana variable.
• No actualizar left con max al ver un carácter repetido.
• Olvidar el centinela final 0 en histograma.
• Usar stack normal cuando el problema necesita stack monotónico.

Verificación

cargo test

Resultado al cerrar el bloque:

334 passed; 0 failed

Siguiente Bloque

El siguiente bloque recomendado es:

• Búsqueda binaria.
• Lower bound / upper bound.
• Búsqueda binaria sobre respuesta.

Primeros problemas sugeridos:

• Binary Search.
• Search Insert Position.
• Search in Rotated Sorted Array.
• Find Minimum in Rotated Sorted Array.
• Koko Eating Bananas.