Nerding about stuff I've found interesting

Problema

Dados un arreglo `A` de números y un número `Q`, determinar si hay dos elementos DIFERENTES en `A` que sumen `Q`.

Problema en Leetcode: https://leetcode.com/problems/two-sum/

Ejemplo:

Input: [2, 0, -13, 6, 28, 7, 10, 5, 17, 9]

Output: [13, 17]

Explicación: -13 + 17 = 4

Aclaración: Aunque 2 + 2 = 4 , no podemos usar el mismo elemento de A, es decir, A[0] + A[0] no es una suma de dos elementos diferentes.

Solución 1: Fuerza bruta

Recorrer cada elemento del arreglo y por cada iteración recorrer el RESTO de los elementos y verificar si la suma de ambos es igual a `Q`

Complejidad

  • Tiempo: `O(n^2)` 🚩
  • Espacio `O(1)` 😍
solution1.cpp

Pequeña optimización:

No es necesario revisar las combinaciones a la izquierda de un elemento puesto que fueron revisadas en iteraciones anteriores.

Si estamos analizando `A[i]`, entonces todas las combinaciones de `A[i]`  con todos los elementos desde `A[0]` hasta `A[i-1]` ya fueron checadas antes:

Sin embargo, la solución sigue teniendo complejidad `O(n^2)` 🚩 en tiempo.

Explicación:

Por cada una de las `n` iteraciones:

  • En la primera iteración vamos a checar `n-1` combinaciones
  • En la segunda `n-2`
  • En la tercera `n-3`
  • ...
  • En la penúltima checamos `1` combinación.

En otras palabras el peor de los escenarios realizamos

`n-1 + n-2 + n-3 + ... + 1`

operaciones, es decir

`1 + 2 + 3 + ... + n-1`

O sea:

`\frac{n(n+1)}{2} = O(n^2)`

porque:

`\sum_{k=1}^{n} = \frac{n(n+1)}{2}`

Solución 2: Sacrificando espacio para reducir tiempo

Usando un hashmap podemos hacer consultas en tiempo constante `O(1)` 😍.

En este hashmap guardaríamos todos los elementos de `A` para iterar UNA sola vez y preguntar:

"Existe `Q - A[i]` en `A`?"

Preguntamos "existe `Q-A[i]` en `A`?" porque cuando estamos observando el elemento `A[i]` queremos saber si existe otro elemento `X` en `A` tal que:

$$A[i] + X = Q$$

De ahí que:

$$X = Q - A[i]$$

Esta solución tiene complejidad:

  • `O(n)` 🙂 en tiempo
  • `O(n)` 🙂 en espacio
solution2.go

Solución 3: Mira mamá, sin manos!

En esta solución no usamos espacio adicional a cambio de ir un poquito más lento.

Esta es una estrategia de aproximación en donde empezamos con el número más grande y el más pequeño que exista en `A`, los sumamos y evaluamos si el resultado es más grande, más chico o igual que el valor que buscamos `Q`.

Basado en el resultado decidimos qué hacer usando las siguientes reglas:

  1. Si el resultado es IGUAL a `Q`, entonces terminamos
  2. Si el resultado es MAYOR que `Q`, entonces buscamos sumarle un número más chiquito, por lo que ahora probamos con el segundo más grande.
  3. Si el resultado es MENOR que `Q`, entonces buscamos sumarle un número más grande; probamos con el segundo más chico.
  4. Continuamos repitiendo los pasos anteriores hasta que nos quedemos sin más números para probar o encontremos dos que sumen `Q`.

Así, nuestro algoritmo será tan eficiente como nuestra forma de encontrar el "siguiente número más chico/grande", es decir, será `O(n \times X)` donde `X` es el costo de encontrar dicho número.

En el siguiente código `X` es el costo de:

  • EL_SIGUIENTE_MÁS_CHICO()
  • EL_SIGUIENTE_MÁS_GRANDE()
partialsolution3.py

Si `A` estuviera ordenado, encontrar estos números es trivial.

Q: En dónde está el más grande de la lista?
A: Al final

Q: Y el 2º más grande?
A: A la izquierda del 1º

Q: Y el 3º más grande?
A: A la izquierda del 2º

Lo inverso sucede con el más chico (de izq a derecha).

Entonces para encontrar el siguiente más grande o chico basta con seleccionar el siguiente a la izquierda o derecha del actualmente más grande o más chico, en otras palabras, tiene costo `O(1)` 😍

Y como ordenar una lista tiene costo `O(nlogn)` tenemos:

  • Tiempo: `O(nlogn)`
  • Espacio: `O(1)`
solution3.py