7a:T585,""" Basic frequency counting: count occurrences of each element Time: O(n) where n is the number of elements Space: O(k) where k is the number of unique elements """ from collections import defaultdict, Counter from typing import TypeVar, List, Dict T = TypeVar('T') def count_frequencies(elements: List[T]) -> Dict[T, int]: """Manual frequency counting implementation.""" frequency_map: Dict[T, int] = {} for element in elements: # Get current count (defaults to 0 if not present) current_count = frequency_map.get(element, 0) # Increment and store frequency_map[element] = current_count + 1 return frequency_map def count_frequencies_defaultdict(elements: List[T]) -> Dict[T, int]: """Using defaultdict for cleaner code.""" frequency_map = defaultdict(int) for element in elements: frequency_map[element] += 1 return dict(frequency_map) def count_frequencies_counter(elements: List[T]) -> Counter: """Using Counter - the Pythonic way.""" return Counter(elements) # Example usage words = ["apple", "banana", "apple", "cherry", "banana", "apple"] # All three produce equivalent results counts = count_frequencies(words) print(counts) # {'apple': 3, 'banana': 2, 'cherry': 1} # Counter provides additional utilities counter = Counter(words) print(counter.most_common(2)) # [('apple', 3), ('banana', 2)]7b:T7fe,import java.util.*; public class FrequencyCounting { /** * Basic frequency counting: count occurrences of each element * Time: O(n) where n is the number of elements * Space: O(k) where k is the number of unique elements */ public static Map countFrequencies(List elements) { Map frequencyMap = new HashMap<>(); for (T element : elements) { // Get current count (defaults to 0 if not present) int currentCount = frequencyMap.getOrDefault(element, 0); // Increment and store frequencyMap.put(element, currentCount + 1); } return frequencyMap; } /** * Using merge() for more concise code (Java 8+) */ public static Map countFrequenciesMerge(List elements) { Map frequencyMap = new HashMap<>(); for (T element : elements) { frequencyMap.merge(element, 1, Integer::sum); } return frequencyMap; } /** * Using compute() for explicit control */ public static Map countFrequenciesCompute(List elements) { Map frequencyMap = new HashMap<>(); for (T element : elements) { frequencyMap.compute(element, (k, v) -> v == null ? 1 : v + 1); } return frequencyMap; } public static void main(String[] args) { List words = Arrays.asList( "apple", "banana", "apple", "cherry", "banana", "apple" ); Map counts = countFrequencies(words); System.out.println(counts); // {apple=3, banana=2, cherry=1} // Finding the most frequent element String mostFrequent = Collections.max( counts.entrySet(), Map.Entry.comparingByValue() ).getKey(); System.out.println("Most frequent: " + mostFrequent); } }7c:T4c7,Understanding the complexity of frequency counting requires examining both the best and worst cases, as well as understanding why this pattern is so efficient. **Time Complexity:** - **Best/Average Case: O(n)** — We iterate through n elements exactly once. Each hash table operation (get and set) is O(1) amortized. - **Worst Case: O(n²)** — If all elements hash to the same bucket (extremely rare with good hash functions), each operation becomes O(n). **Space Complexity:** - **Best Case: O(1)** — If all elements are identical, we store only one entry. - **Worst Case: O(n)** — If all elements are unique, we store n entries. - **Typical Case: O(k)** — Where k is the number of unique elements. For many applications, k << n. **Why O(n) Matters:** Consider the alternative without hash tables. To count frequencies, you might: 1. For each element, scan the entire array to count occurrences 2. Track which elements you've already counted This approach is O(n²). On a million elements: - Hash-based: ~1 million operations - Naive: ~1 trillion operations The speedup factor is **1,000,000x**. This is why frequency counting with hash tables is considered one of the most important algorithmic patterns.7d:T47d,from typing import TypeVar, List, Optional, Set T = TypeVar('T') def find_frequent_elements(elements: List[T], k: int) -> List[T]: """ Find elements that appear more than k times. Optimization: Track only until we exceed threshold. """ counts: dict = {} result: List[T] = [] already_added: Set[T] = set() for element in elements: new_count = counts.get(element, 0) + 1 counts[element] = new_count # Add to result when threshold exceeded (only once) if new_count > k and element not in already_added: result.append(element) already_added.add(element) return result def find_first_duplicate(elements: List[T]) -> Optional[T]: """Find the first duplicate element (early termination).""" seen: Set[T] = set() for element in elements: if element in seen: return element # Early exit! seen.add(element) return None # Example data = [1, 2, 3, 2, 4, 1, 5, 1, 2] print(find_frequent_elements(data, 2)) # [1, 2] (appear > 2 times) print(find_first_duplicate(data)) # 2 (first repeated)7e:T471,/** * Check if two strings are anagrams * Key insight: Anagrams have identical character frequencies */ function areAnagrams(s1: string, s2: string): boolean { if (s1.length !== s2.length) return false; const freq = new Map(); // Build frequency map for first string for (const char of s1) { freq.set(char, (freq.get(char) ?? 0) + 1); } // Subtract frequencies for second string for (const char of s2) { const count = freq.get(char); if (count === undefined || count === 0) { return false; // Character not in s1 or depleted } freq.set(char, count - 1); } return true; // All counts are now 0 } /** * Alternative: Compare two frequency maps */ function mapsEqual(map1: Map, map2: Map): boolean { if (map1.size !== map2.size) return false; for (const [key, value] of map1) { if (map2.get(key) !== value) return false; } return true; } // Examples console.log(areAnagrams("listen", "silent")); // true console.log(areAnagrams("hello", "world")); // false7f:T51b,from collections import Counter def are_anagrams(s1: str, s2: str) -> bool: """ Check if two strings are anagrams. Key insight: Anagrams have identical character frequencies. """ if len(s1) != len(s2): return False freq: dict = {} # Build frequency map for first string for char in s1: freq[char] = freq.get(char, 0) + 1 # Subtract frequencies for second string for char in s2: count = freq.get(char, 0) if count == 0: return False # Character not in s1 or depleted freq[char] = count - 1 return True # All counts are now 0 def are_anagrams_pythonic(s1: str, s2: str) -> bool: """Pythonic version using Counter.""" return Counter(s1) == Counter(s2) def can_form_from(source: str, target: str) -> bool: """ Check if 'target' can be formed from letters in 'source'. (subset containment by frequency) """ source_freq = Counter(source) target_freq = Counter(target) for char, count in target_freq.items(): if source_freq[char] < count: return False return True # Examples print(are_anagrams("listen", "silent")) # True print(can_form_from("aabbcc", "abc")) # True print(can_form_from("abc", "aabbcc")) # False80:T914,/** * Find all anagram occurrences of pattern in text * Uses sliding window with frequency comparison */ function findAnagramIndices(text: string, pattern: string): number[] { if (pattern.length > text.length) return []; const result: number[] = []; const patternFreq = new Map(); const windowFreq = new Map(); // Build pattern frequency map for (const char of pattern) { patternFreq.set(char, (patternFreq.get(char) ?? 0) + 1); } // Track how many characters have matching counts let matchCount = 0; const targetMatchCount = patternFreq.size; for (let i = 0; i < text.length; i++) { // Add character entering window const entering = text[i]; const newEnteringCount = (windowFreq.get(entering) ?? 0) + 1; windowFreq.set(entering, newEnteringCount); // Update match count for entering character const patternEnteringCount = patternFreq.get(entering) ?? 0; if (newEnteringCount === patternEnteringCount) { matchCount++; } else if (newEnteringCount === patternEnteringCount + 1) { matchCount--; } // Remove character leaving window (if window is full) if (i >= pattern.length) { const leaving = text[i - pattern.length]; const oldLeavingCount = windowFreq.get(leaving)!; const newLeavingCount = oldLeavingCount - 1; if (newLeavingCount === 0) { windowFreq.delete(leaving); } else { windowFreq.set(leaving, newLeavingCount); } // Update match count for leaving character const patternLeavingCount = patternFreq.get(leaving) ?? 0; if (oldLeavingCount === patternLeavingCount) { matchCount--; } else if (newLeavingCount === patternLeavingCount) { matchCount++; } } // Check if current window is an anagram if (i >= pattern.length - 1 && matchCount === targetMatchCount) { result.push(i - pattern.length + 1); } } return result; } // Example console.log(findAnagramIndices("cbaebabacd", "abc")); // [0, 6]81:T650,from collections import Counter from math import log from typing import List, Dict def compute_tf(document: str) -> Dict[str, float]: """ Compute term frequency for each word in a document. TF(word) = count(word) / total_words """ words = document.lower().split() word_counts = Counter(words) total_words = len(words) return {word: count / total_words for word, count in word_counts.items()} def compute_idf(documents: List[str]) -> Dict[str, float]: """ Compute inverse document frequency across corpus. IDF(word) = log(total_docs / docs_containing_word) """ total_docs = len(documents) doc_counts: Counter = Counter() for doc in documents: # Count each word once per document (use set) unique_words = set(doc.lower().split()) doc_counts.update(unique_words) return {word: log(total_docs / count) for word, count in doc_counts.items()} def compute_tfidf(document: str, idf: Dict[str, float]) -> Dict[str, float]: """Compute TF-IDF scores for a document.""" tf = compute_tf(document) return {word: tf_score * idf.get(word, 0) for word, tf_score in tf.items()} # Example: Simple search corpus corpus = [ "The quick brown fox jumps over the lazy dog", "The lazy cat sleeps all day long", "A quick solution requires quick thinking" ] idf = compute_idf(corpus) document_scores = compute_tfidf(corpus[0], idf) # Words unique to document 0 have higher TF-IDF print(sorted(document_scores.items(), key=lambda x: x[1], reverse=True)[:5])82:T5dd,/** * Top K Frequent Elements * * Approach 1: Sort by frequency - O(n log n) * Approach 2: Min-heap of size k - O(n log k) * Approach 3: Bucket sort - O(n) (when k can be large) */ // Approach 1: Simple sorting (O(n log n)) function topKFrequentSort(nums: number[], k: number): number[] { const freq = new Map(); for (const num of nums) { freq.set(num, (freq.get(num) ?? 0) + 1); } return [...freq.entries()] .sort((a, b) => b[1] - a[1]) .slice(0, k) .map(entry => entry[0]); } // Approach 3: Bucket sort (O(n)) // Key insight: frequency can be at most n, so we can use an array of buckets function topKFrequentBucket(nums: number[], k: number): number[] { const freq = new Map(); for (const num of nums) { freq.set(num, (freq.get(num) ?? 0) + 1); } // Create buckets: bucket[i] contains elements with frequency i // Index 0 unused since no element has frequency 0 const buckets: number[][] = Array.from( { length: nums.length + 1 }, () => [] ); for (const [num, count] of freq) { buckets[count].push(num); } // Collect from highest frequency buckets const result: number[] = []; for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) { result.push(...buckets[i]); } return result.slice(0, k); } // Example console.log(topKFrequentBucket([1,1,1,2,2,3], 2)); // [1, 2]83:T52e,from collections import Counter from typing import List import heapq def top_k_frequent_counter(nums: List[int], k: int) -> List[int]: """Using Counter's most_common - O(n log n)""" return [num for num, count in Counter(nums).most_common(k)] def top_k_frequent_heap(nums: List[int], k: int) -> List[int]: """Using min-heap of size k - O(n log k)""" freq = Counter(nums) # Min-heap keeps k largest by frequency # We push (count, num) and heapify maintains min at top min_heap = [] for num, count in freq.items(): heapq.heappush(min_heap, (count, num)) if len(min_heap) > k: heapq.heappop(min_heap) # Remove smallest return [num for count, num in min_heap] def top_k_frequent_bucket(nums: List[int], k: int) -> List[int]: """Using bucket sort - O(n)""" freq = Counter(nums) # Buckets indexed by frequency buckets = [[] for _ in range(len(nums) + 1)] for num, count in freq.items(): buckets[count].append(num) # Collect from highest frequency buckets result = [] for i in range(len(buckets) - 1, -1, -1): result.extend(buckets[i]) if len(result) >= k: return result[:k] return result # Example print(top_k_frequent_bucket([1,1,1,2,2,3], 2)) # [1, 2]84:T5dc,/** * First Unique Character in a String * * Key insight: Count frequencies first, then scan for count === 1 * Time: O(n), Space: O(1) if alphabet is fixed (26 lowercase letters) */ function firstUniqChar(s: string): number { const freq = new Map(); // First pass: count frequencies for (const char of s) { freq.set(char, (freq.get(char) ?? 0) + 1); } // Second pass: find first with frequency 1 for (let i = 0; i < s.length; i++) { if (freq.get(s[i]) === 1) { return i; } } return -1; } /** * Variant: Track order of appearance for single-pass streaming * Useful when you can't re-scan the input */ function firstUniqCharStream(s: string): number { const freq = new Map(); const order: number[] = []; // Index of first occurrence const charToIndex = new Map(); for (let i = 0; i < s.length; i++) { const char = s[i]; const count = (freq.get(char) ?? 0) + 1; freq.set(char, count); if (count === 1) { charToIndex.set(char, i); order.push(i); } } // Find first index in order with frequency 1 for (const idx of order) { if (freq.get(s[idx]) === 1) { return idx; } } return -1; } console.log(firstUniqChar("onenoughtone")); // 2 (e is unique) console.log(firstUniqChar("algorithm")); // 0 (a is first unique)85:T464,from collections import Counter def can_construct(ransom_note: str, magazine: str) -> bool: """ Can ransom_note be constructed from magazine letters? Key insight: magazine must have >= frequency of each char in note """ note_freq = Counter(ransom_note) magazine_freq = Counter(magazine) for char, count in note_freq.items(): if magazine_freq[char] < count: return False return True def can_construct_subtract(ransom_note: str, magazine: str) -> bool: """Alternative: subtract and check for negatives""" magazine_freq = Counter(magazine) for char in ransom_note: magazine_freq[char] -= 1 if magazine_freq[char] < 0: return False return True def can_construct_pythonic(ransom_note: str, magazine: str) -> bool: """ Most Pythonic: Counter subtraction leaves only shortage Counter with negative counts indicates what's missing """ return not (Counter(ransom_note) - Counter(magazine)) # Examples print(can_construct("aa", "aab")) # True print(can_construct("aa", "ab")) # False72:{"json":{"id":"seed_46808cc7e0af0ee0a9c2a99125f52855","slug":"common-hashing-patterns","category":"Data Structures & Algorithms","topic":"Hash Tables","title":"Common Hashing Patterns & Problem Types","description":"Master the fundamental hashing patterns that appear across countless programming challenges: frequency counting, pair finding (Two-Sum), duplicate detection, grouping by characteristic, and caching/memoization. Learn to recognize when hashing is the right tool and apply these patterns confidently.","difficulty":"INTERMEDIATE","estimatedMinutes":75,"pages":[{"id":"seed_12cd5e3b34c983ad4bff5f1dddf64511","title":"Frequency Counting","order":0,"content":[{"id":"opening-hook","title":"The Universal Pattern","content":[{"data":{"content":"If you were to analyze every algorithm problem ever solved using hash tables, one pattern would appear more frequently than any other: **frequency counting**. It is so fundamental, so universally applicable, that mastering it unlocks a vast portion of algorithmic problem-solving.\n\nFrequency counting answers the simplest yet most powerful question: **How many times does each thing appear?**\n\nThis deceptively simple question underlies countless real-world applications:\n- How many times has each word appeared in a document?\n- Which characters appear in one string but not another?\n- What is the most common IP address hitting our server?\n- How many votes did each candidate receive?\n- What items appear more than k times in our dataset?\n\nIn every case, the naive approach—iterating through the data repeatedly for each unique element—yields O(n²) complexity. The hash-based approach? **O(n)**. This single pattern optimization has saved more computing hours than perhaps any other algorithmic technique."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Master","content":"By the end of this page, you will deeply understand frequency counting as a pattern: when to apply it, how to implement it efficiently in multiple languages, and how to recognize disguised frequency problems. You will see how this single pattern forms the foundation for dozens of classic interview problems and real-world applications.","variant":"info"},"type":"callout"}]},{"id":"core-concept","title":"The Core Concept","content":[{"data":{"content":"At its heart, frequency counting is a **mapping problem**. We need to map each unique element to its count of occurrences. This is precisely what hash tables excel at: mapping keys to values in O(1) average time.\n\n**The Mental Model:**\n\nImagine you're a librarian cataloging books. As each book arrives, you check if you've seen this title before:\n- If not, create a new entry with count = 1\n- If yes, increment the existing count\n\nAfter processing all books, you have a complete count of every title. The hash table is your catalog index—providing instant lookup by title.\n\n**The Invariant:**\n\nAt any point during frequency counting, the hash table maintains a critical invariant:\n\n> **For every key k in the map, map[k] equals the exact number of times k appeared in the processed portion of the input.**\n\nThis invariant is what makes frequency counting so reliable. It's self-correcting—any element we encounter either creates or updates an entry, never leaving the count in an inconsistent state."},"type":"text"},{"data":{"fileName":"frequency_counting_basic","languages":[{"code":"/**\n * Basic frequency counting: count occurrences of each element\n * Time: O(n) where n is the number of elements\n * Space: O(k) where k is the number of unique elements\n */\nfunction countFrequencies(elements: T[]): Map {\n const frequencyMap = new Map();\n \n for (const element of elements) {\n // Get current count (defaults to 0 if not present)\n const currentCount = frequencyMap.get(element) ?? 0;\n // Increment and store\n frequencyMap.set(element, currentCount + 1);\n }\n \n return frequencyMap;\n}\n\n// Example usage\nconst words = [\"apple\", \"banana\", \"apple\", \"cherry\", \"banana\", \"apple\"];\nconst wordCounts = countFrequencies(words);\n\n// Result: Map { \"apple\" => 3, \"banana\" => 2, \"cherry\" => 1 }\nconsole.log(wordCounts);\n\n// Converting to array for analysis\nconst sorted = [...wordCounts.entries()]\n .sort((a, b) => b[1] - a[1]); // Sort by count descending\n \nconsole.log(\"Most frequent:\", sorted[0]); // [\"apple\", 3]","label":"TypeScript","value":"typescript"},{"code":"$7a","label":"Python","value":"python"},{"code":"$7b","label":"Java","value":"java"}]},"type":"code"}],"titleType":"number","titleNumber":1},{"id":"complexity-analysis","title":"Complexity Analysis","content":[{"data":{"content":"$7c"},"type":"text"},{"data":{"rows":[["Time (n=1,000)","O(1,000)","O(1,000,000)","1,000x"],["Time (n=1,000,000)","O(1,000,000)","O(1,000,000,000,000)","1,000,000x"],["Space (worst)","O(n)","O(n)","Same"],["Space (typical)","O(k) where k << n","O(n)","Better"]],"caption":"Frequency Counting Complexity Summary","headers":["Metric","Hash Table Approach","Naive Approach","Improvement Factor"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"The Practical Perspective","content":"In real-world applications, the space complexity O(k) is often much better than O(n). Counting word frequencies in a novel has millions of words but typically only 10,000-30,000 unique words. Counting customer purchase categories for a retailer might involve billions of transactions but only hundreds of product categories.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"variations-extensions","title":"Variations and Extensions","content":[{"data":{"content":"The basic frequency counting pattern extends to many powerful variations. Each builds on the core concept while adding specific capabilities.\n\n**Variation 1: Bounded Frequency Counting**\n\nSometimes we only care about counts up to some threshold. For example, when detecting duplicates, we only need to know if count > 1. This can optimize early termination:"},"type":"text"},{"data":{"fileName":"bounded_frequency","languages":[{"code":"/**\n * Find elements that appear more than k times\n * Optimization: Track only until we exceed threshold\n */\nfunction findFrequentElements(elements: T[], k: number): T[] {\n const counts = new Map();\n const result: T[] = [];\n const alreadyAdded = new Set();\n \n for (const element of elements) {\n const newCount = (counts.get(element) ?? 0) + 1;\n counts.set(element, newCount);\n \n // Add to result when threshold exceeded (only once)\n if (newCount > k && !alreadyAdded.has(element)) {\n result.push(element);\n alreadyAdded.add(element);\n }\n }\n \n return result;\n}\n\n/**\n * Find the first duplicate element (early termination)\n */\nfunction findFirstDuplicate(elements: T[]): T | undefined {\n const seen = new Set();\n \n for (const element of elements) {\n if (seen.has(element)) {\n return element; // Early exit!\n }\n seen.add(element);\n }\n \n return undefined;\n}","label":"TypeScript","value":"typescript"},{"code":"$7d","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"**Variation 2: Frequency Comparison**\n\nComparing frequencies between two collections reveals relationships like anagrams, permutations, or subset containment:"},"type":"text"},{"data":{"fileName":"frequency_comparison","languages":[{"code":"$7e","label":"TypeScript","value":"typescript"},{"code":"$7f","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"**Variation 3: Rolling/Sliding Window Frequency**\n\nMaintaining frequencies over a sliding window requires careful updates as elements enter and leave:"},"type":"text"},{"data":{"fileName":"sliding_frequency","languages":[{"code":"$80","label":"TypeScript","value":"typescript"}]},"type":"code"}],"titleType":"number","titleNumber":3},{"id":"real-world-applications","title":"Real-World Applications","content":[{"data":{"content":"Frequency counting isn't just an interview pattern—it's a cornerstone of real production systems across every industry. Let's examine how this pattern manifests in different domains:\n\n**1. Search Engines: TF-IDF and Document Indexing**\n\nWhen you search for \"best pizza near me,\" search engines don't match your query against every document sequentially. Instead, they've pre-computed term frequencies for every document in their index.\n\n- **Term Frequency (TF)**: How often does \"pizza\" appear in this document?\n- **Inverse Document Frequency (IDF)**: How common is \"pizza\" across all documents?\n\nBoth require frequency counting at massive scale. Google processes over 8.5 billion searches per day, each matching against billions of indexed documents—all powered by frequency-based ranking."},"type":"text"},{"data":{"fileName":"tf_idf_example","languages":[{"code":"$81","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"**2. Network Security: DDoS Detection and Rate Limiting**\n\nFrequency counting is essential for detecting abuse patterns in network traffic:\n\n- **Rate Limiting**: Count requests per IP per time window\n- **DDoS Detection**: Identify IPs exceeding normal request thresholds\n- **Fraud Detection**: Flag accounts with unusual transaction frequencies\n\n**3. Bioinformatics: Genome Analysis**\n\nCounting nucleotide (A, C, G, T) frequencies helps identify:\n- Gene coding regions\n- Evolutionary relationships between species\n- Potential mutation sites\n\n**4. Recommendation Systems**\n\nFrequency-based collaborative filtering:\n- Count how often users rate items similarly\n- Identify frequently co-purchased products\n- Find popular items within user segments\n\n**5. Log Analysis and Observability**\n\n- Count error types per service\n- Identify most frequent API endpoints\n- Track feature usage patterns"},"type":"text"},{"data":{"icon":"Info","title":"Scale Considerations","content":"At extreme scale (billions of events), exact frequency counting becomes impractical due to memory constraints. Production systems often use probabilistic data structures like Count-Min Sketch or HyperLogLog for approximate counting with bounded error guarantees. These trade exact accuracy for O(1) space complexity.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"interview-problems","title":"Classic Interview Problems","content":[{"data":{"content":"Frequency counting appears in numerous interview problems, often in disguised forms. Learning to recognize the pattern is key to solving them efficiently.\n\n**Problem 1: Top K Frequent Elements**\n\nGiven an array of integers, return the k most frequent elements. This is a direct application of frequency counting followed by selection."},"type":"text"},{"data":{"fileName":"top_k_frequent","languages":[{"code":"$82","label":"TypeScript","value":"typescript"},{"code":"$83","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"**Problem 2: Valid Anagram**\n\nGiven two strings s and t, return true if t is an anagram of s. This is pure frequency comparison."},"type":"text"},{"data":{"content":"**Problem 3: First Unique Character in a String**\n\nGiven a string, find the first non-repeating character and return its index. If it doesn't exist, return -1."},"type":"text"},{"data":{"fileName":"first_unique_char","languages":[{"code":"$84","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"content":"**Problem 4: Ransom Note**\n\nGiven two strings ransomNote and magazine, return true if ransomNote can be constructed from the letters in magazine. Each letter in magazine can only be used once."},"type":"text"},{"data":{"fileName":"ransom_note","languages":[{"code":"$85","label":"Python","value":"python"}]},"type":"code"}],"titleType":"number","titleNumber":5},{"id":"common-pitfalls","title":"Common Pitfalls and Best Practices","content":[{"data":{"content":"Even experienced engineers make mistakes with frequency counting. Here are the most common pitfalls and how to avoid them:"},"type":"text"},{"data":{"items":["**Problem**: Accessing a non-existent key throws an error or returns undefined","**JavaScript/TypeScript**: `map.get(key)` returns `undefined` for missing keys","**Python**: `dict[key]` raises `KeyError` for missing keys","**Java**: `map.get(key)` returns `null` for missing keys","**Solution**: Always use `get(key, default)` or equivalent: `map.get(key) ?? 0`"],"title":{"icon":"AlertCircle","text":"Pitfall 1: Forgetting to Handle Missing Keys","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"items":["**Problem**: 'Apple' and 'apple' are counted as different words","**Solution**: Normalize case before counting: `str.toLowerCase()` or `str.lower()`","**Consider**: Should 'Apple' (brand) and 'apple' (fruit) be the same? Domain matters!"],"title":{"icon":"AlertCircle","text":"Pitfall 2: Case Sensitivity","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"items":["**Problem**: Floating-point comparison issues cause hash collisions","**Example**: `0.1 + 0.2 !== 0.3` due to floating-point representation","**Solution**: Round to fixed precision or use string representation","**Better**: Avoid floating-point keys entirely when possible"],"title":{"icon":"AlertCircle","text":"Pitfall 3: Floating-Point Keys","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"items":["**Problem**: Using arrays or objects as keys directly","**JavaScript Issue**: `[1,2,3] !== [1,2,3]` - Arrays are compared by reference","**Python Issue**: Lists aren't hashable","**Solution**: Convert to immutable representation: `JSON.stringify()` or `tuple()`"],"title":{"icon":"AlertCircle","text":"Pitfall 4: Mutable Keys","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"fileName":"pitfall_examples","languages":[{"code":"// BAD: Using arrays as Map keys\nconst badMap = new Map();\nconst key1 = [1, 2, 3];\nconst key2 = [1, 2, 3];\nbadMap.set(key1, 1);\nconsole.log(badMap.get(key2)); // undefined! (different reference)\n\n// GOOD: Use string representation\nconst goodMap = new Map();\ngoodMap.set(JSON.stringify([1, 2, 3]), 1);\nconsole.log(goodMap.get(JSON.stringify([1, 2, 3]))); // 1\n\n// GOOD: Group by creating composite key strings\nfunction groupByPair(items: [string, string][]): Map {\n const counts = new Map();\n \n for (const [a, b] of items) {\n // Create deterministic composite key\n const key = `${a}||${b}`; // Use delimiter unlikely in data\n counts.set(key, (counts.get(key) ?? 0) + 1);\n }\n \n return counts;\n}","label":"TypeScript","value":"typescript"},{"code":"# BAD: Lists aren't hashable in Python\ntry:\n bad_dict = {}\n bad_dict[[1, 2, 3]] = 1 # TypeError: unhashable type: 'list'\nexcept TypeError as e:\n print(f\"Error: {e}\")\n\n# GOOD: Use tuples (immutable and hashable)\ngood_dict = {}\ngood_dict[(1, 2, 3)] = 1\nprint(good_dict[(1, 2, 3)]) # 1\n\n# GOOD: Frozenset for unordered collections\ndef group_by_set(items):\n \"\"\"Group items by their set membership (order doesn't matter).\"\"\"\n counts = {}\n \n for item in items:\n # frozenset is hashable, unlike set\n key = frozenset(item)\n counts[key] = counts.get(key, 0) + 1\n \n return counts\n\n# Example: {1, 2, 3} and {3, 2, 1} count as same group\ngroups = [[1, 2, 3], [3, 2, 1], [1, 2]]\nprint(group_by_set(groups)) \n# {frozenset({1, 2, 3}): 2, frozenset({1, 2}): 1}","label":"Python","value":"python"}]},"type":"code"},{"data":{"icon":"Lightbulb","title":"Best Practice: Defensive Counting","content":"When frequency counting in production code:\n1. Always normalize input (case, whitespace, encoding)\n2. Use explicit defaults for missing keys\n3. Consider whether keys are truly unique (beware of collisions)\n4. Document your key normalization strategy\n5. Test with edge cases: empty input, single element, all duplicates","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"summary","title":"Summary: Mastering Frequency Counting","content":[{"data":{"content":"We've explored frequency counting from first principles to advanced applications. Let's consolidate the key insights:"},"type":"text"},{"data":{"type":"ordered","items":["**Frequency counting transforms O(n²) to O(n)** — The fundamental speedup that makes this pattern invaluable","**The pattern is: iterate once, build a map, query as needed** — Simple structure, profound impact","**Variations include bounded counting, comparison, and sliding windows** — Each extends the core pattern for specific use cases","**Real-world applications span search engines to bioinformatics** — This isn't just interview prep; it's real engineering","**Language-specific APIs matter** — `Counter`, `defaultdict`, `Map.merge()` make code cleaner and less error-prone","**Watch for key normalization and mutability issues** — Most bugs come from inconsistent key handling"],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now deeply understand frequency counting—the most fundamental hashing pattern. This single concept underpins countless algorithms and appears in nearly every technical interview. Next, we'll explore the Two-Sum pattern and how hashing enables pair-finding problems.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7}],"isLocked":false},{"id":"seed_3c321751a64f3e6299da6eed3e0f150d","title":"Two-Sum and Pair Problems","order":1,"content":null,"isLocked":true},{"id":"seed_9c268293dca19d7931f62c288b48c5d6","title":"Duplicate Detection","order":2,"content":null,"isLocked":true},{"id":"seed_f993da89f57f0e52968d4f2e8e02fd2d","title":"Grouping by Characteristic","order":3,"content":null,"isLocked":true},{"id":"seed_12722e04aa049949c33d3bcefd630893","title":"Caching and Memoization","order":4,"content":null,"isLocked":true}]}}