Contains Duplicate

Last updated Jul 30, 2023 Edit Source

• Programming
• Interviewprep
• Leetcode

Contains Duplicate es una pregunta de Leetcode bastante basica, te sirve para entender unos cuantos conceptos como los trade-offs que se tienen que hacer entre tiempo y espacio en las soluciones de estos problemas. El enunciado dicta lo siguiente:

Dado un array de numeros enteros (nums). Devuelve verdadero si un elemento aparece por lo menos dos veces en el array, devuelve falso si cada elemento es unico.

Para solucionar este problema basta con utilizar espacio extra y una estructura de datos Set que te permita mantener unicamente los elementos que no se repitan, adicional a esto, las operaciones para traer un elemento son O(1).

1. Inicializar un Set en blanco
2. Recorrer cada elemento del array nums.
3. Si es un elemento que ya se encuentra en el Set retornar true directamente porque es un elemento que ya se encontraba ahi
4. Si no, seguir. En caso de llegar a salir de la adicion de los elementos retornar falso porque para ese punto, ya se checaron todos los elementos y no hay necesidad de seguir.

Dado lo anterior, podemos decir que la complejidad del problema es O(n) como maximo, debido a que, en el peor caso, iteraremos sobre cada elemento y cada uno será unico, con lo que, maximo iteraremos la longitud el array nums (n).

• Tiempo: O(n)
• Espacio: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

function containsDuplicate(nums: number[]): boolean {
    const set = new Set<number>();

    for (const n of nums) {
        if (set.has(n)) {
            return true;
        }
        set.add(n);
    }
    
    return false;
};