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)` 😍
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)`
`\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
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:
- Si el resultado es IGUAL a `Q`, entonces terminamos
- 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.
- Si el resultado es MENOR que `Q`, entonces buscamos sumarle un número más grande; probamos con el segundo más chico.
- 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()
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)`
