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

Example 1:

• Input: strs = ["eat","tea","tan","ate","nat","bat"]
• Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

• Input: strs = [""]
• Output: [[""]]

Constraints:

• 1 ≤ strs.length ≤ 10⁴
• 0 ≤ strs[i].length ≤ 100
• strs[i] consists of lowercase English letters only

Group Anagrams builds on Valid Anagram by using a canonical signature (sorted string) as a hash map key to bucket similar strings together.

Pattern: Canonical Key Hashing

When grouping items that are equivalent under some transformation, map each item to a canonical form and use it as a hash map key.

graph TD
    Start["Input Data"] --> Process["Process Element by Element"]
    Process --> Lookup{"Hash Map / Set Lookup"}
    Lookup -- "Match Found" --> Return["Return Indices / Result"]
    Lookup -- "No Match" --> Store["Store in Map / Set"]
    Store --> Process

function groupAnagrams(strs) {
  const groups = [];
  const used = new Array(strs.length).fill(false);
  for (let i = 0; i < strs.length; i++) {
    if (used[i]) continue;
    const group = [strs[i]];
    used[i] = true;
    for (let j = i + 1; j < strs.length; j++) {
      if (!used[j] && [...strs[i]].sort().join('') === [...strs[j]].sort().join('')) {
        group.push(strs[j]);
        used[j] = true;
      }
    }
    groups.push(group);
  }
  return groups;
}

• Time Complexity: O(n² k log k)
• Space Complexity: O(n k)
• Explanation: Compare every pair of strings by their sorted form.

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

• Time Complexity: O(n k log k)
• Space Complexity: O(n k)
• Explanation: Hash map keyed by sorted string signature.

1. Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
2. Iterate & Evaluate: Process the input according to the boundary conditions.
3. Update & Return: Compute the optimal answer and return early or at termination.

1. Recognize anagrams share a sorted form
2. Use the sorted string as a hash map key
3. Explain the O(n k log k) cost of sorting each string
4. Mention the 26-count array as a faster key alternative

1. Two strings are anagrams if their sorted forms match.
2. Use the sorted string as a hash map key.
3. Group original strings under their canonical key.

👉 Solve this problem interactively in the DSA Lab