Coding interview problems › Arrays & Hashing

#️⃣ Arrays & Hashing Medium

Group Anagrams

Group Anagrams explained: give every word a canonical key (sorted letters or a count tuple) and bucket by it in a hash map. Tested Python and a live visual.

Also searched as: group words that are anagrams · anagram grouping hash map

#️⃣

Try it live Free

Hash Tables

Insert keys and watch the hash send equal keys to the same bucket. Here the key is the word's letter signature, so every anagram drops into one shared bucket.

Open the playground →

The problem

Given a list of lowercase words, group together the words that are anagrams of each other. Return the groups in any order.

Input["eat", "tea", "tan", "ate", "nat", "bat"]
Output[["eat","tea","ate"], ["tan","nat"], ["bat"]]

Group order and word order inside a group do not matter.

The key insight

All anagrams share a signature: the same letters with the same counts. If you turn each word into that signature, anagrams collide on the same key, and a hash map from key to list does the grouping for you. Sorting the word gives a simple key; a 26-number count tuple gives a faster one.

Brute force first: Comparing every pair of words with an anagram check is O(n² · L) and still needs extra work to form groups.

Step-by-step approach

  1. Create a dictionary from signature to list of words.
  2. For each word, build its signature, for example tuple(sorted(word)) or a tuple of 26 letter counts.
  3. Append the word to groups[signature].
  4. Return the dictionary's values as a list.

Python solution

PYTHON 3tested
from collections import defaultdict


def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        count = [0] * 26                   # signature: letter counts
        for ch in w:
            count[ord(ch) - ord("a")] += 1
        groups[tuple(count)].append(w)
    return list(groups.values())

Complexity

TimeO(n · L)
SpaceO(n · L)

Each of the n words of length up to L is scanned once to build its count key. Using sorted(word) as the key instead costs O(n · L log L).

Common mistakes

Frequently asked questions

What is the time and space complexity of Group Anagrams?

With a 26-count key it is O(n · L) time, where L is the longest word. With sorted-letter keys it is O(n · L log L). Space is O(n · L) to store the groups.

Which key is better, sorted string or count tuple?

Sorted strings are shorter to write and fine for short words. The count tuple avoids the log factor and is better when words are long.

Does the order of groups matter?

Usually not. If a fixed order is required, sort each group and then sort the list of groups.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Arrays & Hashing Hash Tables lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.