Common Hashing Patterns & Problem Types

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/**
 * 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
 */
function countFrequencies<T>(elements: T[]): Map<T, number> {
    const frequencyMap = new Map<T, number>();
    
    for (const element of elements) {
        // Get current count (defaults to 0 if not present)
        const currentCount = frequencyMap.get(element) ?? 0;
        // Increment and store
        frequencyMap.set(element, currentCount + 1);
    }
    
    return frequencyMap;
}
 
// Example usage
const words = ["apple", "banana", "apple", "cherry", "banana", "apple"];
const wordCounts = countFrequencies(words);
 
// Result: Map { "apple" => 3, "banana" => 2, "cherry" => 1 }
console.log(wordCounts);
 
// Converting to array for analysis
const sorted = [...wordCounts.entries()]
    .sort((a, b) => b[1] - a[1]); // Sort by count descending
    
console.log("Most frequent:", sorted[0]); // ["apple", 3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

/**
 * Find elements that appear more than k times
 * Optimization: Track only until we exceed threshold
 */
function findFrequentElements<T>(elements: T[], k: number): T[] {
    const counts = new Map<T, number>();
    const result: T[] = [];
    const alreadyAdded = new Set<T>();
    
    for (const element of elements) {
        const newCount = (counts.get(element) ?? 0) + 1;
        counts.set(element, newCount);
        
        // Add to result when threshold exceeded (only once)
        if (newCount > k && !alreadyAdded.has(element)) {
            result.push(element);
            alreadyAdded.add(element);
        }
    }
    
    return result;
}
 
/**
 * Find the first duplicate element (early termination)
 */
function findFirstDuplicate<T>(elements: T[]): T | undefined {
    const seen = new Set<T>();
    
    for (const element of elements) {
        if (seen.has(element)) {
            return element; // Early exit!
        }
        seen.add(element);
    }
    
    return undefined;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

/**
 * 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<string, number>();
    
    // 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<K, V>(map1: Map<K, V>, map2: Map<K, V>): 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"));   // false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

/**
 * 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<string, number>();
    const windowFreq = new Map<string, number>();
    
    // 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]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

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])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

/**
 * 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<number, number>();
    
    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<number, number>();
    
    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]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

/**
 * 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<string, number>();
    
    // 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<string, number>();
    const order: number[] = []; // Index of first occurrence
    const charToIndex = new Map<string, number>();
    
    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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

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"))   # False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// BAD: Using arrays as Map keys
const badMap = new Map<number[], number>();
const key1 = [1, 2, 3];
const key2 = [1, 2, 3];
badMap.set(key1, 1);
console.log(badMap.get(key2)); // undefined! (different reference)
 
// GOOD: Use string representation
const goodMap = new Map<string, number>();
goodMap.set(JSON.stringify([1, 2, 3]), 1);
console.log(goodMap.get(JSON.stringify([1, 2, 3]))); // 1
 
// GOOD: Group by creating composite key strings
function groupByPair(items: [string, string][]): Map<string, number> {
    const counts = new Map<string, number>();
    
    for (const [a, b] of items) {
        // Create deterministic composite key
        const key = `${a}||${b}`; // Use delimiter unlikely in data
        counts.set(key, (counts.get(key) ?? 0) + 1);
    }
    
    return counts;
}