¡Bienvenido de nuevo a nuestra serie de blogs sobre resolución de problemas en la ingeniería de software moderna!

En la Parte 1, exploramos el Patrón de contador de frecuencia, una técnica poderosa para optimizar algoritmos contando eficientemente la frecuencia de los elementos. Si te lo perdiste o quieres un repaso rápido, no dudes en consultarlo antes de continuar.

En esta parte, nos sumergiremos en otro patrón esencial: el patrón multipunto. Este patrón es invaluable cuando se trata de escenarios en los que es necesario comparar, buscar o recorrer múltiples elementos simultáneamente. Exploremos cómo funciona y dónde puedes aplicarlo para mejorar la eficiencia de tu código.

02. Patrón multipuntero

El patrón multipuntero es una técnica utilizada en el diseño de algoritmos donde se emplean múltiples punteros (o iteradores) para atravesar estructuras de datos como matrices o listas vinculadas. En lugar de depender de un único puntero o bucle, este patrón utiliza dos o más punteros que se mueven a través de los datos a diferentes velocidades o desde diferentes puntos de partida.

Ejemplo de problema

Escribe una función llamada sumZero que acepte una matriz ordenada de números enteros. La función debe encontrar el primer par donde la suma es cero. Si dicho par existe, devuelve una matriz que incluye ambos valores; de lo contrario, devuelve indefinido.

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

Solución básica

function sumZero(arr){
    for (let i = 0; i 



Complejidad del tiempo - O(N^2)

Solución usando patrón multipuntero

paso 1: comprender el problema

Necesitamos encontrar dos números en una matriz **ordenada que sumen cero. Dado que la matriz está ordenada, podemos aprovechar este orden para encontrar la solución de manera más eficiente.

paso 2: inicializar dos punteros

Configure dos punteros: uno (izquierda) que comience al principio de la matriz y el otro (derecha) que comience al final.

Ejemplo:


Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5




Paso 3: Calcular la suma de los valores en los punteros

Sume los valores en los punteros izquierdo y derecho para obtener la suma


Sum = -4   5 = 1




Paso 4: Compara la suma con cero

• Si la suma es mayor que cero: Mueve el puntero derecho un paso hacia la izquierda para disminuir la suma.

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

• Si la suma es menor que cero: Mueva el puntero izquierdo un paso hacia la derecha para aumentar la suma.

New Sum = -4   2 = -2
Sum is -2 



Paso 5: repetir el proceso

Continúe moviendo los punteros y calculando la suma hasta que se encuentren o encuentre un par.


New Sum = -3   2 = -1
Sum is -1 



La suma es cero, por lo que la función devuelve [-2, 2].

Si el ciclo se completa sin encontrar dicho par, devuelve undefinido.

Código final


function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left  0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left  ;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}




NOTA:
Complejidad del tiempo: O(n) – La función es eficiente y escala linealmente con el tamaño de la matriz.
Complejidad espacial: O(1) – La función utiliza una cantidad mínima de memoria adicional.

Conclusión

El patrón multipunto es una técnica poderosa para resolver problemas que implican buscar, comparar o manipular elementos en una estructura de datos ordenada. Al utilizar múltiples punteros que se acercan entre sí, podemos mejorar significativamente la eficiencia de los algoritmos, reduciendo la complejidad del tiempo de O(n²) a O(n) en muchos casos. Este patrón es versátil y se puede aplicar a una amplia gama de problemas, lo que lo convierte en una estrategia esencial para optimizar el rendimiento de su código.

Estén atentos a nuestra próxima publicación, donde profundizaremos en el Patrón de ventana deslizante otra herramienta esencial para abordar problemas que involucran segmentos de datos dinámicos. ¡Es un patrón increíblemente útil que puede ayudarte a resolver desafíos aún más complejos con facilidad!