LeetCode · #49

Group Anagrams Solution

Given an array of strings strs, group the anagrams together. Return the answer in any order.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #49

🏗️

Pattern

Hash Map — canonical key grouping

Given an array of strings strs, group the anagrams together. Two strings are anagrams if they contain the same characters with the same frequencies. You can return the answer in any order.

Example

 Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
// Anagrams share the same sorted form: "aet", "ant", "abt" 

Constraints

 • 1 ≤ strs.length ≤ 10⁴ • 0 ≤ strs[i].length ≤ 100 • strs[i] consists of lowercase English letters  ↑ Bounded alphabet (26 chars) enables frequency-count keys 

Section Two · Approach 1

Brute Force — O(n² · k)

For each string, compare it against every other string to check if they're anagrams (using sorting or frequency count). Group matching strings together. This requires checking all pairs.

Why it works

Exhaustive pairwise comparison guarantees we find all anagram groups. For each ungrouped string, we scan the remaining strings and pull matches into the same group.

Why we can do better

Problem: Pairwise comparison is O(n²) and each comparison costs O(k) for sorting or frequency check. We repeat work — if "eat" matches "tea", and "tea" matches "ate", we've already proved all three belong together. A HashMap with a canonical key groups them in one pass.

Java — Brute Force (sort each, compare pairs)

 import java.util.*;
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
boolean[] used = new boolean[strs.length];
List<List<String>> result = new ArrayList<>();
for (int i = 0; i < strs.length; i++) {
if (used[i]) continue;
List<String> group = new ArrayList<>();
            group.add(strs[i]);
char[] sorted_i = strs[i].toCharArray();
Arrays.sort(sorted_i);
for (int j = i + 1; j < strs.length; j++) {
if (used[j]) continue;
char[] sorted_j = strs[j].toCharArray();
Arrays.sort(sorted_j);
if (Arrays.equals(sorted_i, sorted_j)) {
                    group.add(strs[j]);
                    used[j] = true;
                }
            }
            result.add(group);
        }
return result;
    }
}

Python — Brute Force

 class Solution:
def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        used = [False] * len(strs)
        result = []
for i in range(len(strs)):
if used[i]:
continue
group = [strs[i]]
            key_i = sorted(strs[i])
for j in range(i + 1, len(strs)):
if not used[j] and sorted(strs[j]) == key_i:
                    group.append(strs[j])
                    used[j] = True
result.append(group)
return result

Metric	Value
Time	O(n² · k log k) — sort each string for every pair
Space	O(n · k) — storing groups

Section Three · Approach 2

Sorted-Key HashMap — O(n · k log k)

All anagrams sort to the same string. Use the sorted form as a HashMap key — every string maps to its anagram group in one pass. No pairwise comparison needed.

💡 Mental model: Imagine a mailroom with labeled pigeonholes. Each pigeonhole is labeled with the alphabetically sorted version of a word. When a letter arrives (e.g., "eat"), you rearrange its letters alphabetically ("aet") and drop it into the "aet" pigeonhole. "tea" and "ate" both sort to "aet" — they land in the same slot automatically. At the end, each pigeonhole holds one complete anagram group.

Algorithm — HashMap with sorted key

Step 1: Create a HashMap<String, List<String>>.
Step 2: For each string in the input, sort its characters → this is the canonical key.
Step 3: Add the original string to the list mapped by the key.
Step 4: Return all values from the map as the grouped result.

🎯 When to recognize this pattern:

Any time you need to group items that share a property — think HashMap with a canonical key.
The signal is "partition a collection by equivalence." This pattern appears in LC 49 (sorted string key), LC 249 (shift pattern key), LC 609 (file content key), and anywhere you need grouping by a derived property.

Why sorted key vs frequency key:

Both work. The sorted key is O(k log k) per string but produces a readable string key.
A frequency-count key (e.g., "1#0#0#...#0" encoding letter counts) avoids sorting — O(k) per string — but creates longer keys.
For short strings (k ≤ 100), sorted key is practical and cleaner. For very long strings, frequency key wins.

Section Four · Trace

Visual Walkthrough

Trace through strs = ["eat", "tea", "tan", "ate", "nat", "bat"]:

Sorted-Key HashMap — grouping in one pass

Notice:

Every string is touched exactly once.
The sorted key acts as a fingerprint — all anagrams share the same fingerprint, so they land in the same bucket automatically.
No pairwise comparison needed.

Section Five · Implementation

Code — Java & Python

Java — Sorted-Key HashMap

 import java.util.*;
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars); // canonical form — anagrams sort identically String key = new String(chars);

            map.computeIfAbsent(key, k -> new ArrayList<>())
               .add(s); // group under sorted key
}
return new ArrayList<>(map.values()); // collect all groups
}
}

Python — defaultdict with sorted key

 from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        groups = defaultdict(list)
for s in strs:
            key = tuple(sorted(s)) # tuple is hashable — serves as dict key
groups[key].append(s)
return list(groups.values())

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute Force (pairwise)	O(n² · k log k)	O(n · k)	Redundant comparisons; no canonical key
Sorted Key ← practical optimal	O(n · k log k)	O(n · k)	Clean, readable. Sorting dominates for long strings.
Frequency-Count Key	O(n · k)	O(n · k)	Avoids sort; longer key strings. Better for large k.

Sorted vs Frequency key?:

With k ≤ 100, sorting is fast and the key is compact.
For very long strings (k > 10⁴), a frequency-count key like "3#0#0#1#0#...#1#1#0" avoids the O(k log k) sort — but creates a 52-character key regardless of string length.
In interviews, sorted key is preferred for clarity unless the interviewer specifically asks about optimization.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty string	`[""]`	Empty string sorts to "" — valid key. Group contains one empty string.
Single character	`["a"]`	Minimum non-empty input. Sorted form is itself — group of one.
All anagrams	`["abc","bca","cab"]`	All map to key "abc" — single group returned.
No anagrams	`["abc","def","ghi"]`	Each string has a unique key — n groups of size 1 each.
Duplicate strings	`["a","a","a"]`	Identical strings are trivially anagrams. All land in the same group.
Mixed lengths	`["ab","abc","ba"]`	Different-length strings can never be anagrams — sorted keys will differ in length.

⚠ Common Mistake: Using the original string as the key instead of the sorted form. Another frequent bug: using Arrays.toString(chars) which includes brackets and commas in the key — use new String(chars) instead for a clean sorted-character key in Java.

← Back to Arrays & Hashing problems

LearningTree

LC 49 · Group Anagrams — Solution & Explanation | DSA Guide