Frequency maps, sets and hashing techniques

Count, deduplicate and group with hash containers, use the two-sum and prefix-sum patterns, and know when sorting beats hashing.

Frequency maps and sets

from collections import Counter, defaultdict
from typing import Iterable, Sequence

def frequencies(xs: Iterable[str]) -> dict[str, int]:
    """Counter does the bookkeeping; most_common sorts for you."""
    return dict(Counter(xs).most_common())

def first_duplicate(xs: Sequence[int]) -> int | None:
    """A set turns a nested loop into a single pass."""
    seen: set[int] = set()
    for x in xs:
        if x in seen:
            return x
        seen.add(x)
    return None

def group_by_length(words: Iterable[str]) -> dict[int, list[str]]:
    groups: dict[int, list[str]] = defaultdict(list)
    for w in words:
        groups[len(w)].append(w)      # defaultdict removes the existence test
    return dict(groups)

def is_anagram(a: str, b: str) -> bool:
    """Counter equality is the clean form; a sort is also O(n log n)."""
    if len(a) != len(b):
        return False
    return Counter(a) == Counter(b)

def top_k_frequent(xs: Sequence[str], k: int) -> list[str]:
    """Counter plus heapq: O(n log k), better than sorting all n when k is small."""
    import heapq
    counts = Counter(xs)
    return [word for word, _ in heapq.nlargest(k, counts.items(), key=lambda kv: kv[1])]


if __name__ == "__main__":
    print(frequencies("mississippi"))
    print(first_duplicate([1, 2, 3, 2]))
    print(group_by_length(["a", "bb", "cc", "ddd"]))
    print(is_anagram("listen", "silent"))
    print(top_k_frequent(["a", "b", "a", "c", "a", "b"], 2))

• A hash container gives average O(1) per operation and O(n) worst case, which an adversary can trigger if the hash function is predictable and the keys come from user input.
• defaultdict(list) and setdefault both remove the pattern of testing for a key and then creating the container. Prefer the one that reads more clearly for the situation.
• A set of keys uses memory proportional to the input, which is the real cost. An in-place sort uses O(log n) extra space and needs no additional structure.
• Iteration order of a hash container is unspecified. Sort the output if the result is compared or displayed.

Two-sum and complement maps

from typing import Sequence

def two_sum(nums: Sequence[int], target: int) -> tuple[int, int] | None:
    """One pass, O(n) time and O(n) space, using the complement as the key."""
    seen: dict[int, int] = {}                 # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return seen[need], i
        seen[x] = i
    return None

def two_sum_sorted(nums: Sequence[int], target: int) -> tuple[int, int] | None:
    """If the input is already sorted, two pointers use O(1) extra space."""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return lo, hi
        if s < target:
            lo += 1
        else:
            hi -= 1
    return None

def subarray_sum_zero(nums: Sequence[int]) -> tuple[int, int] | None:
    """A repeated prefix sum means the elements in between sum to zero."""
    first: dict[int, int] = {0: -1}
    running = 0
    for i, x in enumerate(nums):
        running += x
        if running in first:
            return first[running] + 1, i
        first[running] = i
    return None

def longest_unique_window(s: str) -> int:
    """A map from character to last index gives the sliding-window form."""
    last: dict[str, int] = {}
    best = start = 0
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1
        last[ch] = i
        best = max(best, i - start + 1)
    return best


if __name__ == "__main__":
    print(two_sum([2, 7, 11, 15], 9))          # (0, 1)
    print(two_sum_sorted([1, 2, 3, 4, 6], 9))  # (2, 4)
    print(subarray_sum_zero([1, 2, -3, 4]))    # (0, 2)
    print(longest_unique_window("abcabcbb"))   # 3

Choose hashing when you need membership or a complement lookup and the input order does not matter. Choose sorting when you also need order, neighbours, or a lower memory footprint, and when the extra log n factor is affordable.

Hazards and guarantees

# 1. Mutable and unhashable keys
#    key = [1, 2]        -> TypeError: unhashable type 'list'
key = (1, 2)             # a tuple is hashable if its elements are
# For a dict inside a key, freeze it: tuple(sorted(d.items()))

# 2. A custom __hash__ must agree with __eq__
class Point:
    __slots__ = ("x", "y")
    def __init__(self, x: int, y: int) -> None:
        self.x, self.y = x, y
    def __eq__(self, other: object) -> bool:
        return isinstance(other, Point) and (self.x, self.y) == (other.x, other.y)
    def __hash__(self) -> int:
        return hash((self.x, self.y))    # same fields as __eq__, or lookups fail

# 3. Floating point keys do not behave the way you expect
d = {0.1 + 0.2: "a"}
print(0.3 in d)          # False: 0.1 + 0.2 is not exactly 0.3
# Round or scale to integers for money and measurements.

# 4. Adversarial collisions
#    A hash function an attacker can predict lets them collide every key into
#    one bucket, degrading every operation to O(n). Python randomises string
#    hashing per process by default; do not disable it.

# 5. Memory: a dict of 1,000,000 small keys costs far more than a sorted list
#    of the same keys. Hashing buys time with space.

FAQ

Related

Two pointers, sliding window and prefix sums Complexity and Big-O in practice

Last refreshed 2026-09-18.