1. Understand the problem

• Input: We are given an array of strings strs.

• Task: We need to group all the anagrams together — words that have the same letters and same frequency, just rearranged.

• Output: Return a list of groups.

• Example: [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”] → [[“eat”,”tea”,”ate”],[“tan”,”nat”],[“bat”]].

2. Ask clarify questions

• Are all strings lowercase English letters?

• Can there be empty strings or duplicates?

• Should the order of groups or words inside groups matter?

• What’s the expected time complexity (O(n log n) or O(n * k)) where k is average word length?

3. Work through examples

Example 1: [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”] → [[“eat”,”tea”,”ate”],[“tan”,”nat”],[“bat”]]

Example 2: [””] → [[””]]

Example 3: [“a”] → [[“a”]]

4. Brainstorm 2–3 solutions

1. Naive (O(n² * k)):

• Compare each pair of strings by sorting or counting characters — inefficient.

1. Optimized (O(n * k log k)):

• Sort each string; use the sorted string as a key in a dictionary.

• Example: “eat” → “aet” → group by this key.

1. Most optimized (O(n * k)):

• Use character count (array of size 26) as a hashable tuple key → avoids sorting.

5. Implement solution

5.1. Sorting

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = defaultdict(list)
        for s in strs:
            sortedS = ''.join(sorted(s))
            res[sortedS].append(s)
        return list(res.values())

• Time complexity: O(m * nlogn).

• Space complexity: O(m * n).

5.2. Hash Table

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = defaultdict(list)
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            res[tuple(count)].append(s)
        return list(res.values())

• Time complexity: O(m * n).

• Space complexity: O(m * n).