Hash Table Pattern

Relevant source files

Purpose and Scope

This document explains the hash table pattern as used throughout the repository's algorithm solutions. Hash tables (also known as hash maps, dictionaries, or associative arrays) provide constant-time average-case lookups and are fundamental to solving problems involving uniqueness checks, frequency counting, and value-to-index mappings.

For other algorithmic patterns, see:

Sliding Window techniques: Sliding Window Pattern
Two-pointer techniques: Two Pointers Pattern
Dynamic Programming approaches: Dynamic Programming Pattern

Hash Table Fundamentals

Hash tables store key-value pairs with $O(1)$ average-case time complexity for insertion, deletion, and lookup operations. The pattern is particularly effective when:

Fast lookups are required to check if an element exists
Counting occurrences of elements
Mapping values to their positions/indices
Detecting duplicates or unique elements

Trade-off: Hash tables use $O(n)$ space complexity, exchanging memory for speed compared to $O(n^2)$ brute-force approaches.

Pattern Taxonomy

Sources: solution/0000-0099/0001.Two Sum/README.md1-410 lcci/01.02.Check Permutation/README.md1-347 lcci/01.04.Palindrome Permutation/README.md1-298

Pattern 1: Value-to-Index Mapping

Problem: Two Sum

The canonical hash table problem. Given an array and a target, find two indices where values sum to the target.

Key Insight: Instead of checking all pairs ($O(n^2)$), store each value with its index in a hash table, then check if target - current_value exists.

Algorithm Flow

Sources: solution/0000-0099/0001.Two Sum/README.md67-78 solution/0000-0099/0001.Two Sum/README_EN.md64-74

Multi-Language Implementation

The pattern is consistent across all supported languages, using each language's native hash table implementation:

Language	Hash Table Type	Declaration	Lookup	Insert
Python	`dict`	`d = {}`	`y in d`	`d[x] = i`
Java	`HashMap<K,V>`	`Map<Integer, Integer> d = new HashMap<>()`	`d.containsKey(y)`	`d.put(x, i)`
C++	`unordered_map<K,V>`	`unordered_map<int, int> d`	`d.contains(y)`	`d[x] = i`
Go	`map[K]V`	`d := map[int]int{}`	`j, ok := d[y]`	`d[x] = i`
TypeScript	`Map<K,V>`	`const d = new Map<number, number>()`	`d.has(y)`	`d.set(x, i)`
Rust	`HashMap<K,V>`	`let mut d = HashMap::new()`	`d.get(&y)`	`d.insert(x, i)`

Implementation Examples:

Python: solution/0000-0099/0001.Two Sum/Solution.py1-8
Java: solution/0000-0099/0001.Two Sum/Solution.java1-13
C++: solution/0000-0099/0001.Two Sum/Solution.cpp1-14
Go: solution/0000-0099/0001.Two Sum/Solution.go1-11
TypeScript: solution/0000-0099/0001.Two Sum/Solution.ts1-11
Rust: solution/0000-0099/0001.Two Sum/Solution.rs1-15

Sources: solution/0000-0099/0001.Two Sum/Solution.py1-8 solution/0000-0099/0001.Two Sum/Solution.java1-13 solution/0000-0099/0001.Two Sum/Solution.cpp1-14 solution/0000-0099/0001.Two Sum/Solution.go1-11 solution/0000-0099/0001.Two Sum/Solution.ts1-11 solution/0000-0099/0001.Two Sum/Solution.rs1-15

Pattern 2: Frequency Counting

Problem: Check Permutation

Determine if one string is a permutation (rearrangement) of another by counting character frequencies.

Key Insight: Two strings are permutations if and only if they have identical character frequency distributions.

Algorithm Structure

Sources: lcci/01.02.Check Permutation/README.md40-56 lcci/01.02.Check Permutation/README_EN.md47-63

Implementation Details

Character Array Optimization: When the character set is constrained (e.g., lowercase English letters), use an array of size 26 instead of a hash table for better cache performance:

// Java implementation
int[] cnt = new int[26];
for (char c : s1.toCharArray()) {
    ++cnt[c - 'a'];  // Map 'a'→0, 'b'→1, ..., 'z'→25
}
for (char c : s2.toCharArray()) {
    if (--cnt[c - 'a'] < 0) {
        return false;
    }
}

Language-Specific Implementations:

Java (array-based): lcci/01.02.Check Permutation/Solution.java1-17
Python (Counter): lcci/01.02.Check Permutation/Solution.py1-3
TypeScript (object map): lcci/01.02.Check Permutation/Solution.ts1-16
Rust (vector-based): lcci/01.02.Check Permutation/Solution.rs1-22

Sources: lcci/01.02.Check Permutation/Solution.java1-17 lcci/01.02.Check Permutation/README.md44-56

Pattern 3: Palindrome Permutation Detection

Problem: Determine if String can form Palindrome

Check if a string's characters can be rearranged to form a palindrome.

Key Insight: A string can form a palindrome if and only if at most one character has an odd frequency count.

Two Hash Table Approaches

Sources: lcci/01.04.Palindrome Permutation/README.md36-157 lcci/01.04.Palindrome Permutation/README_EN.md33-156

Approach 1: Frequency Counting

Python Implementation using Counter:

The expression v & 1 efficiently checks if v is odd using bitwise AND.

Java Implementation:

Sources: lcci/01.04.Palindrome Permutation/Solution.py1-4 lcci/01.04.Palindrome Permutation/Solution.java1-12

Approach 2: Toggle Set Pattern

This approach optimizes space by only tracking characters with odd counts:

Add to set on first/third/fifth... occurrence (odd)
Remove from set on second/fourth/sixth... occurrence (even)
Final set size $< 2$ means valid palindrome permutation

Implementation Comparison:

Language	Set Type	Add Operation	Remove Operation	Check Size
Python	`set()`	`vis.add(c)`	`vis.remove(c)`	`len(vis) < 2`
Java	`HashSet<Character>`	`!vis.add(c)`	`vis.remove(c)`	`vis.size() < 2`
TypeScript	`Set<string>`	`vis.add(c)`	`vis.delete(c)`	`vis.size < 2`

Sources: lcci/01.04.Palindrome Permutation/README_EN.md160-292

Complexity Analysis Summary

Pattern	Time Complexity	Space Complexity	Use Case
Value-to-Index Mapping	$O(n)$	$O(n)$	Finding pairs, complements
Frequency Counting	$O(n)$	$O(k)$ where $k$ is charset size	Anagrams, permutations
Toggle Set	$O(n)$	$O(k)$ where $k$ is charset size	Parity checks

Key Observations:

Hash table operations (insert, lookup, delete) are $O(1)$ average case
Space complexity is often $O(k)$ where $k \ll n$ for constrained character sets
Single-pass algorithms are typical: iterate once through input data

Sources: solution/0000-0099/0001.Two Sum/README.md77 lcci/01.02.Check Permutation/README.md56 lcci/01.04.Palindrome Permutation/README.md43

Alternative: Bit Manipulation for Unique Characters

For problems with small character sets, bit manipulation can replace hash tables:

Problem: Is Unique

Bit Vector Approach: Use each bit in a 32-bit integer to represent one character's presence.

Java Implementation:

Advantages over Hash Table:

Space: $O(1)$ instead of $O(n)$
Faster bit operations vs hash function computation
No hash collision handling

Limitations:

Only works for small, bounded character sets (e.g., 26 lowercase letters)
Not applicable for arbitrary keys or large ranges

Sources: lcci/01.01.Is Unique/README.md42-50 lcci/01.01.Is Unique/Solution.java1-12 lcci/01.01.Is Unique/Solution.cpp1-14 lcci/01.01.Is Unique/Solution.go1-11

Language-Specific Hash Table APIs

Python

Dictionary: Native dict type with in operator for membership
Counter: collections.Counter for frequency counting with += support
Set: Native set type for unique elements

Java

HashMap: java.util.HashMap<K,V> with .containsKey(), .put(), .get()
Map.merge(): Convenient pattern cnt.merge(key, 1, Integer::sum) for counting

C++

unordered_map: std::unordered_map<K,V> from <unordered_map>
contains(): C++20 method for cleaner existence checks
unordered_set: std::unordered_set<T> for set operations

Go

map: Built-in map[KeyType]ValueType with comma-ok idiom: val, ok := m[key]
Zero value initialization: accessing non-existent key returns zero value

TypeScript/JavaScript

Map: new Map<K,V>() with .has(), .get(), .set()
Object: Plain objects {} work but less type-safe than Map
Set: new Set<T>() for unique elements

Rust

HashMap: std::collections::HashMap requires explicit import
Ownership: Must use .get(&key) (reference) not .get(key) (move)
Entry API: map.entry(key).or_insert(0) += 1 for clean counting

The hash table pattern appears in multiple problem series:

Standard LeetCode: solution/0000-0099/0001.Two Sum/
Cracking the Coding Interview: lcci/01.02.Check Permutation/ lcci/01.04.Palindrome Permutation/
Character Uniqueness: lcci/01.01.Is Unique/ (bit manipulation variant)

For problems requiring order preservation or range queries, consider:

Binary Search Pattern: Binary Search Pattern for sorted data
Sliding Window Pattern: Sliding Window Pattern for substring problems
Two Pointers Pattern: Two Pointers Pattern for in-place operations

Sources: Directory structure from Problem Organization and Problem Series