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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/**
 * Generic grouping function
 * Groups elements by the result of a key function
 * 
 * Time: O(n * k) where k is the complexity of keyFn
 * Space: O(n)
 */
function groupBy<T, K>(items: T[], keyFn: (item: T) => K): Map<K, T[]> {
    const groups = new Map<K, T[]>();
    
    for (const item of items) {
        const key = keyFn(item);
        
        if (!groups.has(key)) {
            groups.set(key, []);
        }
        groups.get(key)!.push(item);
    }
    
    return groups;
}
 
// Example 1: Group numbers by parity (even/odd)
const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const byParity = groupBy(numbers, n => n % 2 === 0 ? 'even' : 'odd');
console.log(byParity);
// Map { 'odd' => [1, 3, 5, 7, 9], 'even' => [2, 4, 6, 8, 10] }
 
// Example 2: Group strings by first letter
const words = ['apple', 'banana', 'apricot', 'blueberry', 'cherry'];
const byFirstLetter = groupBy(words, w => w[0].toLowerCase());
console.log(byFirstLetter);
// Map { 'a' => ['apple', 'apricot'], 'b' => ['banana', 'blueberry'], 'c' => ['cherry'] }
 
// Example 3: Group objects by property
interface Person { name: string; age: number; city: string; }
const people: Person[] = [
    { name: 'Alice', age: 30, city: 'NYC' },
    { name: 'Bob', age: 25, city: 'LA' },
    { name: 'Charlie', age: 30, city: 'NYC' },
    { name: 'Diana', age: 25, city: 'NYC' },
];
const byCity = groupBy(people, p => p.city);
console.log(byCity);
// Map { 'NYC' => [Alice, Charlie, Diana], 'LA' => [Bob] }

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

// PROBLEM: Objects as keys don't work by default
const badGrouping = new Map<number[], string[]>();
const key1 = [1, 2];
const key2 = [1, 2]; // Same content, different reference
badGrouping.set(key1, ['item1']);
badGrouping.get(key2); // undefined! Different object reference
 
// SOLUTION 1: Serialize to string
function groupByArrayKey<T>(items: T[], keyFn: (item: T) => number[]): Map<string, T[]> {
    const groups = new Map<string, T[]>();
    
    for (const item of items) {
        const keyArray = keyFn(item);
        const keyString = JSON.stringify(keyArray); // Serialize
        
        if (!groups.has(keyString)) {
            groups.set(keyString, []);
        }
        groups.get(keyString)!.push(item);
    }
    
    return groups;
}
 
// Example: Group points by their quadrant signature
interface Point { x: number; y: number; }
const points: Point[] = [
    { x: 1, y: 2 }, { x: -1, y: 3 }, { x: 2, y: 1 }, { x: -2, y: -1 }
];
 
const byQuadrant = groupByArrayKey(points, p => [
    Math.sign(p.x),  // -1, 0, or 1
    Math.sign(p.y)
]);
console.log(byQuadrant);
// Map { '[1,1]' => [Point(1,2), Point(2,1)], '[-1,1]' => [Point(-1,3)], '[-1,-1]' => [Point(-2,-1)] }

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

/**
 * Group Anagrams - Sorting Approach
 * Time: O(n * k log k) where k is max string length
 * Space: O(n * k)
 */
function groupAnagramsSorting(strs: string[]): string[][] {
    const groups = new Map<string, string[]>();
    
    for (const str of strs) {
        // Key: sorted characters
        const key = str.split('').sort().join('');
        
        if (!groups.has(key)) {
            groups.set(key, []);
        }
        groups.get(key)!.push(str);
    }
    
    return [...groups.values()];
}
 
/**
 * Group Anagrams - Character Count Approach
 * Time: O(n * k) where k is max string length
 * Space: O(n * k)
 * 
 * Faster for long strings (avoids O(k log k) sorting)
 */
function groupAnagramsCounting(strs: string[]): string[][] {
    const groups = new Map<string, string[]>();
    
    for (const str of strs) {
        // Build character count key
        const counts = new Array(26).fill(0);
        for (const char of str) {
            counts[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        // Convert to string key: "1#0#0#..." for counts of a, b, c, ...
        const key = counts.join('#');
        
        if (!groups.has(key)) {
            groups.set(key, []);
        }
        groups.get(key)!.push(str);
    }
    
    return [...groups.values()];
}
 
// Example
const words = ["eat", "tea", "tan", "ate", "nat", "bat"];
console.log(groupAnagramsSorting(words));
// [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
 
// Trace the counting approach:
// "eat" → counts = [1,0,0,0,1,0,...,1,...] (a:1, e:1, t:1)
// Key = "1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0"
// "tea" → same counts → same key → grouped with "eat"

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
67
68
69
70
71
72
73

/**
 * Check if two strings are isomorphic
 * Time: O(n), Space: O(n)
 */
function isIsomorphic(s: string, t: string): boolean {
    if (s.length !== t.length) return false;
    
    // Pattern: encode each position as the index of first occurrence
    const patternize = (str: string): string => {
        const firstOccurrence = new Map<string, number>();
        const pattern: number[] = [];
        
        for (let i = 0; i < str.length; i++) {
            const char = str[i];
            if (!firstOccurrence.has(char)) {
                firstOccurrence.set(char, i);
            }
            pattern.push(firstOccurrence.get(char)!);
        }
        
        return pattern.join(',');
    };
    
    return patternize(s) === patternize(t);
}
 
// Examples:
// "egg" → pattern [0, 1, 1] (e first seen at 0, g at 1, g at 1)
// "add" → pattern [0, 1, 1] (a first seen at 0, d at 1, d at 1)
// Same pattern → isomorphic!
 
// "foo" → pattern [0, 1, 1]
// "bar" → pattern [0, 1, 2] (all different)
// Different patterns → not isomorphic
 
console.log(isIsomorphic("egg", "add"));   // true
console.log(isIsomorphic("foo", "bar"));   // false
console.log(isIsomorphic("paper", "title")); // true
 
/**
 * Group Isomorphic Strings
 * Given a list of strings, group all isomorphic strings together
 */
function groupIsomorphic(strs: string[]): string[][] {
    const groups = new Map<string, string[]>();
    
    const patternize = (str: string): string => {
        const firstOccurrence = new Map<string, number>();
        const pattern: number[] = [];
        
        for (let i = 0; i < str.length; i++) {
            if (!firstOccurrence.has(str[i])) {
                firstOccurrence.set(str[i], i);
            }
            pattern.push(firstOccurrence.get(str[i])!);
        }
        
        return pattern.join(',');
    };
    
    for (const str of strs) {
        const key = patternize(str);
        if (!groups.has(key)) {
            groups.set(key, []);
        }
        groups.get(key)!.push(str);
    }
    
    return [...groups.values()];
}
 
console.log(groupIsomorphic(["egg", "add", "foo", "bar", "paper", "title"]));
// [["egg", "add"], ["foo"], ["bar"], ["paper", "title"]]

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

def word_pattern(pattern: str, s: str) -> bool:
    """
    Check if string follows the pattern.
    Time: O(n + m), Space: O(n)
    """
    words = s.split()
    
    if len(pattern) != len(words):
        return False
    
    # Two mappings needed: pattern → word AND word → pattern
    # Both must be bijective (one-to-one and onto)
    pattern_to_word = {}
    word_to_pattern = {}
    
    for char, word in zip(pattern, words):
        # Check pattern → word mapping
        if char in pattern_to_word:
            if pattern_to_word[char] != word:
                return False
        else:
            pattern_to_word[char] = word
        
        # Check word → pattern mapping
        if word in word_to_pattern:
            if word_to_pattern[word] != char:
                return False
        else:
            word_to_pattern[word] = char
    
    return True
 
 
def word_pattern_using_pattern(pattern: str, s: str) -> bool:
    """
    Alternative: Compare normalized patterns.
    """
    words = s.split()
    
    if len(pattern) != len(words):
        return False
    
    def normalize(items):
        mapping = {}
        result = []
        for item in items:
            if item not in mapping:
                mapping[item] = len(mapping)
            result.append(mapping[item])
        return tuple(result)
    
    return normalize(pattern) == normalize(words)
 
 
# Examples
print(word_pattern("abba", "dog cat cat dog"))  # True
print(word_pattern("abba", "dog cat cat fish")) # False
print(word_pattern("aaaa", "dog cat cat dog"))  # False (a→dog, a→cat conflict)

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

/**
 * Multi-level grouping with nested maps
 */
interface SaleRecord {
    year: number;
    month: number;
    product: string;
    amount: number;
}
 
function groupSalesMultiLevel(sales: SaleRecord[]): Map<number, Map<number, Map<string, SaleRecord[]>>> {
    const result = new Map<number, Map<number, Map<string, SaleRecord[]>>>();
    
    for (const sale of sales) {
        // Level 1: Year
        if (!result.has(sale.year)) {
            result.set(sale.year, new Map());
        }
        const yearMap = result.get(sale.year)!;
        
        // Level 2: Month
        if (!yearMap.has(sale.month)) {
            yearMap.set(sale.month, new Map());
        }
        const monthMap = yearMap.get(sale.month)!;
        
        // Level 3: Product
        if (!monthMap.has(sale.product)) {
            monthMap.set(sale.product, []);
        }
        monthMap.get(sale.product)!.push(sale);
    }
    
    return result;
}
 
/**
 * Generic multi-level grouping
 */
type KeyFunction<T> = (item: T) => string | number;
 
function groupByMultiple<T>(
    items: T[], 
    keyFns: KeyFunction<T>[]
): Map<any, any> {
    if (keyFns.length === 0) {
        throw new Error("At least one key function required");
    }
    
    if (keyFns.length === 1) {
        // Base case: single-level grouping
        const groups = new Map<any, T[]>();
        for (const item of items) {
            const key = keyFns[0](item);
            if (!groups.has(key)) {
                groups.set(key, []);
            }
            groups.get(key)!.push(item);
        }
        return groups;
    }
    
    // Recursive case: group by first key, then recursively group each bucket
    const firstLevel = new Map<any, T[]>();
    for (const item of items) {
        const key = keyFns[0](item);
        if (!firstLevel.has(key)) {
            firstLevel.set(key, []);
        }
        firstLevel.get(key)!.push(item);
    }
    
    const result = new Map<any, any>();
    for (const [key, group] of firstLevel) {
        result.set(key, groupByMultiple(group, keyFns.slice(1)));
    }
    
    return result;
}
 
// Example usage
const sales: SaleRecord[] = [
    { year: 2024, month: 1, product: 'Widget', amount: 100 },
    { year: 2024, month: 1, product: 'Gadget', amount: 200 },
    { year: 2024, month: 2, product: 'Widget', amount: 150 },
    { year: 2023, month: 12, product: 'Widget', amount: 90 },
];
 
const grouped = groupByMultiple(sales, [
    s => s.year,
    s => s.month,
    s => s.product
]);
 
// Navigate: grouped.get(2024).get(1).get('Widget') → [first sale]

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

from collections import defaultdict
from typing import List, Dict, Tuple
from dataclasses import dataclass
 
@dataclass
class SaleRecord:
    year: int
    month: int
    product: str
    amount: float
 
 
def group_by_composite_key(
    sales: List[SaleRecord]
) -> Dict[Tuple[int, int, str], List[SaleRecord]]:
    """
    Single-level grouping with composite key.
    Often simpler than nested maps.
    """
    groups = defaultdict(list)
    
    for sale in sales:
        key = (sale.year, sale.month, sale.product)
        groups[key].append(sale)
    
    return dict(groups)
 
 
def aggregate_by_composite_key(
    sales: List[SaleRecord]
) -> Dict[Tuple[int, int], float]:
    """
    Group and aggregate in one pass.
    Sum amounts by (year, month).
    """
    totals = defaultdict(float)
    
    for sale in sales:
        key = (sale.year, sale.month)
        totals[key] += sale.amount
    
    return dict(totals)
 
 
# Example
sales = [
    SaleRecord(2024, 1, 'Widget', 100),
    SaleRecord(2024, 1, 'Gadget', 200),
    SaleRecord(2024, 1, 'Widget', 50),
    SaleRecord(2024, 2, 'Widget', 150),
]
 
# Group by all three dimensions
by_all = group_by_composite_key(sales)
print(by_all[(2024, 1, 'Widget')])  # [SaleRecord(2024,1,Widget,100), SaleRecord(2024,1,Widget,50)]
 
# Aggregate by year and month
monthly_totals = aggregate_by_composite_key(sales)
print(monthly_totals)  # {(2024, 1): 350.0, (2024, 2): 150.0}

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
67
68
69
70
71
72
73

/**
 * Generic group and aggregate
 */
function groupAndAggregate<T, K, R>(
    items: T[],
    keyFn: (item: T) => K,
    aggregator: (group: T[]) => R
): Map<K, R> {
    // First, group
    const groups = new Map<K, T[]>();
    for (const item of items) {
        const key = keyFn(item);
        if (!groups.has(key)) {
            groups.set(key, []);
        }
        groups.get(key)!.push(item);
    }
    
    // Then, aggregate each group
    const result = new Map<K, R>();
    for (const [key, group] of groups) {
        result.set(key, aggregator(group));
    }
    
    return result;
}
 
// Example: Calculate statistics per category
interface Product {
    category: string;
    name: string;
    price: number;
}
 
const products: Product[] = [
    { category: 'Electronics', name: 'Phone', price: 999 },
    { category: 'Electronics', name: 'Tablet', price: 599 },
    { category: 'Clothing', name: 'Shirt', price: 49 },
    { category: 'Clothing', name: 'Pants', price: 79 },
    { category: 'Electronics', name: 'Laptop', price: 1299 },
];
 
// Sum prices per category
const sumByCategory = groupAndAggregate(
    products,
    p => p.category,
    group => group.reduce((sum, p) => sum + p.price, 0)
);
console.log(sumByCategory);
// Map { 'Electronics' => 2897, 'Clothing' => 128 }
 
// Statistics per category
interface Stats {
    count: number;
    sum: number;
    avg: number;
    min: number;
    max: number;
}
 
const statsByCategory = groupAndAggregate<Product, string, Stats>(
    products,
    p => p.category,
    group => ({
        count: group.length,
        sum: group.reduce((s, p) => s + p.price, 0),
        avg: group.reduce((s, p) => s + p.price, 0) / group.length,
        min: Math.min(...group.map(p => p.price)),
        max: Math.max(...group.map(p => p.price)),
    })
);
console.log(statsByCategory.get('Electronics'));
// { count: 3, sum: 2897, avg: 965.67, min: 599, max: 1299 }