Data Structure & Algorithms
Two pointers y sliding window
Patrones two pointers y sliding window para secuencias, ventanas fijas o variables, compactación y problemas con estado incremental.
- Última actualización
- Actualizada
- Nivel
- Aplicación
Data Structure & Algorithms
Patrones two pointers y sliding window para secuencias, ventanas fijas o variables, compactación y problemas con estado incremental.
Two pointers y sliding window reducen trabajo repetido al mantener posiciones y estado incremental sobre una secuencia.
No funcionan por la forma del código. Necesitan una propiedad que haga seguros los movimientos.
En un array ordenado, busca una pareja con suma objetivo.
function findPairWithSum(
values: readonly number[],
target: number,
): [number, number] | null {
let left = 0;
let right = values.length - 1;
while (left < right) {
const sum = values[left] + values[right];
if (sum === target) return [left, right];
if (sum < target) {
left += 1;
} else {
right -= 1;
}
}
return null;
}Si sum < target, mantener values[left] y mover right hacia la izquierda solo produciría una suma menor o igual. Ninguna pareja con ese left puede servir. Por eso es seguro incrementarlo.
El orden del array es la propiedad que justifica el movimiento.
O(n);O(1).Sin orden, esta regla no es válida. Podrías ordenar primero en O(n log n), pero perderías índices originales salvo que guardes pares, o usar hashing en O(n) promedio con O(n) memoria.
Un puntero lee; otro marca dónde escribir el siguiente elemento válido.
function deduplicateSorted(values: number[]): number {
if (values.length === 0) return 0;
let write = 1;
for (let read = 1; read < values.length; read += 1) {
if (values[read] !== values[write - 1]) {
values[write] = values[read];
write += 1;
}
}
return write;
}Invariante: values[0..write) contiene exactamente los valores únicos vistos, en orden.
El array está ordenado, por lo que basta comparar con el último valor único. En datos sin ordenar necesitarías un Set.
Fast and slow pointers aparecen en linked lists y arrays:
La clave es una relación matemática entre velocidades, no el nombre de las variables.
Una ventana representa un segmento contiguo:
values = [2, 1, 5, 1, 3, 2]
[5, 1, 3]
left rightEn lugar de recalcular el segmento completo al moverlo, actualiza el estado:
entra un elemento → agregar su efecto
sale un elemento → retirar su efectoMáxima suma de k elementos contiguos.
function maxFixedWindowSum(
values: readonly number[],
windowSize: number,
): number | null {
if (windowSize <= 0 || windowSize > values.length) return null;
let windowSum = 0;
for (let index = 0; index < windowSize; index += 1) {
windowSum += values[index];
}
let best = windowSum;
for (let right = windowSize; right < values.length; right += 1) {
windowSum += values[right];
windowSum -= values[right - windowSize];
best = Math.max(best, windowSum);
}
return best;
}O(k);n - k veces con trabajo constante;O(n);O(1).Recalcular cada suma costaría O(nk).
Busca el segmento mínimo con suma al menos target, suponiendo valores positivos.
function minimumLengthAtLeast(
values: readonly number[],
target: number,
): number {
let left = 0;
let sum = 0;
let best = Infinity;
for (let right = 0; right < values.length; right += 1) {
sum += values[right];
while (sum >= target) {
best = Math.min(best, right - left + 1);
sum -= values[left];
left += 1;
}
}
return best === Infinity ? 0 : best;
}Con positivos:
Cuando la suma ya alcanza el objetivo, mover left intenta reducir longitud. Cuando deja de alcanzarlo, seguir contrayendo no puede volverla válida.
Con negativos, esa monotonicidad desaparece. Una ventana puede mejorar al agregar un negativo o empeorar al quitarlo de formas no previsibles. La técnica anterior deja de ser correcta.
Aunque hay un while dentro de un for, cada índice:
right;left.Tiempo total O(n), memoria O(1).
Este es un análisis amortizado por movimientos de punteros.
La ventana mantiene la última posición de cada carácter.
function longestUniqueSubstring(text: string): number {
const characters = [...text];
const lastIndex = new Map<string, number>();
let left = 0;
let best = 0;
for (let right = 0; right < characters.length; right += 1) {
const character = characters[right];
const previous = lastIndex.get(character);
if (previous !== undefined && previous >= left) {
left = previous + 1;
}
lastIndex.set(character, right);
best = Math.max(best, right - left + 1);
}
return best;
}Invariante: la ventana characters[left..right] no contiene caracteres repetidos.
Mover left directamente después de la aparición previa evita retirar uno por uno.
[...text] trabaja por code points, no por grapheme clusters. Un emoji compuesto puede ocupar varios elementos visibles. El dominio de “carácter” debe definirse.
Para problemas como “máximo segmento con a lo sumo k valores distintos”:
map.size representa distintos activos.function longestAtMostKDistinct<T>(
values: readonly T[],
k: number,
): number {
if (k < 0) return 0;
const counts = new Map<T, number>();
let left = 0;
let best = 0;
for (let right = 0; right < values.length; right += 1) {
const incoming = values[right];
counts.set(incoming, (counts.get(incoming) ?? 0) + 1);
while (counts.size > k) {
const outgoing = values[left];
const count = counts.get(outgoing)! - 1;
if (count === 0) counts.delete(outgoing);
else counts.set(outgoing, count);
left += 1;
}
best = Math.max(best, right - left + 1);
}
return best;
}Tiempo promedio O(n), memoria O(k) activa, aunque el número de claves temporales puede variar durante contracción.
Algunos conteos se simplifican:
subarrays con exactamente k distintos
= atMost(k) - atMost(k - 1)Esto funciona porque cada subarray tiene una cantidad definida de distintos y las colecciones están anidadas.
No todas las propiedades “exactamente” pueden descomponerse así; debes comprobar la relación.
Two pointers también combina arrays ordenados.
function mergeSorted(
left: readonly number[],
right: readonly number[],
): number[] {
const result: number[] = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) result.push(left[i++]);
else result.push(right[j++]);
}
while (i < left.length) result.push(left[i++]);
while (j < right.length) result.push(right[j++]);
return result;
}Tiempo O(n + m), porque cada puntero avanza hasta el final una vez.
Después de ordenar intervalos por inicio, un puntero recorre y otro representa el último intervalo consolidado. El orden garantiza que solo necesitas comparar con el último resultado.
Two pointers no siempre se ven como left/right; pueden ser “entrada” y “salida”, “lista A” y “lista B” o “último consolidado” y “actual”.
A veces prefix sums, monotonic deque, hashing o DP son alternativas.
n;k = 0;left hacia atrás usando una aparición previa fuera de la ventana.O(n²) sin contar movimientos totales.¿Por qué la ventana variable para suma mínima deja de ser correcta con números negativos?
Porque expandir puede reducir la suma y contraer puede aumentarla. Ya no existe una dirección segura para mover los límites, así que el algoritmo puede descartar una ventana que después habría producido una mejor solución.