Data Structure & Algorithms
Cómo reconocer patrones algorítmicos a partir de restricciones y propiedades: two pointers, ventanas, heaps, DP, backtracking, greedy y grafos.
Un patrón de resolución no es una plantilla que se copia. Es una relación recurrente entre las restricciones del problema, las operaciones necesarias y una propiedad que permite evitar trabajo.
La pregunta útil no es “¿qué patrón toca?”, sino “¿qué información puedo mantener mientras avanzo para no recomputar o retroceder innecesariamente?”.
Observa señales, pero confirma la propiedad.
| Señal | Patrón candidato | Propiedad que debes confirmar |
|---|---|---|
| Array ordenado, pareja o partición | Two pointers | Mover un puntero descarta opciones de forma segura |
| Subarray o substring contiguo | Sliding window | El estado se actualiza al entrar y salir elementos |
| Prefijos o rangos repetidos | Prefix sum | La operación de rango puede derivarse de acumulados |
| Secuencia con siguiente mayor o menor | Monotonic stack | Los elementos dominados nunca volverán a ser útiles |
| K mejores o prioridad dinámica | Heap | Solo necesitas acceder repetidamente al extremo prioritario |
| Respuesta monotónica | Binary search on answer | Si una respuesta es factible, un lado completo también lo es |
| Conectividad dinámica | Union-Find | Importa unir y consultar componentes, no los caminos |
| Elecciones reversibles | Backtracking | El espacio de soluciones forma un árbol de decisiones |
| Subproblemas repetidos | Dynamic programming | Existe un estado suficiente y transiciones reutilizables |
Puede usar extremos opuestos o punteros que avanzan a distinta velocidad.
Usa extremos cuando el orden permite decidir qué lado mover. Usa fast and slow pointers cuando necesitas detectar ciclos, compactar datos o separar lectura de escritura.
function removeDuplicates(sorted: number[]): number {
if (sorted.length === 0) return 0;
let write = 1;
for (let read = 1; read < sorted.length; read += 1) {
if (sorted[read] !== sorted[write - 1]) {
sorted[write] = sorted[read];
write += 1;
}
}
return write;
}Invariante: sorted[0..write-1] contiene los valores únicos vistos hasta read.
Sirve para segmentos contiguos cuando puedes actualizar el estado incrementalmente.
No funciona automáticamente si quitar un elemento no permite restaurar el estado de forma eficiente o si la condición no es monotónica respecto al tamaño de la ventana.
En una linked list, un puntero avanza un paso y otro dos. Si hay ciclo, terminan coincidiendo. El patrón no depende de “magia”; depende de que, dentro del ciclo, la distancia relativa cambia en una unidad por iteración.
También aparece al compactar arrays: read explora y write marca dónde colocar el siguiente valor válido.
Ordena intervalos por inicio y mantiene el último intervalo consolidado. Si el siguiente comienza antes de que el actual termine, se fusionan.
La ordenación crea la propiedad necesaria: después de procesar un prefijo, ningún intervalo futuro puede comenzar antes que uno ya omitido.
No se limita a buscar un valor. Puede encontrar la primera posición válida, la última inválida o el mínimo valor factible.
Requisito: el espacio de búsqueda debe dividirse en regiones monotónicas, por ejemplo:
false false false true true true
↑ primera respuesta válidaMantén un min-heap de tamaño k para conservar los k elementos más grandes vistos. El menor de esos candidatos está en la raíz y puede descartarse cuando aparece uno mejor.
Tiempo: O(n log k). Memoria adicional: O(k).
La estructura del resultado, no la palabra “árbol”, decide el recorrido.
Añade un conjunto visited cuando un nodo puede alcanzarse por varios caminos. Decide cuándo marcar:
Elige, explora y deshace. Úsalo cuando debes enumerar soluciones y las decisiones futuras dependen del prefijo construido.
El pruning debe apoyarse en una imposibilidad demostrable, no en una intuición.
Busca una pregunta repetida: “¿cuál es la mejor respuesta desde este estado?”. Si dos caminos llegan al mismo estado y el futuro ya no depende de cómo llegaron, puedes reutilizar el resultado.
Excelente para preguntas de conectividad después de uniones. No sirve para recuperar el camino entre dos nodos ni para eliminar aristas de forma sencilla.
Mantiene candidatos en orden creciente o decreciente. Cuando llega un elemento que domina a los del tope, esos elementos se resuelven y salen definitivamente.
function nextGreater(values: number[]): number[] {
const result = Array(values.length).fill(-1);
const stack: number[] = [];
for (let i = 0; i < values.length; i += 1) {
while (stack.length > 0 && values[i] > values[stack.at(-1)!]) {
result[stack.pop()!] = values[i];
}
stack.push(i);
}
return result;
}Cada índice entra y sale una vez: tiempo O(n), aunque exista un while anidado.
Transforma consultas repetidas de rango en restas de acumulados. El costo inicial O(n) se amortiza cuando hay muchas consultas.
Un patrón es válido por una propiedad del problema. Si no puedes explicar qué opciones descarta o qué trabajo reutiliza, todavía no has justificado su uso.
Un problema pide el segmento contiguo más corto cuya suma sea al menos k. ¿Sliding window funciona siempre?
No. Con números no negativos, al expandir la suma no disminuye y al contraer no aumenta, lo que produce una condición monotónica útil. Con números negativos, quitar o agregar un valor puede cambiar la suma en cualquier dirección; se necesita otra técnica, como prefix sums con una deque monotónica en ciertas variantes.