Group Anagrams

🎯

Group Anagrams

mediumHASH_MAPAmazonFacebookGoogle

Imagine you have a large list of words and want to organize them so that all words that are anagrams of each other are grouped together, making it easier to find related words quickly.

💡 This problem is about grouping strings that contain the same characters in different orders. Beginners often struggle because they don't immediately see how to efficiently identify anagrams without comparing every pair of strings.

📋

Problem Statement

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. Input: strs, an array of strings. Output: A list of lists of strings, where each sublist contains strings that are anagrams of each other.

1 ≤ strs.length ≤ 10^50 ≤ strs[i].length ≤ 100strs[i] consists of lowercase English letters.

💡

Example

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

Outputeatteaatetannatbat

The words 'eat', 'tea', and 'ate' are anagrams of each other, as are 'tan' and 'nat'. 'bat' has no anagram in the list.

• Empty input array → returns empty list
• All strings are empty → groups all empty strings together
• No anagrams present → each string forms its own group
• Very large input with many duplicates → groups correctly without performance issues

⚠️

Common Mistakes

Using sorted string as key but forgetting to join characters

Key becomes a list or array, causing hash map errors or wrong grouping

✅ Convert sorted characters back to a string before using as key

Not handling empty strings correctly

Empty strings may be grouped incorrectly or cause errors

✅ Ensure empty strings produce a valid key (empty string or zero count array)

Using nested loops to compare strings instead of hashing

Solution is too slow and times out on large inputs

✅ Use hash map with sorted or frequency keys to achieve linear time grouping

Using character frequency array as key without separators

Different frequency arrays produce same string key, causing wrong grouping

✅ Add separators (like '#') between counts to ensure unique keys

Modifying input strings in-place without copying

Original data is corrupted, causing incorrect output or bugs

✅ Always work on copies when sorting or modifying strings

🧠

Brute Force (Compare Every Pair)

💡 This approach exists to establish a baseline understanding by directly comparing strings to find anagrams, even though it is inefficient. It helps beginners grasp the problem's nature before optimizing.

Intuition

Check every pair of strings to see if they are anagrams by comparing their sorted forms or character counts, then group them accordingly.

Algorithm

1. Initialize an empty list to hold groups of anagrams.
2. For each string in the input list, check if it is an anagram of any existing group by comparing with each group's representative string.
3. If it matches, add it to that group; otherwise, create a new group with this string.
4. Return the list of groups after processing all strings.

💡 This algorithm is straightforward but involves many repeated comparisons, making it slow for large inputs.

</>

Code

def groupAnagrams(strs):
    groups = []
    for s in strs:
        found = False
        for group in groups:
            if sorted(s) == sorted(group[0]):
                group.append(s)
                found = True
                break
        if not found:
            groups.append([s])
    return groups

# Driver code
if __name__ == '__main__':
    input_list = ["eat", "tea", "tan", "ate", "nat", "bat"]
    print(groupAnagrams(input_list))

Line Notes

groups = []Initialize the list to store groups of anagrams

for s in strs:Iterate over each string to place it in a group

for group in groups:Check each existing group to find a matching anagram group

if sorted(s) == sorted(group[0]):Compare sorted characters to detect anagrams

group.append(s)Add string to the matching group

if not found:If no group matched, create a new group with this string

import java.util.*;
public class GroupAnagrams {
    public static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> groups = new ArrayList<>();
        for (String s : strs) {
            boolean found = false;
            for (List<String> group : groups) {
                if (isAnagram(s, group.get(0))) {
                    group.add(s);
                    found = true;
                    break;
                }
            }
            if (!found) {
                List<String> newGroup = new ArrayList<>();
                newGroup.add(s);
                groups.add(newGroup);
            }
        }
        return groups;
    }

    private static boolean isAnagram(String s1, String s2) {
        char[] a1 = s1.toCharArray();
        char[] a2 = s2.toCharArray();
        Arrays.sort(a1);
        Arrays.sort(a2);
        return Arrays.equals(a1, a2);
    }

    public static void main(String[] args) {
        String[] input = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(groupAnagrams(input));
    }
}

Line Notes

List<List<String>> groups = new ArrayList<>();Initialize list to hold groups

for (String s : strs)Iterate over each string

for (List<String> group : groups)Check existing groups for anagram match

if (isAnagram(s, group.get(0)))Compare current string with group's first string

group.add(s);Add string to matched group

if (!found)Create new group if no match found

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

bool isAnagram(const string& s1, const string& s2) {
    string a1 = s1, a2 = s2;
    sort(a1.begin(), a1.end());
    sort(a2.begin(), a2.end());
    return a1 == a2;
}

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> groups;
    for (const string& s : strs) {
        bool found = false;
        for (auto& group : groups) {
            if (isAnagram(s, group[0])) {
                group.push_back(s);
                found = true;
                break;
            }
        }
        if (!found) {
            groups.push_back({s});
        }
    }
    return groups;
}

int main() {
    vector<string> input = {"eat", "tea", "tan", "ate", "nat", "bat"};
    vector<vector<string>> result = groupAnagrams(input);
    for (auto& group : result) {
        for (auto& word : group) {
            cout << word << " ";
        }
        cout << endl;
    }
    return 0;
}

Line Notes

vector<vector<string>> groups;Initialize groups container

for (const string& s : strs)Iterate over each string

for (auto& group : groups)Check each existing group for anagram match

if (isAnagram(s, group[0]))Compare current string with group's first string

group.push_back(s);Add string to matched group

if (!found)Create new group if no match found

function isAnagram(s1, s2) {
    return s1.split('').sort().join('') === s2.split('').sort().join('');
}

function groupAnagrams(strs) {
    const groups = [];
    for (const s of strs) {
        let found = false;
        for (const group of groups) {
            if (isAnagram(s, group[0])) {
                group.push(s);
                found = true;
                break;
            }
        }
        if (!found) {
            groups.push([s]);
        }
    }
    return groups;
}

// Test
const input = ["eat", "tea", "tan", "ate", "nat", "bat"];
console.log(groupAnagrams(input));

Line Notes

const groups = [];Initialize array to hold groups

for (const s of strs)Iterate over each string

for (const group of groups)Check existing groups for anagram match

if (isAnagram(s, group[0]))Compare current string with group's first string

group.push(s);Add string to matched group

if (!found)Create new group if no match found

⏱

Complexity

TimeO(n^2 * k log k)

SpaceO(n * k)

For each of the n strings, we compare with up to n groups. Each comparison sorts strings of length k, costing k log k. Hence O(n^2 * k log k). Space stores all strings.

💡 If n=1000 and k=10, this means about 1,000,000 comparisons each sorting 10 characters, which is very slow.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand the problem before optimizing.

🧠

Sorting Each String as Key (Hash Map)

💡 This approach improves efficiency by using a hash map keyed by the sorted version of each string, grouping anagrams together in linear time relative to input size.

Intuition

Sort each string to create a canonical form that is identical for all anagrams, then group strings by this key in a hash map.

Algorithm

1. Initialize an empty hash map where keys are sorted strings and values are lists of anagrams.
2. For each string in the input, sort its characters to form the key.
3. Add the original string to the list corresponding to this key in the hash map.
4. Return all the grouped lists from the hash map.

💡 This algorithm leverages sorting to create a unique key for each anagram group, making grouping straightforward and efficient.

</>

Code

from collections import defaultdict

def groupAnagrams(strs):
    anagram_map = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))
        anagram_map[key].append(s)
    return list(anagram_map.values())

# Driver code
if __name__ == '__main__':
    input_list = ["eat", "tea", "tan", "ate", "nat", "bat"]
    print(groupAnagrams(input_list))

Line Notes

from collections import defaultdictUse defaultdict to simplify map initialization

anagram_map = defaultdict(list)Create map to group anagrams by sorted key

for s in strs:Process each string in input

key = ''.join(sorted(s))Sort string to create canonical key

anagram_map[key].append(s)Add string to its anagram group

return list(anagram_map.values())Return all grouped anagrams

import java.util.*;
public class GroupAnagrams {
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> anagramMap = new HashMap<>();
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            anagramMap.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(anagramMap.values());
    }

    public static void main(String[] args) {
        String[] input = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(groupAnagrams(input));
    }
}

Line Notes

Map<String, List<String>> anagramMap = new HashMap<>();Initialize map to group anagrams

for (String s : strs)Iterate over each string

char[] chars = s.toCharArray();Convert string to char array for sorting

Arrays.sort(chars);Sort characters to form key

anagramMap.computeIfAbsent(key, k -> new ArrayList<>()).add(s);Add string to group keyed by sorted string

return new ArrayList<>(anagramMap.values());Return all groups as list

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> anagramMap;
    for (string& s : strs) {
        string key = s;
        sort(key.begin(), key.end());
        anagramMap[key].push_back(s);
    }
    vector<vector<string>> result;
    for (auto& p : anagramMap) {
        result.push_back(move(p.second));
    }
    return result;
}

int main() {
    vector<string> input = {"eat", "tea", "tan", "ate", "nat", "bat"};
    vector<vector<string>> result = groupAnagrams(input);
    for (auto& group : result) {
        for (auto& word : group) {
            cout << word << " ";
        }
        cout << endl;
    }
    return 0;
}

Line Notes

unordered_map<string, vector<string>> anagramMap;Map keys are sorted strings, values are groups

for (string& s : strs)Iterate over each string

string key = s;Copy string to sort for key

sort(key.begin(), key.end());Sort characters to create key

anagramMap[key].push_back(s);Add original string to group

for (auto& p : anagramMap)Collect all groups into result vector

function groupAnagrams(strs) {
    const anagramMap = new Map();
    for (const s of strs) {
        const key = s.split('').sort().join('');
        if (!anagramMap.has(key)) {
            anagramMap.set(key, []);
        }
        anagramMap.get(key).push(s);
    }
    return Array.from(anagramMap.values());
}

// Test
const input = ["eat", "tea", "tan", "ate", "nat", "bat"];
console.log(groupAnagrams(input));

Line Notes

const anagramMap = new Map();Initialize map to group anagrams

for (const s of strs)Iterate over each string

const key = s.split('').sort().join('');Sort string characters to form key

if (!anagramMap.has(key))Create new group if key not present

anagramMap.get(key).push(s);Add string to its group

return Array.from(anagramMap.values());Return all groups as array

⏱

Complexity

TimeO(n * k log k)

SpaceO(n * k)

Sorting each string of length k costs k log k, done for n strings. Hash map insertions and lookups are average O(1).

💡 For n=1000 and k=10, this means about 10,000 operations sorting plus fast grouping, which is efficient.

Interview Verdict: Accepted / Standard approach

This approach is efficient and commonly accepted in interviews for grouping anagrams.

🧠

Counting Characters as Key (Frequency Map)

💡 This approach avoids sorting by using character frequency counts as keys, which can be faster for longer strings with limited character sets.

Intuition

Represent each string by a 26-length array counting each letter's frequency, then use this frequency array as a key to group anagrams.

Algorithm

1. Initialize a hash map where keys are frequency count tuples and values are lists of strings.
2. For each string, count the frequency of each character (a-z).
3. Convert the frequency array to a tuple or string to use as a hash map key.
4. Add the original string to the list corresponding to this key.
5. Return all grouped lists from the hash map.

💡 This algorithm uses character counts to uniquely identify anagram groups without sorting, improving performance for long strings.

</>

Code

from collections import defaultdict

def groupAnagrams(strs):
    anagram_map = defaultdict(list)
    for s in strs:
        count = [0]*26
        for ch in s:
            count[ord(ch) - ord('a')] += 1
        key = tuple(count)
        anagram_map[key].append(s)
    return list(anagram_map.values())

# Driver code
if __name__ == '__main__':
    input_list = ["eat", "tea", "tan", "ate", "nat", "bat"]
    print(groupAnagrams(input_list))

Line Notes

count = [0]*26Initialize frequency array for 26 letters

for ch in s:Count each character's frequency

key = tuple(count)Convert frequency list to immutable tuple for hashing

anagram_map[key].append(s)Group string by frequency key

return list(anagram_map.values())Return all grouped anagrams

import java.util.*;
public class GroupAnagrams {
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> anagramMap = new HashMap<>();
        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            StringBuilder keyBuilder = new StringBuilder();
            for (int num : count) {
                keyBuilder.append('#');
                keyBuilder.append(num);
            }
            String key = keyBuilder.toString();
            anagramMap.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(anagramMap.values());
    }

    public static void main(String[] args) {
        String[] input = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(groupAnagrams(input));
    }
}

Line Notes

int[] count = new int[26];Frequency array for letters a-z

for (char c : s.toCharArray())Count characters in string

keyBuilder.append('#'); keyBuilder.append(num);Build unique string key from counts

anagramMap.computeIfAbsent(key, k -> new ArrayList<>()).add(s);Group string by frequency key

return new ArrayList<>(anagramMap.values());Return all groups

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> anagramMap;
    for (string& s : strs) {
        int count[26] = {0};
        for (char c : s) {
            count[c - 'a']++;
        }
        string key;
        for (int i = 0; i < 26; i++) {
            key += '#';
            key += to_string(count[i]);
        }
        anagramMap[key].push_back(s);
    }
    vector<vector<string>> result;
    for (auto& p : anagramMap) {
        result.push_back(move(p.second));
    }
    return result;
}

int main() {
    vector<string> input = {"eat", "tea", "tan", "ate", "nat", "bat"};
    vector<vector<string>> result = groupAnagrams(input);
    for (auto& group : result) {
        for (auto& word : group) {
            cout << word << " ";
        }
        cout << endl;
    }
    return 0;
}

Line Notes

int count[26] = {0};Initialize frequency array for letters

for (char c : s)Count frequency of each character

string key; for (int i = 0; i < 26; i++)Build string key from counts with separators

anagramMap[key].push_back(s);Group string by frequency key

for (auto& p : anagramMap)Collect groups into result vector

function groupAnagrams(strs) {
    const anagramMap = new Map();
    for (const s of strs) {
        const count = new Array(26).fill(0);
        for (const ch of s) {
            count[ch.charCodeAt(0) - 97]++;
        }
        const key = count.join('#');
        if (!anagramMap.has(key)) {
            anagramMap.set(key, []);
        }
        anagramMap.get(key).push(s);
    }
    return Array.from(anagramMap.values());
}

// Test
const input = ["eat", "tea", "tan", "ate", "nat", "bat"];
console.log(groupAnagrams(input));

Line Notes

const count = new Array(26).fill(0);Initialize frequency array for letters

for (const ch of s)Count each character's frequency

const key = count.join('#');Create unique key by joining counts with separator

if (!anagramMap.has(key))Create new group if key not present

anagramMap.get(key).push(s);Add string to its group

return Array.from(anagramMap.values());Return all groups

⏱

Complexity

TimeO(n * k)

SpaceO(n * k)

Counting characters for each string costs O(k), done for n strings. Hash map operations are average O(1).

💡 For n=1000 and k=10, this means about 10,000 operations, faster than sorting for longer strings.

Interview Verdict: Accepted / Optimal for large strings

This approach is optimal when strings are long but character set is small, avoiding sorting overhead.

📊

All Approaches - One-Glance Tradeoffs

💡 The sorting-based hash map approach is the best balance of simplicity and efficiency, and is what you should code in 95% of interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2 * k log k)	O(n * k)	No	Yes	Mention only - never code
2. Sorting Each String as Key	O(n * k log k)	O(n * k)	No	Yes	Code this approach
3. Counting Characters as Key	O(n * k)	O(n * k)	No	Yes	Mention as optimization for large strings

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to grasp the problem, then move to efficient hashing approaches. Practice coding and explaining each step clearly.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach and its inefficiencies.Step 3: Introduce the sorting-based hash map solution.Step 4: Discuss the character count optimization for large strings.Step 5: Code the chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to identify anagrams efficiently, use hash maps correctly, and optimize for time and space. Clear communication and handling edge cases are critical.

Common Follow-ups

• How would you handle Unicode or extended character sets? → Use a larger frequency array or a map for counts.
• Can you optimize space usage? → Use in-place sorting or compress keys.

💡 These follow-ups test your adaptability to variations and deeper understanding of hashing and string manipulation.

🔍

Pattern Recognition

When to Use

1) Need to group strings by character composition, 2) Anagrams or permutations involved, 3) Hash map or frequency counting is applicable, 4) Sorting or counting can create canonical keys.

Signature Phrases

group the anagramsrearranging the letterssame characters exactly once

NOT This Pattern When

Sorting arrays or grouping by numeric values is different; this pattern specifically involves grouping strings by character composition.

Similar Problems

Group Shifted Strings - groups strings by shifting patternLongest Palindromic Substring - uses character frequency conceptsValid Anagram - checks if two strings are anagrams

Practice

1. Consider the following code snippet implementing the optimal approach for longest consecutive sequence. What is the value of max_len returned when the input is [1, 9, 3, 10, 2]?

easy

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Identify sequence starts

   Numbers are {1,2,3,9,10}. Sequence starts are numbers where num-1 not in set: 1 and 9.

2. Step 2: Count consecutive lengths

   From 1: sequence is 1,2,3 -> length 3. From 9: sequence is 9,10 -> length 2. Max length is 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Longest consecutive sequence is [1,2,3] length 3 [OK]

Hint: Only count sequences starting at numbers without predecessor [OK]

Common Mistakes:

• Counting sequences from every number causing duplicates
• Off-by-one errors in length counting
• Confusing max length with total unique numbers

2. The following code attempts to find the longest contiguous subarray with equal number of 0s and 1s. Which line contains a subtle bug that can cause incorrect results on some inputs?

def findMaxLength(nums):
    prefix_sum = 0
    seen = {}
    max_length = 0
    for i, num in enumerate(nums):
        prefix_sum += 1 if num == 1 else -1
        if prefix_sum in seen:
            max_length = max(max_length, i - seen[prefix_sum])
        else:
            seen[prefix_sum] = i
    return max_length

medium

A. Line 3: Not initializing seen with {0: -1}

B. Line 6: Incorrect prefix_sum update logic

C. Line 8: Using max instead of min for max_length update

D. Line 10: Returning max_length instead of prefix_sum

Solution

1. Step 1: Check initialization of seen map

   Seen should start with {0: -1} to handle subarrays starting at index 0.

2. Step 2: Consequence of missing initialization

   Without {0: -1}, subarrays starting at index 0 with equal 0s and 1s are missed, causing incorrect max_length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing initial entry causes missed subarrays at start [OK]

Hint: Always initialize seen with sum 0 at index -1 [OK]

Common Mistakes:

• Forgetting initial seen entry
• Incorrect prefix sum update
• Wrong max_length update logic

3. What is the time complexity of the optimal Happy Number detection algorithm that uses a known set of unhappy cycle numbers and repeatedly computes the sum of squares of digits until termination?

medium

A. O(n) where n is the input number

B. O(k * n) where k is iterations and n is the number of digits

C. O(log n) because each iteration reduces the number size drastically

D. O(k * log n) where k is the number of iterations until 1 or cycle

Solution

1. Step 1: Identify cost per iteration

   Each iteration computes sum of squares of digits, which takes O(log n) time since number of digits is proportional to log n.

2. Step 2: Count iterations until termination

   There are k iterations until number reaches 1 or cycle; total time is O(k * log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Time depends on iterations and digit count, not linear in n [OK]

Hint: Sum of squares per iteration costs O(log n) [OK]

Common Mistakes:

• Confusing input size n with number of digits
• Assuming linear O(n) time

4. What is the time complexity of the optimal bucket sort approach for finding the top k frequent elements in an array of size n with u unique elements?

medium

A. O(n + u) since building frequency map and buckets takes linear time

B. O(n log n) due to sorting the frequency map keys

C. O(u * log u) because sorting unique elements is required

D. O(n) because frequency counting and bucket filling are linear in n

Solution

1. Step 1: Analyze frequency counting

   Counting frequencies requires iterating over n elements -> O(n)

2. Step 2: Analyze bucket filling and result collection

   Filling buckets and collecting top k elements is O(n) since total frequencies sum to n, plus O(u) for iterating unique elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Complexity is O(n + u), which is linear since u ≤ n [OK]

Hint: Frequency counting + bucket filling is linear [OK]

Common Mistakes:

• Assuming sorting unique keys is needed
• Confusing n with u in complexity
• Ignoring that bucket iteration is linear in total elements

5. Suppose the problem is modified so that the array can contain negative numbers and k can be zero. Which modification to the prefix sum + hash map approach correctly handles this variant?

hard

A. Use prefix sums without modulo and store sums in a hash map to detect repeated sums for k=0

B. Normalize k to positive and use modulo as usual, ignoring zero k case

C. Skip modulo operations entirely and check if any subarray sum equals zero when k=0

D. Replace hash map with a balanced tree to handle negative sums and zero k

Solution

1. Step 1: Understand that modulo by zero is undefined

   When k=0, modulo operations cannot be used; must check sums equal zero directly.

2. Step 2: Use prefix sums and hash map of sums (not modulo) to detect repeated sums indicating zero-sum subarray

   This approach correctly handles negative numbers and zero k.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Detect repeated prefix sums for zero k to find zero-sum subarrays [OK]

Hint: For k=0, detect repeated prefix sums without modulo [OK]

Common Mistakes:

• Applying modulo when k=0 causing errors
• Ignoring negative numbers in modulo computations
• Using data structures that don't support negative sums efficiently