LeetCode Challenge: 49. Group Anagrams - JavaScript Solution 🚀

Top Interview 150

The Group Anagrams problem involves grouping words that are anagrams of each other. Let’s solve LeetCode 49: Group Anagrams step by step.

🚀 Problem Description

Given an array of strings strs, group all strings that are anagrams.

An anagram is a word or phrase formed by rearranging the letters of another. Both strings must have the same characters in the same frequencies.

💡 Examples

Example 1

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

Example 2

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

Example 3

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

🏆 JavaScript Solution

The key idea is to use a hash map to group anagrams. Each anagram has the same sorted character sequence, which we can use as the key.

Implementation

var groupAnagrams = function(strs) { const map = new Map(); for (let str of strs) { const sortedStr = str.split("").sort().join(""); if (!map.has(sortedStr)) { map.set(sortedStr, []); } map.get(sortedStr).push(str); } return Array.from(map.values()); }; 

🔍 How It Works

1. Sort Each String:

   • For each string in strs, sort its characters alphabetically.
   • Use the sorted string as the key in the hash map.

2. Group Strings by Key:

   • If the sorted string is not already a key in the map, add it with an empty array.
   • Append the original string to the array corresponding to the key.

3. Return Groups:

   • Extract the grouped arrays from the map and return them.

🔑 Complexity Analysis

• Time Complexity:

  • Sorting each string: O(m⋅nlogn), where n is the average string length and m is the number of strings.
  • Inserting into the hash map: O(m).
  • Total: O(m⋅nlogn).

• Space Complexity:

  • The hash map stores O(m) keys and values.

📋 Dry Run

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

Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Follow-Up: Faster Grouping Using Character Count

Instead of sorting strings (which costs O(nlogn)), we can use the character count as the key.

Implementation

var groupAnagrams = function(strs) { const map = new Map(); for (let str of strs) { const charCount = Array(26).fill(0); for (let char of str) { charCount[char.charCodeAt(0) - "a".charCodeAt(0)]++; } const key = charCount.join("#"); if (!map.has(key)) { map.set(key, []); } map.get(key).push(str); } return Array.from(map.values()); }; 

Complexity (Character Count Approach)

• Time Complexity: O(m⋅n), where m is the number of strings and n is the average string length.

  • Counting characters is O(n).

• Space Complexity: O(m) for the hash map.

✨ Pro Tips for Interviews

1. Highlight Trade-Offs:

   • Sorting strings is simpler to implement but slower than using character counts.

2. Edge Cases:

   • Empty strings: [""].
   • Single-character strings: ["a", "b", "a"].

📚 Learn More

Check out the full explanation and code walkthrough on my previous Dev.to post:
👉 Valid Anagram - JavaScript Solution

What’s your preferred method to solve this problem? Let’s discuss! 🚀