Los problemas de concurso premian reconocer una forma rápido. Dos punteros es la primera forma que vale la pena aprender, porque no cuesta nada: sin segundo arreglo, sin diccionario, sin recursión. Dos variables int y el arreglo que te dieron.
Esta es la parte 1 de diez, con cinco patrones cada una. Todos los programas de abajo están completos, se ejecutaron en .NET 10, y su salida está pegada de la ejecución.
Cómo ejecutar esto
.NET 10 ejecuta un solo archivo .cs sin proyecto, sin clase y sin Main:
dotnet run twopointers.csEso es nuevo, y es la forma más rápida de probar todo esto. Todo lo de esta página está escrito así.
Patrón 1 — Cerrando desde ambos extremos
Tienes un arreglo ordenado. Encuentra dos valores que sumen un objetivo.
La versión obvia prueba todos los pares. En un arreglo de seis elementos eso está bien. Cuenta lo que hace en realidad:
int[] a = [2, 7, 11, 15, 19, 26];
int target = 30;
int bruteSteps = 0;
for (int i = 0; i < a.Length; i++)
for (int j = i + 1; j < a.Length; j++)
{
bruteSteps++;
if (a[i] + a[j] == target) goto done;
}
done:
int twoPtrSteps = 0;
int lo = 0, hi = a.Length - 1;
while (lo < hi)
{
twoPtrSteps++;
int sum = a[lo] + a[hi];
if (sum == target) break;
if (sum < target) lo++; else hi--;
}
Console.WriteLine($"n = {a.Length}");
Console.WriteLine($"every pair : {bruteSteps} pairs examined");
Console.WriteLine($"two pointers : {twoPtrSteps} steps");Imprime:
n = 6
every pair : 11 pairs examined
two pointers : 4 stepsOnce pares contra cuatro pasos no es una diferencia interesante. Con n = 100000 son cinco mil millones contra cien mil, y eso es todo el concurso.
Esta es la jugada. El arreglo está ordenado, así que a[hi] es el valor más grande que sigue en juego. Si a[lo] + a[hi] es demasiado chico, entonces a[lo] no tiene pareja en ninguna parte — lo acabas de emparejar con lo más grande disponible y aun así te quedaste corto. Así que a[lo] no puede ser parte de ninguna respuesta. Deséchalo y no lo vuelvas a mirar.
La misma lógica en espejo: si la suma es demasiado grande, a[hi] es demasiado grande para todo lo que queda, así que descártalo.
Dos punteros que se acercan desde ambos extremos de un arreglo ordenado. Una celda gris ya fue descartada y no se vuelve a mirar.
int[] a = [2, 7, 11, 15, 19, 26];
int target = 30;
int lo = 0, hi = a.Length - 1;
while (lo < hi)
{
int sum = a[lo] + a[hi];
string move = sum == target ? "= target, stop"
: sum < target ? "< target, lo++"
: "> target, hi--";
Console.WriteLine($"lo={lo} hi={hi} {a[lo],2} + {a[hi],2} = {sum,2} {move}");
if (sum == target) break;
if (sum < target) lo++; else hi--;
}
Console.WriteLine($"\nindices ({lo}, {hi}) -> values ({a[lo]}, {a[hi]})");Imprime:
lo=0 hi=5 2 + 26 = 28 < target, lo++
lo=1 hi=5 7 + 26 = 33 > target, hi--
lo=1 hi=4 7 + 19 = 26 < target, lo++
lo=2 hi=4 11 + 19 = 30 = target, stop
indices (2, 4) -> values (11, 19)Cada paso descarta exactamente un índice y nunca lo reconsidera. Hay n índices, así que hay a lo sumo n pasos. Por eso es lineal, y vale la pena decirlo de esa forma en vez de “los punteros se encuentran en el medio” — el descarte es la razón, el encuentro es solo cómo se ve.
Costo: O(n) en tiempo después del ordenamiento, O(1) en espacio.
Úsalo cuando la entrada esté ordenada o puedas darte el lujo de ordenarla, y mover lo a la derecha haga tu cantidad más grande mientras mover hi a la izquierda la haga más chica. Esa monotonía es todo el requisito. Sin ella el paso de descarte es inválido y todo el asunto devuelve respuestas equivocadas en silencio.
Patrón 2 — El puntero de escritura
Elimina los duplicados de un arreglo ordenado en el lugar, y reporta cuántos valores quedan.
La versión tentadora construye un List<int>, agrega los que se conservan, y copia de vuelta. Es correcta. También asigna un segundo arreglo, y con 10⁶ elementos esa asignación es la diferencia entre pasar y no pasar.
Aquí los dos punteros se mueven en la misma dirección. r lee cada celda. w marca dónde va el siguiente valor que se conserva. La razón por la que nada se destruye es que w nunca puede rebasar a r — w solo avanza cuando r avanza, y arranca por detrás.
Un arreglo, dos tareas. r lee cada celda, w marca dónde va el siguiente valor que se conserva. w nunca rebasa a r, así que nada se sobrescribe antes de leerse. Todo lo que queda pasado w al final está viejo y se ignora.
int[] a = [1, 1, 2, 2, 2, 3, 4, 4, 5];
Console.WriteLine($"before: [{string.Join(", ", a)}]\n");
int w = 1;
for (int r = 1; r < a.Length; r++)
{
if (a[r] == a[w - 1])
{
Console.WriteLine($"r={r} a[r]={a[r]} {$"same as a[{w - 1}]",-12} skip w stays {w}");
continue;
}
a[w] = a[r];
w++;
Console.WriteLine($"r={r} a[r]={a[r]} {"new value",-12} a[{w - 1}]={a[r]} w -> {w}");
}
Console.WriteLine($"\nkept {w}: [{string.Join(", ", a[..w])}]");
Console.WriteLine($"tail : [{string.Join(", ", a[w..])}] <- stale, and that is fine");Imprime:
before: [1, 1, 2, 2, 2, 3, 4, 4, 5]
r=1 a[r]=1 same as a[0] skip w stays 1
r=2 a[r]=2 new value a[1]=2 w -> 2
r=3 a[r]=2 same as a[1] skip w stays 2
r=4 a[r]=2 same as a[1] skip w stays 2
r=5 a[r]=3 new value a[2]=3 w -> 3
r=6 a[r]=4 new value a[3]=4 w -> 4
r=7 a[r]=4 same as a[3] skip w stays 4
r=8 a[r]=5 new value a[4]=5 w -> 5
kept 5: [1, 2, 3, 4, 5]
tail : [3, 4, 4, 5] <- stale, and that is fineMira la cola. [3, 4, 4, 5] se queda ahí, vieja. Eso no es un error que haya que limpiar — sobrescribirla costaría otra pasada sin ningún beneficio. El contrato es que la respuesta es a[..w], y todo lo que está pasado w no es asunto de quien llama.
Costo: O(n) en tiempo, O(1) en espacio.
Úsalo cuando el problema diga en el lugar, o devuelve la nueva longitud, o sin asignar memoria. Compactar, filtrar y particionar por un predicado son todos este mismo patrón con otras palabras.
Patrón 3 — Ordena, ancla, recorre
Encuentra todos los triples que suman cero, sin reportar ningún triple dos veces.
Tres bucles anidados son O(n³) y no van a pasar. Pero fija el primer valor y mira lo que queda: encuentra dos valores que sumen -a[i]. Eso es el patrón 1, exactamente. Ordenar una vez al principio cuesta O(n log n) y compra la monotonía que el patrón 1 necesita.
La parte realmente delicada no es la búsqueda, son los duplicados. Hay que omitirlos en dos lugares distintos, por dos razones distintas:
- Un ancla repetida. Si
a[i] == a[i-1], todo triple que empieza eniya se encontró empezando eni-1. Omite el ancla por completo. - Un
loohirepetido después de un acierto. Una vez registrado un triple, mueve los dos punteros más allá de cualquier copia de los valores recién usados, o la siguiente iteración reporta el mismo triple otra vez.
Ordena una vez, fija un valor y corre dos punteros sobre el resto. Omitir un ancla repetida es lo que evita que el mismo triple se reporte dos veces.
int[] a = [-1, 2, -4, -1, 1, 0];
Array.Sort(a);
Console.WriteLine($"sorted: [{string.Join(", ", a)}]\n");
List<(int, int, int)> found = [];
for (int i = 0; i < a.Length - 2; i++)
{
if (i > 0 && a[i] == a[i - 1])
{
Console.WriteLine($"anchor i={i} a[i]={a[i],2} duplicate anchor, skip");
continue;
}
int lo = i + 1, hi = a.Length - 1;
Console.WriteLine($"anchor i={i} a[i]={a[i],2} need a[lo] + a[hi] == {-a[i]}");
while (lo < hi)
{
int sum = a[i] + a[lo] + a[hi];
Console.WriteLine($" lo={lo} hi={hi} {a[i],2} + {a[lo],2} + {a[hi],2} = {sum,2}");
if (sum == 0)
{
found.Add((a[i], a[lo], a[hi]));
while (lo < hi && a[lo] == a[lo + 1]) lo++;
while (lo < hi && a[hi] == a[hi - 1]) hi--;
lo++; hi--;
}
else if (sum < 0) lo++;
else hi--;
}
}
Console.WriteLine();
foreach (var t in found) Console.WriteLine($"triplet: {t}");Imprime:
sorted: [-4, -1, -1, 0, 1, 2]
anchor i=0 a[i]=-4 need a[lo] + a[hi] == 4
lo=1 hi=5 -4 + -1 + 2 = -3
lo=2 hi=5 -4 + -1 + 2 = -3
lo=3 hi=5 -4 + 0 + 2 = -2
lo=4 hi=5 -4 + 1 + 2 = -1
anchor i=1 a[i]=-1 need a[lo] + a[hi] == 1
lo=2 hi=5 -1 + -1 + 2 = 0
lo=3 hi=4 -1 + 0 + 1 = 0
anchor i=2 a[i]=-1 duplicate anchor, skip
anchor i=3 a[i]= 0 need a[lo] + a[hi] == 0
lo=4 hi=5 0 + 1 + 2 = 3
triplet: (-1, -1, 2)
triplet: (-1, 0, 1)El ancla en i=2 se omite sin un solo paso interno, porque -1 ya tuvo su turno en i=1. Esa omisión es lo que hace que la salida sea un conjunto y no una lista con repetidos.
Costo: O(n²) en tiempo — n anclas, cada una con un recorrido lineal — más el ordenamiento. O(1) en espacio, aparte de la salida.
Úsalo cuando necesites una combinación de tamaño fijo que cumpla una condición. Four-sum es esto otra vez con un bucle más por fuera.
Patrón 4 — Manda cada valor a su propio índice
Un arreglo tiene n valores en el rango 1..n. Un valor aparece dos veces, otro falta. Encuentra los dos, sin usar memoria extra.
Un HashSet<int> lo resuelve y cuesta O(n) de memoria. El truco de sumar los valores te da una ecuación y necesitas dos. Pero mira otra vez la restricción: los valores son 1..n y el arreglo tiene longitud n. El arreglo es una tabla hash, y la función hash es v - 1.
Así que pon cada valor donde corresponde. El valor 3 va al índice 2. Si dos valores quieren el mismo lugar, el arreglo deja de poder moverse, y la celda que nunca se llenó te dice qué falta.
El bucle es un while, no un for, y eso importa. Después de un intercambio, el índice i tiene un valor distinto que todavía no se ha colocado, así que i no debe avanzar. Avanza solo cuando el valor en i ya está en su lugar.
El ordenamiento cíclico manda cada valor al índice que le corresponde. Cuando dos valores quieren el mismo lugar el arreglo deja de moverse, y lo que queda fuera de sitio nombra tanto el duplicado como el número faltante.
int[] a = [3, 1, 5, 4, 3, 2];
Console.WriteLine($"start: [{string.Join(", ", a)}] values are 1..{a.Length}\n");
int i = 0;
while (i < a.Length)
{
int home = a[i] - 1;
if (a[i] != a[home])
{
Console.WriteLine($"i={i} a[i]={a[i]} belongs at index {home}, which holds {a[home]} swap");
(a[i], a[home]) = (a[home], a[i]);
Console.WriteLine($" -> [{string.Join(", ", a)}]");
}
else
{
Console.WriteLine($"i={i} a[i]={a[i]} is already home (or its twin is) i++");
i++;
}
}
Console.WriteLine($"\nsorted as far as it can be: [{string.Join(", ", a)}]\n");
for (int j = 0; j < a.Length; j++)
if (a[j] != j + 1)
Console.WriteLine($"index {j} holds {a[j]}, should hold {j + 1} -> duplicate = {a[j]}, missing = {j + 1}");Imprime:
start: [3, 1, 5, 4, 3, 2] values are 1..6
i=0 a[i]=3 belongs at index 2, which holds 5 swap
-> [5, 1, 3, 4, 3, 2]
i=0 a[i]=5 belongs at index 4, which holds 3 swap
-> [3, 1, 3, 4, 5, 2]
i=0 a[i]=3 is already home (or its twin is) i++
i=1 a[i]=1 belongs at index 0, which holds 3 swap
-> [1, 3, 3, 4, 5, 2]
i=1 a[i]=3 is already home (or its twin is) i++
i=2 a[i]=3 is already home (or its twin is) i++
i=3 a[i]=4 is already home (or its twin is) i++
i=4 a[i]=5 is already home (or its twin is) i++
i=5 a[i]=2 belongs at index 1, which holds 3 swap
-> [1, 2, 3, 4, 5, 3]
i=5 a[i]=3 is already home (or its twin is) i++
sorted as far as it can be: [1, 2, 3, 4, 5, 3]
index 5 holds 3, should hold 6 -> duplicate = 3, missing = 6Eso parece que podría ser cuadrático — un bucle con un intercambio adentro que a veces no avanza. No lo es. Cada intercambio pone al menos un valor en su lugar definitivo, y un valor que ya está en su lugar nunca se vuelve a mover. Hay n valores, así que hay a lo sumo n intercambios en toda la ejecución.
Cuando los valores son una permutación de un rango conocido, el arreglo ya es una tabla hash y tienes permiso de usarlo como tal.
Costo: O(n) en tiempo, O(1) en espacio.
Úsalo cuando el problema diga valores del 1 al n, o del 0 al n, y pida uno faltante o uno duplicado. Esa frase es la pista, y te está haciendo un favor por estar ahí.
Patrón 5 — Tres regiones en una pasada
Ordena un arreglo que solo contiene 0, 1 y 2. Una pasada, sin ordenamiento por comparación.
Contar cada valor y reescribir funciona, y son dos pasadas. Tampoco generaliza, que es la objeción de fondo — la versión de abajo es cómo particionas alrededor de un pivote cuando hay muchas claves iguales, que es lo que evita que quicksort se degrade con entradas llenas de duplicados.
Tres índices parten el arreglo en cuatro regiones. Todo lo que está a la izquierda de low es un 0 ya resuelto. Todo lo que está a la derecha de high es un 2 ya resuelto. Entre mid y high está la parte que nadie ha mirado todavía, y se encoge en uno en cada iteración.
Todo el algoritmo son estas tres reglas más una invariante: todo lo que está a la izquierda de low es un 0, todo lo que está a la derecha de high es un 2, y la región desconocida se encoge en uno en cada iteración. Esa última regla es la que la gente escribe mal — el valor que llega intercambiado desde high nunca fue examinado, así que mid no debe pasarlo.
Lee otra vez esa tercera regla, porque es la que se escribe mal. Cuando intercambias a[mid] con a[high], el valor que llega a mid viene de la región sin examinar. Nadie lo ha probado. Avanza mid más allá de él y acabas de meter un valor sin probar entre los 1 ya resueltos. Avanzar mid en el caso 0 está bien por la razón opuesta: el valor que llega viene de low, y todo lo que está antes de mid ya fue probado.
int[] a = [2, 0, 2, 1, 1, 0, 2, 1, 0];
Console.WriteLine($"start: [{string.Join(", ", a)}]\n");
int low = 0, mid = 0, high = a.Length - 1;
while (mid <= high)
{
switch (a[mid])
{
case 0:
(a[low], a[mid]) = (a[mid], a[low]);
Console.WriteLine($"a[mid]=0 swap into the 0s low {low}->{low + 1} mid {mid}->{mid + 1} high {high} [{string.Join(", ", a)}]");
low++; mid++;
break;
case 1:
Console.WriteLine($"a[mid]=1 already correct low {low} mid {mid}->{mid + 1} high {high} [{string.Join(", ", a)}]");
mid++;
break;
default:
(a[mid], a[high]) = (a[high], a[mid]);
Console.WriteLine($"a[mid]=2 swap into the 2s low {low} mid {mid} high {high}->{high - 1} [{string.Join(", ", a)}]");
high--;
break;
}
}
Console.WriteLine($"\ndone: [{string.Join(", ", a)}]");Imprime:
start: [2, 0, 2, 1, 1, 0, 2, 1, 0]
a[mid]=2 swap into the 2s low 0 mid 0 high 8->7 [0, 0, 2, 1, 1, 0, 2, 1, 2]
a[mid]=0 swap into the 0s low 0->1 mid 0->1 high 7 [0, 0, 2, 1, 1, 0, 2, 1, 2]
a[mid]=0 swap into the 0s low 1->2 mid 1->2 high 7 [0, 0, 2, 1, 1, 0, 2, 1, 2]
a[mid]=2 swap into the 2s low 2 mid 2 high 7->6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=1 already correct low 2 mid 2->3 high 6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=1 already correct low 2 mid 3->4 high 6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=1 already correct low 2 mid 4->5 high 6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=0 swap into the 0s low 2->3 mid 5->6 high 6 [0, 0, 0, 1, 1, 1, 2, 2, 2]
a[mid]=2 swap into the 2s low 3 mid 6 high 6->5 [0, 0, 0, 1, 1, 1, 2, 2, 2]
done: [0, 0, 0, 1, 1, 1, 2, 2, 2]Nueve valores, nueve iteraciones, y nunca compara dos elementos del arreglo entre sí.
Costo: O(n) en tiempo, O(1) en espacio, y es estable en el sentido que importa aquí — una pasada, sin recursión.
Úsalo cuando estés particionando en tres grupos con una prueba barata sobre cada elemento. El planteo clásico son los colores de la bandera; el planteo útil es menor que el pivote, igual al pivote, mayor que el pivote.
Qué recordar
-
Los extremos opuestos necesitan monotonía, no solo que esté ordenado. Mover
loa la derecha debe empujar tu cantidad hacia un lado y moverhia la izquierda debe empujarla hacia el otro. Revisa eso antes de confiar en el descarte. -
Dos punteros en la misma dirección son la edición en el lugar.
wva detrás der, así que nada se sobrescribe antes de leerse, y la cola vieja pasadawes deliberada. -
Un ancla repetida y un puntero repetido son dos errores de duplicados distintos. Arreglar uno no arregla el otro, y solo uno de los dos se ve en un caso de prueba chico.
-
1..nen el enunciado significa que el arreglo puede ser su propia tabla hash. O(1) en espacio en vez de O(n), y el bucle de intercambios es lineal porque cada intercambio deja un valor resuelto para siempre. -
Después de intercambiar desde
high,midno se mueve. El valor que acabas de recibir nunca fue examinado. Es un carácter de diferencia y es el error más común de todo el patrón.
La parte 2 toma la misma idea de dos índices y hace que los dos punteros viajen en la misma dirección, donde el hueco entre ellos es la respuesta: ventanas deslizantes, y el truco de a-lo-sumo-K que convierte “exactamente K” en una resta.