Top K Frequent Elements

Last updated Aug 5, 2023 Edit Source

• Programming
• Interviewprep
• Leetcode

Es un problema bastante sencillo que te tiene que enseñar todavia un par de trucos interesantes, especificamente con el algoritmo de sorting Bucket Sort. El problema dicta lo siguiente:

Dado un array de numeros nums retorna la cantidad de k valores que se repitan mas veces. Por ejemplo, dado el array [1,1,1,2,2,3] retorna los 2 valores mas comunes. La respuesta es [1,2].

Para solucionar este problema tenemos dos alternativas (realmente mas pero escenciales de enteder solamente dos). Una conlleva el uso de un algoritmo de sorting y la otra el uso de una variacion del Bucket Sort.

Es posible solucionar el problema de forma bastante sencilla utilizando un algoritmo de sorting:

1. Inicializar un mapa vacio en el que la llave correspondera a un numero particular y el valor a la cantidad de veces que este aparece en el array.
2. Cargar el mapa con los datos del array
3. Ordenar el mapa por los valores en forma descendente, de modo que, el elemento que se repite mas veces se encuentre al inicio
4. Retornar los k primeros elementos

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

function topKFrequent(nums: number[], k: number): number[] {
	const map = new Map<number, number>();

	for (const n of nums) {
		map.has(n)
			? map.set(n, map.get(n) as number + 1)
			: map.set(n, 1);
	}

	const sorted = [...map.entries()].sort((a, b) => b[1] - a[1]).map(e => e[0]);
	return sorted.slice(0, k);
}

Se puede utilizar un truquito una vez que entiendes algo intereasnte del problema: Como maximo, un elemento puede repetirse hasta nums.length veces, NO MAS. Con eso en mente podemos desarrollar lo siguiente:

1. Inicializar un mapa vacio en el que la llave correspondera a un numero particular y el valor a la cantidad de veces que este aparece en el array.
2. Cargar el mapa con los datos del array
3. Inicializar un array en el que el indice ith contendra una lista con los elementos que se repiten dicha cantidad de veces. Por ejemplo
4. Cargamos el array con los datos del mapa, de modo que, si un elemento se repite tres veces (1) se encontrara en el indice 3 del array.
5. Inicialziamos una variable que tendra la respuesta
6. Iteramos el mapa iniciando por el final (debido a que alli se encuentran las listas que contienen los elementos que se repiten mas veces).
7. Vamos agregando elementos de las listas conforme vayan apareciendo en el mapa recorriendolo de fin a principio
8. Cada vez que agreguemos un elemento, debemos comprobar si ahora tenemos la cantidad k de elementos que buscamos.
9. De ser asi, retornamos el resultado
10. De no ser asi, seguimos con la iteracion hasta que retornemos

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

function topKFrequent(nums: number[], k: number): number[] {
	const map = new Map<number, number>();

	for (const n of nums) {
		map.has(n)
			? map.set(n, map.get(n) as number + 1)
			: map.set(n, 1);
	}

	const freq = Array.from({ length: nums.length + 1}, () => [] as number[]);

	for (const [key, value] of map.entries()) {
		freq[value].push(key);
	}

	const result: number[] = []
	for (let i = freq.length-1; i >= 0; i--) {
		for (const n of freq[i]) {
			result.push(n);
			if (result.length === k) {
				return result;
			}
		}
	}
	return result;
}

En este problema, el hecho de que se necesite contar la cantidad de apariciones de cada numero ya implica el uso de un notes/Hash Table (hashmap, map, diccionario, objeto, pares de clave-valor) que sirva para guardar dos cosas:

1. Llave: Cada numero unico dentro del array
2. Valor: La cantidad de veces que aparece

Esto es asi, debido a que, por la definicion del Hash Table, podemos saber que las llaves seran unicas, lo que nos permitira contar la cantidad de veces que este ocurre en el array nums.

De modo que, dado un array como el siguiente: [1, 1, 7, 7, 7, 5, 5, 5, 5] podamos tener un hashmap como:

1
2
3
4
5

map = {
	1: 2
	7: 3
	5: 4
}

Con esto ya tenemos la primera parte del problema resuelto. Ahora, podemos tomar varios approaches para terminar de solucionar el problema.

La siguiente parte implica obtener los K elementos mas comunes, para esto, necesitamos re-ordenar el mapa basado en valores, o obtener de alguna forma los K valores mas comunes.

Una forma de hacerlo, es utilizando sorted en python, este recibe tres valores: sorted(iterable, key, reverse=?)

1. Iterable. La coleccion iterable que se quiere ordenar
2. Key. Un callback para una funcion que indica como se ordenara
3. Reverse. Si la lista se busca inversa o no

1

tupla = sorted(hm.items(), key=lambda x:x[1], reverse=True)

Una vez se aplica esta funcion, podemos retornar las llaves hasta los k elementos.

1
2
3
4
5
6
7
8
9

def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        hm = {}
        for num in nums:
            if num in hm:
                hm[num] = hm.get(num) + 1
            else:
                hm[num] = 1
        result = sorted(hm.items(), key=lambda x:x[1], reverse=True)
        return [result[i][0] for i in range(k)]