Group Anagrams

Jun 19, 2025

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

Note: Anagram is a word or phrase formed by rearranging the letters of another word or phrase.

Input: 
· ["eat","tan","nat"]
Output: 
· [["eat"],["nat","tan"]]

Input: 
· ["eat","tan","bat"]
Output: 
· [["eat"],["tan"],["bat"]]

🟡 Approach 1: Brute Force

Logic:
- Sort each string’s characters
- Use sorted strings as keys in a map
- Group original strings by their keys
Time Complexity:
- O(n · k log k)
- Sorting one string takes O(k log k)
- Sorting n strings takes O(n · k log k)
Space Complexity:
- O(n·k)
- Storing one string uses O(k) space
- Storing n strings takes O(n·k) space

🟢 Approach 2: Use Count Arrays (Optimal)

Idea:
- Sorting each string takes time
- But we don’t need to sort
- We can use a fixed-size char count array as the key
- This reduces time from O(k log k) to O(k)
Logic:
- Create an empty map
- For each string:
  - Count chars in a fixed-size array
  - Convert count array to a tuple key
  - Add original string to map[key]
- This way, we group all strings with the same key
- Return all grouped strings from the map
Time Complexity:
- O(n·k)
- Creating a key for each string is O(k)
- Grouping and storing it in a map is O(1)
- Doing this for n strings is O(n·k)
Space Complexity:
- O(n·k)
- Storing counts for one string is O(k)
- Total space for n strings is O(n · k)

What if you can’t use an array?
- Use a map for counts.
- We still get a O(n·k) solution.
What if case doesn’t matter?
- Convert all strings to lowercase first.
- Then run the same grouping logic.
What if input contains Unicode?
- We can’t use fixed-size count arrays as keys.
- Instead, use a map to count chars for each string.
- Big O complexity stays similar overall.
- But key creation may be slower.
- And each key may use more space.

Harpreet's Newsletter