Two Sum, resolviendo un reto de programación

Resolver retos de programación es algo que me apasiona: por un lado requiere entender las bases de la programacióny tener un conocimiento profundo del funcionamiento de los ordenadores, saber sobre órdenes de complejidad y la notación "Big O" y por otro lado, tener algo de ingenio y creatividad.

Hay muchas plataformas en las que podrás encontrar todo tipo de retos como este para aprender a resolverlos. Personalmente siempre me ha gustado mucho Project Euler. El otro día encontré de casualidad LeetCode y me propuse ir resolviendo retos de forma esporádica, por diversión. Es algo que siempre me gustó ya que uno aprende mucho al resolver estos problemas, y como digo, me divierte.

El primero de estos retos se titula Two Sum y es el que vamos a resolver hoy. Este tipo de problemas suelen ponerlos en entrevistas técnicas para ver cómo una persona razona, cómo resuelve un problema y poner a prueba sus conocimientos. Este es un tema que podemos debatir en otro vídeo/post.

Lo que quiero destacar es que puedes utilizar cualquier lenguaje para resolverlo, el que más te apetezca. Aquí te recomiendo que lo utilices para mejorar en un lenguaje con el que sientas cómodo, o lo uses para ponerte a prueba en algún lenguaje que estés aprendiendo y mejorar.

Te recomiendo que no sigas leyendo si quieres intentar solucionarlo tú primero y luego volver aquí.

Notación Big O. Órdenes de complejidad.

Los órdenes de complejidad es una herramienta que nos permite clasificar los diferentes algoritmos sin tener en cuenta el tiempo concreto, si no cómo se comportan (ya sea en tiempo o en memoria) en función del tamaño de la entrada.

Por ejemplo, O(1) significa que el tiempo o la memoria son constantes, independientemente del tamaño de la entrada. O(n) es lineal, O(n^2) cuadrático, etc.

Escribiendo este post me doy cuenta que este tema es muy interesante y lo añado a mi lista para comentarlo en profundidad en otro post.

Problema "Two Sum"

Dado un array de enteros, y otro número entero objetivo, tu misión es encontrar dos números del array que sumen el objetivo. En concreto, tienes que devolver un array con los índices de dichos números.

Por ejemplo, siendo el objetivo 6 y el array [ 3, 1, 2, 7, 6, 4, 8], la solución sería encontrar los índices de los números 2 y 4, que sería [2, 5].

Primera solución: fuerza bruta

En general siempre deberías intentar resolver cualquier problema de la forma más simple. ¿Por qué? Porque cuando uno se enfrenta a un problema hay que evitar caer en parálisis por análisis y tener una solución que te permita avanzar hacia un resultado. Igualmente un error común es comenzar intentando optimizar un problema, ya que no sabes dónde puedes tener el cuello de botella en tu algoritmo, lo que no quita que conozcas las limitaciones de tu solución. Vamos a ello.

La primera idea es recorrer el array con un doble bucle for, de forma que para cada número (primer bucle) recorremos el array buscando otro número (segundo bucle) cuya suma sea el número objetivo.

Por ejemplo, una primera solución implementada en Rust puede ser la siguiente:

impl Solution { pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> { 
    for i in 0..nums.len() { 
        for j in (i+1)..nums.len() { 
            if nums[i] + nums[j] == target { 
                return vec![i as i32, j as i32]; 
            } 
        }
    } 
    return vec![]; 
}

Esta solución tiene un orden de complejidad O(n^2), ya que la complejidad es exponencial en función del tamaño de la entrada debido al doble bucle for. Al tener que recorrer y comparar cada elemento con todos los demás elementos del array, hace que necesite cada vez más tiempo.

Segunda solución: usando una tabla hash

El código anterior puede mejorarse de la siguiente forma. Para evitar tener un bucle dentro de un bucle, lo que supone una complejidad de O(n^2) podríamos tener una complejidad d O(n) si conseguimos no anidar los bucles for.

Aquí estuve pensando un rato y la idea es la siguiente: cuando recorres el array del ejemplo, si tienes un 3 sabes que tienes que buscar un el número complementario, en este caso 9 (objetivo) - 3 (n) = 6 (complementario). Por tanto, podemos crear una estructura de datos tipo HashMap, para ir almacenando las diferencias, y luego en otra pasada podemos encontrar si algún elemento del array pertenece a este conjunto en tiempo constante O(1) (esto es una propiedad de algunas tablas hash).

Podríamos solucionarlo con el siguiente código:

use std::collections::HashMap;

pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut dif = HashMap::<i32, i32>::new();
    for i in 0..nums.len() {
        dif.insert(target - nums[i], i as i32);
    }
    for i in 0..nums.len() {
        if let Some(&j) = dif.get(&nums[i]) {
            if i as i32 != j {
                return vec![i as i32,j as i32];
            }
        }
    }

    return vec![];
}

La cosa no queda aquí, ya que podemos optimizarla para calcularlo en una única pasada, evitándonos recorrer dos veces el array inicial.

use std::collections::HashMap;

pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut dif = HashMap::<i32, i32>::new();

    for i in 0..nums.len() {
        if let Some(&j) = dif.get(&nums[i]) {
            if i as i32 != j {
                return vec![i as i32,j as i32];
            }
        }

        dif.insert(target - nums[i], i as i32);
    }

    return vec![];
}

Quiero destacar que esta solución es O(n) pero requerirá más tiempo al necesitar reservar memoria para los datos de la tabla hash, y aunque sea más eficiente para grandes cantidades de datos para conjuntos pequeños posiblemente la primera solución sea más rápida. Igual que por ejemplo la solución 2 y 3 son ambas O(n) pero la segunda en la práctica será más rápida en la práctica.

Esto lo dejo para otro post, ya que como comento los órdenes de complejdiad son un tema muy interesante y profundo, y también nos permite que estudiemos los tiempos de dos algoritmos utilizando tests estadísticos.