Hash Tables Pattern Guide for LeetCode

1. Core Hash Table Patterns

Template 1: Basic Frequency Counter

def frequency_counter_template(arr):
    counter = {}  # or collections.Counter(arr)

    # Count frequencies
    for item in arr:
        counter[item] = counter.get(item, 0) + 1

    return counter

Template 2: Two-Sum Pattern

def two_sum_template(arr, target):
    seen = {}  # val -> index

    for i, num in enumerate(arr):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

    return []

Template 3: Hash Map with Multiple Values

from collections import defaultdict

def multi_value_hash_template():
    # For storing multiple values per key
    hash_map = defaultdict(list)  # or defaultdict(set)

    # Adding values
    def add_value(key, value):
        hash_map[key].append(value)

    # Getting values
    def get_values(key):
        return hash_map[key]

2. LeetCode Problem Categories

Category 1: Frequency Based Problems

1. LeetCode 1: Two Sum

def twoSum(nums: List[int], target: int) -> List[int]:
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

1. LeetCode 242: Valid Anagram

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    char_count = {}

    # Count characters in first string
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1

    # Decrement counts for second string
    for char in t:
        if char not in char_count:
            return False
        char_count[char] -= 1
        if char_count[char] == 0:
            del char_count[char]

    return len(char_count) == 0

Category 2: Grouping Problems

1. LeetCode 49: Group Anagrams

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    groups = defaultdict(list)

    for s in strs:
        # Use sorted string as key
        key = ''.join(sorted(s))
        groups[key].append(s)

    return list(groups.values())

Category 3: Cache Implementation

1. LeetCode 146: LRU Cache

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> node
        self.dll = DoublyLinkedList()  # for O(1) remove

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1

        # Move to front (most recently used)
        node = self.cache[key]
        self.dll.remove(node)
        self.dll.add_to_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # Update existing & move to front
            node = self.cache[key]
            node.value = value
            self.dll.remove(node)
            self.dll.add_to_front(node)
        else:
            # Add new node
            node = Node(key, value)
            self.cache[key] = node
            self.dll.add_to_front(node)

            # Remove LRU if over capacity
            if len(self.cache) > self.capacity:
                lru = self.dll.remove_last()
                del self.cache[lru.key]