Hashing

#Topic: dict CRUD, get() default value, iteration patterns
#Time: O(1) average -- insert/delete/access
#Space: O(n) -- number of stored key-value pairs


def demo_crud() -> None:
    """Basic CRUD operations for dict."""
    print("=" * 50)
    print("dict CRUD")
    print("=" * 50)

    #Create
    d: dict[str, int] = {}
    d["apple"] = 3
    d["banana"] = 5
    d["cherry"] = 2
    print("After creation:", d)

    #Access -- KeyError when accessing a non-existent key
    print("d['apple']:", d["apple"])
    try:
        _ = d["grape"]
    except KeyError as e:
        print(f"KeyError occurred: {e}")

    #Safe access -- get()
    print("d.get('grape', 0) :", d.get("grape", 0))   #Default value 0
    print("d.get('apple', 0) :", d.get("apple", 0))   # 3

    #Update
    d["apple"] = 10
    print("After update:", d)

    #Delete
    del d["cherry"]
    print("After deletion:", d)

    removed = d.pop("banana", -1)
    print(f"pop('banana') = {removed}, remaining dict: {d}")


def demo_iteration() -> None:
    """dict iteration pattern."""
    print()
    print("=" * 50)
    print("Dict iteration")
    print("=" * 50)

    scores = {"Alice": 95, "Bob": 87, "Carol": 92, "David": 78}

    #Keys only
    print("keys()  :", list(scores.keys()))

    #Values only
    print("values():", list(scores.values()))

    #Key-value pairs
    print("items():")
    for name, score in scores.items():
        print(f"  {name}: {score}")

    #Sorted iteration
    print("Scores in descending order:")
    for name, score in sorted(scores.items(), key=lambda x: -x[1]):
        print(f"  {name}: {score}")


def demo_advanced_patterns() -> None:
    """Advanced dict pattern."""
    print()
    print("=" * 50)
    print("Advanced patterns")
    print("=" * 50)

    #setdefault -- set only when key is missing
    d: dict[str, list[int]] = {}
    for num in [1, 2, 1, 3, 2, 1]:
        key = "odd" if num % 2 else "even"
        d.setdefault(key, []).append(num)
    print("setdefault grouping:", d)

    # dict comprehension
    squares = {x: x ** 2 for x in range(1, 6)}
    print("squares:", squares)

    #Filtering
    large = {k: v for k, v in squares.items() if v > 9}
    print("v > 9 filter:", large)

    #Merge (Python 3.9+)
    a = {"x": 1, "y": 2}
    b = {"y": 20, "z": 3}
    merged = a | b   #b takes priority
    print("a | b:", merged)

    #frequency calculation
    words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
    freq: dict[str, int] = {}
    for w in words:
        freq[w] = freq.get(w, 0) + 1
    print("Frequency:", freq)
    print("Mode:", max(freq, key=freq.get))  # type: ignore[arg-type]


if __name__ == "__main__":
    demo_crud()
    demo_iteration()
    demo_advanced_patterns()

#Topic: set operations, frozenset, membership test
#Time: O(1) average -- add/remove/in
#Space: O(n) -- number of elements


def demo_set_basics() -> None:
    """set basic operation."""
    print("=" * 50)
    print("Basic set operations")
    print("=" * 50)

    s: set[int] = set()

    #Addition
    for v in [3, 1, 4, 1, 5, 9, 2, 6, 5]:
        s.add(v)
    print("After add (duplicates removed):", sorted(s))

    #Membership -- O(1)
    print("5 in s:", 5 in s)
    print("7 in s:", 7 in s)

    #Removal
    s.remove(1)           #KeyError if not present
    s.discard(100)        #OK even if not present
    print("After remove(1), discard(100):", sorted(s))

    #pop -- remove arbitrary element
    val = s.pop()
    print(f"pop() = {val}, remaining: {sorted(s)}")


def demo_set_operations() -> None:
    """Set operations -- union/intersection/difference/symmetric difference."""
    print()
    print("=" * 50)
    print("Set operations")
    print("=" * 50)

    A = {1, 2, 3, 4, 5}
    B = {3, 4, 5, 6, 7}
    print("A:", sorted(A))
    print("B:", sorted(B))

    print("A | B (union) :", sorted(A | B))
    print("A & B (intersection) :", sorted(A & B))
    print("A - B (difference) :", sorted(A - B))
    print("B - A (difference) :", sorted(B - A))
    print("A ^ B (symmetric difference) :", sorted(A ^ B))

    #Subset / Superset
    C = {1, 2, 3}
    print()
    print(f"{sorted(C)} <= {sorted(A)}: {C <= A}  (issubset)")
    print(f"{sorted(A)} >= {sorted(C)}: {A >= C}  (issuperset)")
    print(f"A.isdisjoint(B): {A.isdisjoint(B)}")  #Disjoint check

    D = {10, 20}
    print(f"A.isdisjoint(D={sorted(D)}): {A.isdisjoint(D)}")  # True


def demo_frozenset() -> None:
    """frozenset -- immutable set, can be used as a dict key."""
    print()
    print("=" * 50)
    print("frozenset")
    print("=" * 50)

    fs = frozenset([1, 2, 3, 2, 1])
    print("frozenset:", fs)
    print("1 in fs:", 1 in fs)

    #Use frozenset as dict key
    d: dict[frozenset[int], str] = {}
    d[frozenset([1, 2])] = "pair"
    d[frozenset([3, 4, 5])] = "triple"
    print("frozenset key dict:", d)

    #Supports set operations too
    fa = frozenset([1, 2, 3])
    fb = frozenset([2, 3, 4])
    print("fa & fb:", fa & fb)


def demo_performance() -> None:
    """Comparison of membership performance between set and list."""
    import time
    print()
    print("=" * 50)
    print("Membership performance: set vs list")
    print("=" * 50)

    n = 500_000
    data = list(range(n))
    target = n - 1  #Worst case

    # list -- O(n)
    t0 = time.perf_counter()
    _ = target in data
    list_time = time.perf_counter() - t0

    # set -- O(1)
    data_set = set(data)
    t0 = time.perf_counter()
    _ = target in data_set
    set_time = time.perf_counter() - t0

    print(f"list (O(n)): {list_time:.6f}s")
    print(f"set  (O(1)): {set_time:.6f}s")
    if set_time > 0 and set_time < list_time:
        print(f"set is about {list_time / set_time:.0f} times faster!")


if __name__ == "__main__":
    demo_set_basics()
    demo_set_operations()
    demo_frozenset()
    demo_performance()

#Topic : Counter -- Frequency calculation, most_common, arithmetic operations
#Time  : O(n) -- Creating Counter
#Space : O(k) -- k = Number of unique elements

from collections import Counter


def demo_counter_creation() -> None:
    """Various ways to create a Counter."""
    print("=" * 50)
    print("Create Counter")
    print("=" * 50)

    #String
    c1 = Counter("aababcabcd")
    print("String:", c1)

    #List
    c2 = Counter([1, 2, 1, 3, 2, 1])
    print("List:", c2)

    #Keyword arguments
    c3 = Counter(red=4, blue=2, green=1)
    print("Keywords:", c3)

    #From dict
    c4 = Counter({"a": 3, "b": 1})
    print("dict  :", c4)


def demo_most_common() -> None:
    """most_common -- the top K elements."""
    print()
    print("=" * 50)
    print("most_common")
    print("=" * 50)

    text = "the quick brown fox jumps over the lazy dog"
    word_cnt = Counter(text.split())
    print("Total:", word_cnt)
    print("Top 3:", word_cnt.most_common(3))
    print("Bottom 3:", word_cnt.most_common()[:-4:-1])  #Reverse slicing

    char_cnt = Counter(text.replace(" ", ""))
    print("Top 5 characters:", char_cnt.most_common(5))


def demo_arithmetic() -> None:
    """Counter arithmetic operation."""
    print()
    print("=" * 50)
    print("Counter arithmetic")
    print("=" * 50)

    c1 = Counter(a=4, b=2, c=0, d=-2)
    c2 = Counter(a=1, b=2, c=3)
    print("c1:", c1)
    print("c2:", c2)

    print("c1 + c2 (sum)  :", c1 + c2)   #Only positives
    print("c1 - c2 (difference)  :", c1 - c2)   #Only positives
    print("c1 & c2 (min) :", c1 & c2)   #Minimum value per key
    print("c1 | c2 (max) :", c1 | c2)   #Maximum value per key

    #subtract -- Including negatives
    c3 = Counter(a=4, b=2)
    c3.subtract(Counter(a=1, b=5))
    print("After subtract:", c3)   # a:3, b:-3

    #update -- Addition
    c4 = Counter(a=1)
    c4.update({"a": 2, "b": 3})
    print("After update:", c4)


def demo_practical_uses() -> None:
    """Practical usage patterns of counters."""
    print()
    print("=" * 50)
    print("Practical use")
    print("=" * 50)

    #1. Find duplicate elements
    nums = [1, 2, 3, 2, 4, 1, 5, 1]
    cnt = Counter(nums)
    duplicates = [n for n, c in cnt.items() if c > 1]
    print("Duplicate elements:", sorted(duplicates))

    #2. Number of unique elements
    print("Number of unique elements:", len(cnt))

    #3. Total sum
    print("Total number of elements:", sum(cnt.values()))

    #4. Check anagram
    def is_anagram(s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

    print("listen/silent anagram:", is_anagram("listen", "silent"))

    #5. Common elements of two lists (including duplicates)
    a = [1, 2, 2, 3, 4]
    b = [2, 2, 3, 3, 5]
    intersection = list((Counter(a) & Counter(b)).elements())
    print("Common elements (including duplicates):", sorted(intersection))


if __name__ == "__main__":
    demo_counter_creation()
    demo_most_common()
    demo_arithmetic()
    demo_practical_uses()

#Topic: Hash Applications -- Two-Sum, Anagram Group, Consecutive Sequence, Subarray Sum
#Time: O(n) -- Hash-based
#Space: O(n) -- Hash table size

from collections import Counter, defaultdict


def two_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    """Two-Sum: Return two indices whose sum is target -- O(n).

    Improve brute force O(n^2) to O(n) using a hash."""
    seen: dict[int, int] = {}   #{value: index}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return None


def group_anagrams(words: list[str]) -> list[list[str]]:
    """Group anagrams -- O(n * k log k), k = maximum word length.

    Use the sorted string as the key."""
    groups: dict[str, list[str]] = defaultdict(list)
    for word in words:
        key = "".join(sorted(word.lower()))
        groups[key].append(word)
    return list(groups.values())


def first_non_repeating(s: str) -> str:
    """Return the first unique character -- O(n)."""
    freq = Counter(s)
    for ch in s:
        if freq[ch] == 1:
            return ch
    return ""   #If none, empty string


def longest_consecutive_sequence(nums: list[int]) -> int:
    """Return the length of the longest consecutive sequence -- O(n).

    Achieve O(n) using a hash set without sorting."""
    num_set = set(nums)
    best = 0

    for num in num_set:
        if num - 1 not in num_set:    #Only search the starting point of the consecutive sequence
            cur = num
            length = 1
            while cur + 1 in num_set:
                cur += 1
                length += 1
            best = max(best, length)

    return best


def subarray_sum_equals_k(nums: list[int], k: int) -> int:
    """Return the number of subarrays with sum k -- O(n).

    Prefix sum + hash map pattern."""
    count = 0
    prefix_sum = 0
    prefix_cnt: dict[int, int] = defaultdict(int)
    prefix_cnt[0] = 1   #Cumulative sum of empty array = 0

    for num in nums:
        prefix_sum += num
        count += prefix_cnt[prefix_sum - k]
        prefix_cnt[prefix_sum] += 1

    return count


if __name__ == "__main__":
    print("=" * 55)
    print("Two-Sum")
    print("=" * 55)
    cases = [
        ([2, 7, 11, 15], 9,  (0, 1)),
        ([3, 2, 4],      6,  (1, 2)),
        ([3, 3],         6,  (0, 1)),
        ([1, 5, 3, 7],   8,  (1, 2)),
    ]
    for nums, target, expected in cases:
        result = two_sum(nums, target)
        ok = "OK" if result == expected else "NG"
        print(f"nums={nums}, target={target} -> {result}  {ok}")

    print()
    print("=" * 55)
    print("Grouping anagrams")
    print("=" * 55)
    words = ["eat", "tea", "tan", "ate", "nat", "bat"]
    groups = group_anagrams(words)
    print("Input:", words)
    for g in groups:
        print(" ", sorted(g))

    print()
    print("=" * 55)
    print("First unique character")
    print("=" * 55)
    for s in ["leetcode", "loveleetcode", "aabb"]:
        result = first_non_repeating(s)
        print(f"{s!r:15} -> {result!r}")

    print()
    print("=" * 55)
    print("Longest consecutive sequence")
    print("=" * 55)
    seq_cases = [
        ([100, 4, 200, 1, 3, 2], 4),
        ([0, 3, 7, 2, 5, 8, 4, 6, 0, 1], 9),
    ]
    for nums, expected in seq_cases:
        result = longest_consecutive_sequence(nums)
        ok = "OK" if result == expected else "NG"
        print(f"{nums} -> {result}  {ok}")

    print()
    print("=" * 55)
    print("Number of subarrays whose sum is k")
    print("=" * 55)
    sub_cases = [
        ([1, 1, 1], 2, 2),
        ([1, 2, 3], 3, 2),
    ]
    for nums, k, expected in sub_cases:
        result = subarray_sum_equals_k(nums, k)
        ok = "OK" if result == expected else "NG"
        print(f"nums={nums}, k={k} -> {result}  {ok}")