Course4all

Group Anagrams

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Arrays & Hashing.

Group Anagrams

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.

Visual Representation

Input: ["eat", "tea", "tan", "ate", "nat", "bat"] 1. Sort each string to create a 'key': "eat" -> "aet" "tea" -> "aet" "tan" -> "ant" ... 2. Group by key in a Hash Map: "aet" -> ["eat", "tea", "ate"] "ant" -> ["tan", "nat"] "abt" -> ["bat"]
Medium

Examples

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
"eat", "tea", and "ate" are anagrams. "tan" and "nat" are anagrams. "bat" is alone.
Approach 1

Level I: Brute Force (Compare All Pairs)

Intuition

Compare every string with every other string to check if they are anagrams. We use a used boolean array to keep track of strings that have already been grouped. This is the simplest baseline approach but inefficient for large inputs.
⏱ O(N² * K log K) where N is the number of strings and K is the average length of strings (due to sorting for comparison).💾 O(N * K) to store the result.

Detailed Dry Run

String AString BSorted(A)Sorted(B)Is Anagram?
"eat""tea""aet""aet"Yes
"eat""tan""aet""ant"No
"tan""nat""ant""ant"Yes
java
import java.util.*;

public class Main {
    public static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        boolean[] used = new boolean[strs.length];
        for (int i = 0; i < strs.length; i++) {
            if (used[i]) continue;
            List<String> group = new ArrayList<>();
            group.add(strs[i]);
            used[i] = true;
            for (int j = i + 1; j < strs.length; j++) {
                if (!used[j] && areAnagrams(strs[i], strs[j])) {
                    group.add(strs[j]);
                    used[j] = true;
                }
            }
            res.add(group);
        }
        return res;
    }

    private static boolean areAnagrams(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        return Arrays.equals(c1, c2);
    }

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

Level II: Better Solution (HashMap with Sorted String Key)

Intuition

Instead of nested loops, we use a Hash Map. Since all anagrams share the same sorted version, we sort each string and use it as a key. All strings that result in the same sorted string are added to the same list.
⏱ O(N * K log K) where N is the number of strings and K is the maximum length of a string.💾 O(N * K) to store the Hash Map.

Detailed Dry Run

Input StringSorted KeyAction
"eat""aet"Map["aet"] = ["eat"]
"tea""aet"Map["aet"] = ["eat", "tea"]
"tan""ant"Map["ant"] = ["tan"]
java
import java.util.*;

public class Main {
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            String key = String.valueOf(ca);
            if (!map.containsKey(key)) map.put(key, new ArrayList<>());
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }

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

Level III: Optimal Solution (Frequency Bucket Key)

Intuition

Instead of sorting each string (O(Klog⁡K)O(K \log K)), we can use the character frequencies (26 characters) as the Hash Map key. This reduces the transformation time to linear O(K)O(K). We represent the count array as a string or tuple to use as a key.
⏱ O(N * K) where N is the number of strings and K is the maximum length of a string.💾 O(N * K) to store the Hash Map and count strings.

Detailed Dry Run

Bucket Count Key

CharFrequency Count Array
eat[1, 0, 0, 0, 1, ..., 1, ...] (a:1, e:1, t:1)
tea[1, 0, 0, 0, 1, ..., 1, ...] (same signature)
Logic: key = "#1#0#0...#1". Anagrams share the same key without ever sorting.
java
import java.util.*;

public class Main {
    public static List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) count[c - 'a']++;
            
            StringBuilder sb = new StringBuilder("");
            for (int i = 0; i < 26; i++) {
                sb.append('#');
                sb.append(count[i]);
            }
            String key = sb.toString();
            if (!map.containsKey(key)) map.put(key, new ArrayList<>());
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }

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

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionContains Duplicate
Next Question →Longest Consecutive Sequence