Big O Practice: Group Anagrams

def group_anagrams(strs):
    groups = {}
    for s in strs:
        key = ''.join(sorted(s))
        groups.setdefault(key, []).append(s)
    return list(groups.values())

Variables

• n - number of strings in the input
• k - maximum length of any single string

Explanation

For each of the `n` strings we sort its characters (**O(k log k)**), giving total time **O(n · k log k)**. The map stores all `n` strings keyed by their sorted form, so total characters held is **O(n · k)**. A counting-array key changes time to O(n · k) but the sort version is canonical.

More Big O practice problems · Today's daily problem