[BLOG] Untitled Post

untitled-post.md

title	location	images	tags	privacy	createdAt
Untitled Post	19.2283, 72.9481		blog quick-post	public	2025-12-29 15:41:49 UTC

USER: saare ke saare soltion dede iska from brtute to better to wired to best and ek mind mapp dede i want ever soltion if it is not incrementall and a soltion of diferent kind then also

ASSISTANT: ### Interview Dry Run (Hinglish Style)

Scenario: Aap interviewer ke saamne baithe ho. Input array hai: ["act","pots","tops","cat","stop","hat"].

Interviewer: "Bhai, isko group kaise karega?"

You: "Sir, dekho simple hai. Anagrams ka matlab kya hai? Characters wahi hain, bas order alag hai. Agar main act ko sort karun toh wo act banega. Agar main cat ko sort karun toh wo bhi act banega!

Toh dimag mein ek idea aata hai:

1. Har word ko uthao.
2. Uska ek 'Signature' banao (ya toh sort karke ya count karke).
3. Jis-jis ka signature same hai, unko ek baalti (bucket) mein daal do.

Example dekhte hain:

• act -> Signature: act | Bucket: {"act": ["act"]}
• pots -> Signature: opst | Bucket: {"act": ["act"], "opst": ["pots"]}
• tops -> Signature: opst | Bucket: {"act": ["act"], "opst": ["pots", "tops"]}
• cat -> Signature: act | Bucket: {"act": ["act", "cat"], "opst": ["pots", "tops"]}

Last mein saari baaltiyan return kar do! Simple na?"

---

The Systematic Breakdown (Process)

1. Identify the "Group Criteria": Do strings belong together? Use a Hash Map where Key = Signature and Value = List of strings.
2. Generate Signature:
   • Brute: Compare every word with every other word using a boolean "visited" array ($O(N^2)$).
   • Better: Sort the string to get the key ($O(N \cdot K \log K)$).
   • Best: Count the frequencies of 'a-z' to get the key ($O(N \cdot K)$).

---

Solutions (Brute to Wired to Best)

1. Brute Force (Nested Loops - No Map)

Yaha hum ek empty results list rakhte hain aur har word ke liye check karte hain ki kya ye pehle kisi group mein ja chuka hai. Complexity: $O(N^2 \cdot K \log K)$

// Logic: Do nested loops. If anagram found and not visited, add to a temp list.
// Generally avoid in interviews unless asked for absolute basic.

2. The "Better" Solution (Sorting as Key)

Commonly used. Most intuitive. Time: $O(N \cdot K \log K)$ where $N$ is number of strings, $K$ is max length.

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for (string s : strs) {
        string key = s;
        sort(key.begin(), key.end()); // Sorting identifies the anagram group
        groups[key].push_back(s);
    }
    
    vector<vector<string>> result;
    for (auto& pair : groups) {
        result.push_back(pair.second);
    }
    return result;
}

3. The "Best" Solution (Frequency Counting)

Instead of sorting (which is slow), use a frequency array of size 26 as the key. Time: $O(N \cdot K)$

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for (string s : strs) {
        vector<int> count(26, 0);
        for (char c : s) count[c - 'a']++;
        
        // Convert count array to a unique string key like "1#0#2#..."
        string key = "";
        for (int i : count) key += to_string(i) + "#"; 
        
        groups[key].push_back(s);
    }
    
    vector<vector<string>> result;
    for (auto& pair : groups) result.push_back(pair.second);
    return result;
}

4. The "Wired" Solution (Prime Factorization Hashing)

This is "Galaxy Brain" logic. Fundamental Theorem of Arithmetic says every number has a unique prime factorization. Assign a prime number to each char (a=2, b=3, c=5...). The product of these for any anagram will be identical!

// Note: Can cause overflow for very long strings, use double or long long carefully.
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
    unordered_map<double, vector<string>> groups;
    for (string s : strs) {
        double prod = 1;
        for (char c : s) prod *= primes[c - 'a'];
        groups[prod].push_back(s);
    }
    vector<vector<string>> result;
    for (auto& p : groups) result.push_back(p.second);
    return result;
}

---

Mind Map

GROUP ANAGRAMS
│
├── 1. Brute Force (Nested Loop)
│   └── Compare S1 with S2, S3... Sn using "isAnagram()"
│   └── Time: O(N^2 * K) | Space: O(N)
│
├── 2. Categorize by Sorting (The Standard)
│   └── Key = Sorted String (e.g., "eat" -> "aet")
│   └── Data Structure: Map<String, List>
│   └── Time: O(N * K log K) | Space: O(N * K)
│
├── 3. Categorize by Count (The Efficient)
│   └── Key = String/Tuple of 26 integers
│   └── Data Structure: Map<Key, List>
│   └── Time: O(N * K) | Space: O(N * K)
│
└── 4. Prime Product (The "Wired" Hack)
    └── Key = Product of prime assigned to each char
    └── Warning: Potential integer overflow!
    └── Time: O(N * K) | Space: O(N)

Interview Tip: Always start with the Sorting approach, explain its $O(N \cdot K \log K)$ bottleneck, and then propose the Frequency Counting approach to reach $O(N \cdot K)$. This shows you know how to optimize.