4Sum diseccionado
Vamos a llevar un célebre problema de entrevistas técnicas a la morgue. Lo diseccionaremos con precisión quirúrgica, cortándolo en diminutos fragmentos hasta revelar sus más oscuros secretos. Acompáñame en este relato teñido de sangre y lógica implacable. Te advierto: será un viaje largo… y quizás perturbador.
Problema:
Dado un array de enteros nums y un entero target, encontrar todos los cuartetos
únicos [nums[a], nums[b], nums[c], nums[d]] tales que:
0 ≤ a,b,c,d < na,b,cy d son índices distintosnums[a] + nums[b] + nums[c] + nums[d] == target
Ejemplo:
- Input:
nums=[1,0,-1,0,-2,2],target = 0 - Output:
[[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]]
Fuerza bruta ¡bruta!
Hagamos un primer intento de resolver esto: nos piden un arreglo con sub-arreglos de 4 elementos cada uno, cuya suma es 0, no parece muy complicado.
// input de ejemplo
$nums = [1, 0, -1, 0, -2, 2];
$target = 0;
// acá almacenaremos los resultados cuya suma es 0
$result = [];
// Necesitamos un `for` para recorrer el arreglo... de perogrullo!
for($i = 0; $i < count($nums); $i++) {
// Necesitamos otro `for` para combinar con $i
for($j = 0; $j < count($nums); $j++) {
// Ehhhh necesitamos otro `for` para combinar con $j
for($k = 0; $k < count($nums); $k++) {
// ¡adivina!... otro para combinar con $k
for($l = 0; $l < count($nums); $l++) {
// Verificamos si la suma de los 4 números es igual al objetivo
if ($nums[$i] + $nums[$j] + $nums[$k] + $nums[$l] == $target) {
$quadruplet = [$nums[$i], $nums[$j], $nums[$k], $nums[$l]];
if (!in_array($quadruplet, $result)) {
$result[] = $quadruplet;
}
}
}
}
}
}
El resultado final es un $result con 85 arreglos que suman 0… ¡espera un
segundo!… ¡85!… WTF!
Acá hay algo muy mal, veamos, si te fijas todos los bucles for arrancan en 0,
lo que nos permite generar combinaciones con los mismos números de índice en
diferente orden, o dicho de otra forma, se repiten los índices ¿Cómo arreglamos
esto? incrementando en uno el valor de inicio del siguiente for:
for($i = 0; ...)
for($j = $i + 1; ... )
for($k = $j + 1; ... )
for($l = $l + 1; ...)
Una mejora más: para asegurar de que siempre haya al menos tres números después de $i debemos restringir el alcance de los bucles, es decir: $i solo puede llegar a $n - 3, $j solo puede llegar a $n - 2 y $k solo puede llegar a $n - 1, $l al ser el último puedo menor a $n.
En consecuencia nuestros bucles fors deberían quedar así:
for($i = 0; $i < $n - 3; $i++) {
for($j = $i + 1; $j < $n - 2; $j++) {
for($k = $j + 1; $k < $n - 1; $k++) {
for($l = $k + 1; $l < $n; $l++) {
Así ha quedado:
function fourSum($nums, $target) {
$result = [];
$n = count($nums);
for( $i = 0; $i < $n - 3; $i++) {
for ($j = $i + 1; $j < $n - 2; $j++) {
for ($k = $j + 1; $k < $n - 1; $k++) {
for ($l = $k + 1; $l < $n; $l++) {
if ($nums[$i] + $nums[$j] + $nums[$k] + $nums[$l] == $target) {
$quadruplet = [$nums[$i], $nums[$j], $nums[$k], $nums[$l]];
if (!in_array($quadruplet, $result)) {
$result[] = $quadruplet;
}
}
}
}
}
}
return $result;
}
Dejemos de lado la fuerza bruta
Hasta el momento nuestro script sigue siendo fuerza bruta, podríamos decir «fuerza bruta funcional». Tenemos 4 bucles fors anidados que nos dejan los ojos ensangrentados. El golpe en la performance es demasiado grande, la complejidad temporal es de O(n4). Veamos si podemos optimizar esto.
Two pointers
Existe una técnica en programación de nombre Two Pointers; en la cual dos punteros recorren una estructura de datos, generalmente en direcciones opuestas; éstos avanzan o retroceden de acuerdo a las condiciones especificadas.
// Problema: Busca el par de elementos que sumen 7
// Lista ordenada
$list = [2, 3, 4, 8, 13];
// objetivo
$target = 7;
$result = null;
// puntero izquierdo
$left = 0;
// puntero derecho
$right = count($list) - 1;
// Iniciamos bucle while
while ($left < $right) {
// sumamos los valores
$currentSum = $list[$left] + $list[$right];
// evaluamos ¿es igual a target?
// si lo es ¡problema resuelto!
if ($currentSum === $target) {
$result = [$list[$left], $list[$right]];
break;
}
// Evaluamos: ¿Es la suma menor al objetivo?
if ($currentSum < $target) {
// Es menor... entonces avanzamos
// un lugar por la izquierda
$left++;
// de lo contrario retrocedemos
// un lugar por la derecha
} else {
$right--;
}
}
echo implode(", ", $result) . PHP_EOL; // 3, 4
La complejidad temporal de un bucle while es O(n), ya que, en el peor de los casos, ejecutará como máximo n iteraciones. Es importante asegurarse de que la lista inicial esté ordenada; de lo contrario, la complejidad aumentaría a O(n log n).
Volviendo a nuestro problema
Ya tenemos claro cómo encontraremos los dos últimos números (con la ayuda de
Two Pointers). Para los primeros dos usaremos dos bucles for anidados.
Resolviendo el problema
El siguiente gráfico muestra cómo resolveremos finalmente el problema 4Sum:
Necesitamos:
- Listado inicial ordenado.
- Bucle externo (
i) para encontrar el primer número. - Bucle interno (
j) para encontrar el segundo número. - Two pointers para
k(left) yl(right) para encontrar los últimos dos números.
Cuartetos únicos
La primera vez que intenté resolver este problema pasé por alto algo muy importante: los cuartétos deben ser únicos, en otras palaras [1, 2, -1, -2] y [-1, -2, 1, 2] son soluciones válidas, sí, pero son la misma combinación de números. Así que debemos evitar duplicados.
Solución final
public function fourSum(array $nums, int $target): array
{
// Requisito fundamental, ordenar
sort($nums);
// Donde guardaremos los resultados
$result = [];
// Contamos los elementos del arreglo inicial
$n = count($nums);
// For externo
for($i = 0; $i < $n - 3; $i++) {
// Evitamos cuartetos duplicados para el primer número
if ($i > 0 && $nums[$i] == $nums[$i - 1]) {
continue;
}
// For interno
for($j = $i + 1; $j < $n - 2; $j++) {
// Evitamos cuartetos duplicados para el segundo número
if ($j > $i + 1 && $nums[$j] == $nums[$j - 1]) {
continue;
}
// punteros izquierda y derecha
$left = $j + 1;
$right = $n - 1;
// Acá la técnica Two Pointers inicia su magia
while($left < $right) {
// Hacemos la suma para ver si nos sirve, de no tener
// un resultado esperado avanzaremos los punteros izq
// o der según el resultado que nos de $sum.
$sum = $nums[$i] + $nums[$j] + $nums[$left] + $nums[$right];
// Hora de la verdad
if ($sum == $target) {
// Se encontró un cuarteto válido, guadamos el resultado
$result[] = [$nums[$i], $nums[$j], $nums[$left], $nums[$right]];
// Saltamos valores duplicados para el tercer número
while ($left < $right && $nums[$left] == $nums[$left + 1]) {
$left++;
}
// Saltamos valores duplicados para el 4to número
while ($left < $right && $nums[$right] == $nums[$right - 1]) {
$right--;
}
// Mueve los punteros
$left++;
$right--;
} elseif ($sum < $target) {
// Si la suma es menor que el objetivo, mueva el puntero izquierdo hacia la derecha.
$left++;
} else {
// Si la suma es mayor que el objetivo, mueva el puntero derecho hacia la izquierda.
$right--;
}
} // while
} // for $j
} // for $i
return $result;
}
Complejidad temporal
- Ordenar el arreglo toma O(N log N)
- Los dos bucles anidados toman O(N^2)
- La búsqueda con dos punteros toma O(N)
- Complejidad total: O(N^3)
¿Test?… test:
Te comparto la solución final junto a sus test. Acá el resultado de los mismos:
Four Sum
✔ Basic case
✔ No solution
✔ Multiple solutions
✔ Negative numbers
✔ Duplicates in array
✔ Small array
OK (6 tests, 6 assertions)