Continuemos con nuestra serie sobre algoritmos y estructuras de datos, en este caso vamos a ver el patrón Multiple pointers.

Multiple pointers pattern

Este patrón, pensando en arrays, se basa en crear puntos o valores que corresponden a una posición y moverse al principio, el medio o al final según ciertos condiciones. Este patrón es muy eficiente para reducir al mínimo posible la complejidad espacial.

Pensemos lo primero en un ejemplo donde poder usarlo, vamos a crear un método que dentro de un array ordenado nos devuelva la primera pareja que sume 0.

En un primer momento lo que nos vendría a la cabeza sería hacer 2 loops recorriendo dos veces todo:

function sumZero (arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (arr[i] + arr[j] === 0) {
        return [arr[i], arr[j]]
      } 
    }
  }
}

console.log(sumZero([-2, -1, 0, 1, 2])) // [-2, 2]

Este algoritmo tiene una complejidad:

  • Temporal O(n^2)
  • Espacial O(1)

Que aunque en complejidad espacial no esta mal en temporal se nos puede ir de las manos.

Veamos una solución algo mejor usando este patrón, pero antes de continuar quiero recalcar que esto es posible porque el array esta ordenado, en general muchos de los algoritmos cuentan con esto para poder resolverse (más adelante veremos varios de los mejores patrones de ordenación). Vamos con la solución:

function sumZero (arr) {
  // Establecemos los puntos de inicio (multiple pointers u know)
  let left = 0
  let right = arr.length - 1

  while (left < right) { // para no pasarnos
    let sum = arr[left] + arr[right]

    if (sum === 0) {
      return [arr[left], arr[right]]
    } else if (sum > 0) {
      right--
    } else {
      left++
    }
  }
}

console.log(sumZero([-3, -2, -1, 0, 1, 2, 4])) // [-2, 2]

En esta solución lo que hacemos es ir moviendo nuestros puntos y comprobando si cumple la condición de ser igual a 0. Como es un array ordenado si la suma es mayor de 0 quiere decir que el valor es superior por la derecha del 0 (nuestra variable right) y si el valor es negativo quiere decir que el valor es superior por la izquierda (varible left). Según cual sea de los dos lo que hacemos es ir moviendo nuestros puntos hasta que en algun momento de 0 o hayamos recorrido todos los valores por entre ambos puntos.

Esta solución tiene una complejidad de:

  • Temporal O(n), solo recorremos una vez los valores.
  • Espacial O(1)

Veamos un ejemplo algo más dificil, en este caso queremos comprobar si un string es una subsecuencia de otro, o más bien si aparece como una secuencia de los carácteres de otro pero de manera ordenada, es decir, si word estaría dentro de hello world en orden (no es word pero el orden es primero w y ultimo d)

function isInString (string1, string2) {
  // Establecemos los puntos de inicio (multiple pointers u know)
  let s1 = 0
  let s2 = 0

  while (s2 < string2.length) { // para no pasarnos
    if (string1[s1] === string2[s2]) s1++
    if (s1 === string1.length) return true
    s2++
  }
  return false
}

console.log(isInString('ninja', 'new in jail')) // true si quitamos lo que sobra n__ in ja__

En este caso tenemos dos strings que debemos recorrer y queremos comprobar si el primero string1 es una subsecuencia del segundo string2. En este caso nuestros puntos los situamos al inicio de cada string y vamos recorriendo, si encontramos una coincidencia de la primera posición del string1 en la primera posición del string2, movemos la posición del string1 si no, movemos la posición del string2 y así sucesivamente una vez que hayamos recorrido todo el string1 quiere decir que ya tenemos coincidencia y devolvemos true, en el caso de que la posición de string2 sea mayor que el tamaño del string2 quiere decir que no tenemos coincidencias por lo que devolvemos false.

Este patrón como vemos es muy util para comparar de alguna forma ya sea un elemento o varios y no tener que recorrerlos todos n veces convirtiendo la complejidad temporal en O(n^x) siendo x la cantidad de veces (o la cantidad de elementos) que tenemos que recorrer un elemento (o varios) al completo. En este caso por ejemplo tenemos una complejidad de:

  • Temporal O(n + m). Dos strings que en el peor de los casos recorreremos enteros pero solo una vez cada uno.
  • Espacial O(1)

Hasta aquí lo referente a este patrón de resolución de problemas, nos vemos en el siguienteeee un abraazoooo