S024 · Hashmaps & Sets — Hash Functions, Collisions

"""hashmaps.py — the canonical hashmap patterns + a mini hashmap from scratch.
 
Run:  python hashmaps.py
"""
from __future__ import annotations
from collections import defaultdict, Counter
 
 
# ------------------------------------------------------------------
# 1) Two Sum — the ‘complement lookup’ pattern
# ------------------------------------------------------------------
def two_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    """Return indices (i, j) with nums[i] + nums[j] == target. O(n) time."""
    seen: dict[int, int] = {}                # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:                     # O(1) lookup
            return seen[need], i
        seen[x] = i
    return None
 
 
# ------------------------------------------------------------------
# 2) Group Anagrams — the ‘group by key’ pattern
# ------------------------------------------------------------------
def group_anagrams(words: list[str]) -> list[list[str]]:
    """Group words that are anagrams of each other. Key = sorted characters."""
    groups: dict[tuple[str, ...], list[str]] = defaultdict(list)
    for w in words:
        key = tuple(sorted(w))
        groups[key].append(w)
    return list(groups.values())
 
 
# ------------------------------------------------------------------
# 3) Top-K frequent — the ‘count by key’ pattern
# ------------------------------------------------------------------
def top_k_frequent(nums: list[int], k: int) -> list[int]:
    counts = Counter(nums)
    return [val for val, _ in counts.most_common(k)]
 
 
# ------------------------------------------------------------------
# 4) Longest Consecutive Sequence — the ‘set as membership oracle’ pattern
# ------------------------------------------------------------------
def longest_consecutive(nums: list[int]) -> int:
    """Longest run of consecutive integers, in any order. O(n)."""
    pool = set(nums)
    best = 0
    for x in pool:
        # Only start counting from the LEFT end of a run.
        if x - 1 in pool:
            continue
        length = 1
        while x + length in pool:
            length += 1
        best = max(best, length)
    return best
 
 
# ------------------------------------------------------------------
# 5) Subarray Sum Equals K — the ‘prefix-sum + hashmap’ pattern
# ------------------------------------------------------------------
def subarray_sum_equals_k(nums: list[int], k: int) -> int:
    """Count contiguous subarrays whose sum == k. O(n).
 
    Trick: if prefix_sum[j] − prefix_sum[i-1] == k, that's a valid subarray.
    So we count, at each j, how many previous prefix sums equal prefix_sum[j] − k.
    """
    count = 0
    prefix = 0
    seen: dict[int, int] = {0: 1}            # sum 0 has occurred once (empty prefix)
    for x in nums:
        prefix += x
        count += seen.get(prefix - k, 0)     # O(1) lookup
        seen[prefix] = seen.get(prefix, 0) + 1
    return count
 
 
# ------------------------------------------------------------------
# 6) A toy hashmap — see the machinery
# ------------------------------------------------------------------
class MiniHashMap:
    """Open-addressing hashmap with linear probing. ~50 lines of the real thing."""
    _EMPTY = object()
    _TOMBSTONE = object()
 
    def __init__(self, capacity: int = 8) -> None:
        self._cap = capacity
        self._size = 0
        self._keys = [self._EMPTY] * capacity
        self._vals = [None] * capacity
 
    def _probe(self, key):
        """Yield indices to probe for `key`."""
        h = hash(key) & (self._cap - 1)      # cheap mod when cap is a power of 2
        for step in range(self._cap):
            yield (h + step) & (self._cap - 1)
 
    def __setitem__(self, key, value):
        if (self._size + 1) * 3 >= self._cap * 2:   # >2/3 full → resize
            self._resize()
        for idx in self._probe(key):
            slot = self._keys[idx]
            if slot is self._EMPTY or slot is self._TOMBSTONE or slot == key:
                if slot is self._EMPTY or slot is self._TOMBSTONE:
                    self._size += 1
                self._keys[idx] = key
                self._vals[idx] = value
                return
 
    def __getitem__(self, key):
        for idx in self._probe(key):
            slot = self._keys[idx]
            if slot is self._EMPTY:
                raise KeyError(key)
            if slot is not self._TOMBSTONE and slot == key:
                return self._vals[idx]
        raise KeyError(key)
 
    def _resize(self):
        old_keys, old_vals = self._keys, self._vals
        self._cap *= 2
        self._keys = [self._EMPTY] * self._cap
        self._vals = [None] * self._cap
        self._size = 0
        for k, v in zip(old_keys, old_vals):
            if k is not self._EMPTY and k is not self._TOMBSTONE:
                self[k] = v
 
 
if __name__ == "__main__":
    print("two_sum [2,7,11,15] target=9 :", two_sum([2, 7, 11, 15], 9))
    print("group_anagrams:", group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
    print("top_k [1,1,1,2,2,3] k=2 :", top_k_frequent([1, 1, 1, 2, 2, 3], 2))
    print("longest_consecutive [100,4,200,1,3,2] :", longest_consecutive([100, 4, 200, 1, 3, 2]))
    print("subarray_sum k=2 [1,1,1] :", subarray_sum_equals_k([1, 1, 1], 2))
 
    m = MiniHashMap()
    for w in "the quick brown fox jumps over the lazy dog".split():
        m[w] = m.__getitem__(w) + 1 if w in ("the",) and w in m._keys else 1
    print("MiniHashMap 'the' :", m["the"])
    print("MiniHashMap 'fox' :", m["fox"])