> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/hashing/group-anagrams.md).

# Group Anagrams

## Definition

A word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.

## Valid Anagram ([LC.242](https://leetcode.com/problems/valid-anagram/description/))

> Given two strings, determine if they are anagrams.

## Example

```
("anagram", "nagaram") => true
("rat", "car") => false
```

## Approach 1

let N = len(word1) + len(word2)\
Sort then compare O(Nlog(N)) + O(N)

```java
public boolean isAnagram(String word1, String word2) {
    if (word1.length() != word2.length()) {
        return false;
    }
    char[] arr1 = word1.toCharArray();
    char[] arr2 = word2.toCharArray();
    Arrays.sort(arr1);
    Arrays.sort(arr2);
    return Arrays.equals(arr1, arr2);
}
```

## Approach 2

Use a hashtable then count O(N) + O(N)

```java
public boolean isAnagram(String word1, String word2) {
    if (word1.length() != word2.length()) {
        return false;
    }
    int[] countTable = new int[26];
    // count
    for (int i = 0; i < word1.length(); i++) {
        countTable[word1.charAt(i) - 'a']++;
    }
    // decrease
    for (int i = 0; i < word2.length(); i++) {
        countTable[word2.charAt(i) - 'a']--;
    }
    // check
    for (int i = 0; i < 26; i++) {
        if (countTable[i] != 0) return false;
    }
    return true;
}
```

## Group Anagrams ([LC.49](https://leetcode.com/problems/group-anagrams/description/))

> Given an array of words, return a list of lists of anagrams.

## Example

```
I: ["eat", "tea", "tan", "ate", "nat", "bat"]
O: [ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ]
```

## Brute Force Approach

For each word in the list, we try to find its group by checking with the rest of the list. Keep a visited array so we don't visit the word more than once.

```java
public List<List<String>> groupAnagrams(String[] words) {
    List<List<String>> anagramList = new ArrayList<>();
    boolean[] visited = new boolean[words.length];
    // check null
    if (words == null || words.length == 0) {
        return anagramList;
    }
    // search all word in words
    for (int i = 0; i < words.length; i++) {
        List<String> group = new ArrayList<>();
        if (visited[i]) {
            continue;
        }
        visited[i] = true;
        group.add(words[i]);
        for (int j = i + 1; j < words.length; j++) {
            if (visited[j]) {
                continue;
            }
            if (isAnagram(words[i], words[j])) {
                group.add(words[j]);
                visited[j] = true;
            }
        }
        anagramList.add(group);
    }
    return anagramList;
}
```

Let N be the number of words, K be the maximum length of a word.\
The time complexity is O(N) (outer loop) \* O(N) (inner loop worst case compare against the rest) \* O(2K) (hashtable + compare) = O(KN^2). This will pass `100 / 101 test cases` on LC. How can we do better?

## Sorting and Hashing

We can optimized to the inner loop to O(K) by hashing the sorted word. If the hashmap contains the word then we add it to the result list. If not, we want to put (sortedWord, sortedWord) to the map.

```java
public List<List<String>> groupAnagrams(String[] words) {
    List<List<String>> groups = new ArrayList<>();
    if (words == null || words.length == 0) {
        return groups;
    }
    Map<String, List<String>> hashmap = new HashMap<>();
    for (String word : words) {
        char[] arr = word.toCharArray();
        Arrays.sort(arr);
        String key = String.valueOf(arr);
        // O(K) instead of inner loop
        if (hashmap.containsKey(key)) {
            hashmap.get(key).add(word);
        } else {
            hashmap.put(key, new ArrayList<String>());
            hashmap.get(key).add(word);
        }
    }
    for (String key : hashmap.keySet()) {
        groups.add(hashmap.get(key));
    }
    return groups;
}
```

```python
# brute force 

# map[key] => value 

# key = sorted str, value is the list of acutal words 

# in the end return all the values 


def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    
    n = len(strs)
    
    results = []
    
    if n == 0:
        return results
    
    # change this list to a set if dup is an issue  
    stem_dict: Dict[str, List[str]] = {}
    
    for word in strs:
        # sorted() returns a copy 
        # list.sort() modifies in place 
        stem = ''.join(sorted(word))
        
        if stem in stem_dict:
            stem_dict[stem].append(word)
        else:
            stem_dict[stem] = [word]
        
    
    return stem_dict.values()
```

Time complexity O(NKlogK) Space complexity O(NK)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-1/basic_data_structure/hashing/group-anagrams.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.