LeetCode 49 · Arrays & Hashing · concept: hash-maps

Problem

Given an array of strings, group the ones that are anagrams of each other.

["eat","tea","tan","ate","nat","bat"]
-> [["eat","tea","ate"], ["tan","nat"], ["bat"]]

The core idea — a canonical key

All anagrams of a word share something unique to their group. If you can compute a canonical signature that’s identical for anagrams and different otherwise, you just bucket words by that signature in a hash map. Two natural signatures:

Approach 1 — sorted string as the key

Sorting any anagram yields the same string ("eat", "tea", "ate" all → "aet").

from collections import defaultdict
 
def groupAnagrams(strs):
    groups = defaultdict(list)
    for word in strs:
        key = "".join(sorted(word))     # canonical signature
        groups[key].append(word)
    return list(groups.values())

Time O(n · k log k) for n words of length up to k (each sort is k log k), space O(n·k).

Approach 2 — character-count tuple as the key (optimal)

Building on Valid Anagram: anagrams share a character-count vector. A 26-length count tuple is a signature you can build in O(k) instead of O(k log k) — no sort.

from collections import defaultdict
 
def groupAnagrams(strs):
    groups = defaultdict(list)
    for word in strs:
        count = [0] * 26
        for ch in word:
            count[ord(ch) - ord("a")] += 1
        groups[tuple(count)].append(word)   # tuple is hashable; list isn't
    return list(groups.values())

Time O(n · k), space O(n·k). Faster asymptotically because the key is built in linear time.

Why tuple, not list

A dict key must be hashable, which in Python means immutable — a list raises TypeError: unhashable type, a tuple doesn’t. This is exactly the hashability constraint from data-type-classification: a mutable key could change after hashing and corrupt the table.

Complexity summary

ApproachTimeSpace
Sorted-string keyO(n·k log k)O(n·k)
Count-tuple keyO(n·k)O(n·k)

Key insight

Grouping = hashing by a canonical key. The skill is designing a signature that’s identical within a group and unique across groups — sorted string or count vector here. defaultdict(list) is the idiomatic “append into buckets” container. This “bucket by a computed key” move recurs whenever a problem says “group / partition these by some equivalence.”

↑ Back to NeetCode 150 — Solved