Agrupe y clasifique con un mapa

Muchos problemas le piden agrupar elementos que tienen algo en común. Un mapa de claves a grupos convierte esto en un único recorrido limpio. 🗂️

El truco consiste en elegir una clave que sea idéntica para los elementos del mismo grupo. Si acierta, el resto resulta sencillo.

Use defaultdict(list) para que cada clave nueva comience con un grupo vacío. Puede añadir elementos sin comprobar nunca si la clave existe.

Para cada elemento, calcule su clave y append el elemento al grupo de esa clave. Una línea por elemento agrupa todo.

Los anagramas comparten sus letras ordenadas, por lo que la cadena ordenada es la clave de grupo perfecta. Ordene una vez y después agrupe según ella.

Cuando ordenar resulta lento, también puede usar como clave una tupla de recuentos de letras. Las tuplas son hashable, así que encajan perfectamente en un dict.

Agrupe números por su resto, paridad o longitud cambiando únicamente la clave. El patrón sigue siendo idéntico en distintos problemas.

Cuando los valores caben en un intervalo pequeño, coloque cada uno en un grupo indexado y léalos en orden. Esto permite una ordenación casi lineal.

Después de crear los grupos, la respuesta suele estar en los values del dict. Conviértalos en una lista cuando el juez necesite los grupos como tales.

Si solo necesita los tamaños de los grupos, agrupe en un Counter o sume las longitudes al final. Elija según lo que realmente solicite el enunciado.

Agrupar con un mapa requiere O(n) en lugar de comparar cada par. La clave hasheada realiza el trabajo de encontrar las coincidencias.

Agrupe asociando la clave de cada elemento con un grupo de defaultdict en un único recorrido O(n). Elija bien la clave y los problemas de agrupación resultarán mucho más sencillos. 🚀