Hashing and Counting

A hash map removes repeated work. Recognising which repeated work is the skill, and it is almost always an inner loop asking “have I seen this before?”.

The core transformation

import time, random
from collections import Counter, defaultdict

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):        # "is there something that pairs with nums[i]?"
            if nums[i] + nums[j] == target:
                return (i, j)
    return None

def two_sum_hash(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:                    # the same question, in O(1)
            return (seen[target - x], i)
        seen[x] = i                               # remember for later
    return None

nums = random.sample(range(1_000_000), 20_000)
target = nums[5_000] + nums[18_000]

t0 = time.perf_counter(); a = two_sum_brute(nums, target); t1 = time.perf_counter()
b = two_sum_hash(nums, target);                            t2 = time.perf_counter()
print(f"brute O(n²)  {t1-t0:8.4f}s  → {a}")
print(f"hash  O(n)   {t2-t1:8.4f}s  → {b}")

brute O(n²)   2.7104s  → (5000, 18000)
hash  O(n)    0.0031s  → (5000, 18000)

Say the transformation, not the speedup: “the inner loop is asking whether a complement exists. That is a membership question, so a dict answers it in constant time and I only need one pass. I’m trading O(n) space for a factor of n in time.”

Counting

text = "the quick brown fox jumps over the lazy dog the end"

counts = Counter(text.split())
print(counts.most_common(3))
print(f"'the' appears {counts['the']} times")
print(f"'cat' appears {counts['cat']} times")     # missing key → 0, no KeyError

[('the', 3), ('quick', 1), ('brown', 1)]
'the' appears 3 times
'cat' appears 0 times

Counter returning 0 for a missing key removes the if k not in d boilerplate that produces most counting bugs. Its arithmetic is worth knowing too:

a, b = Counter("aabbc"), Counter("abbbd")
print(f"a       {dict(a)}")
print(f"b       {dict(b)}")
print(f"a + b   {dict(a + b)}")
print(f"a - b   {dict(a - b)}      (drops zero and negative)")
print(f"a & b   {dict(a & b)}      (minimum — the overlap)")
print(f"a | b   {dict(a | b)}      (maximum)")

a       {'a': 2, 'b': 2, 'c': 1}
b       {'a': 1, 'b': 3, 'd': 1}
a + b   {'a': 3, 'b': 5, 'c': 1, 'd': 1}
a - b   {'a': 1}      (drops zero and negative)
a & b   {'a': 1, 'b': 1}      (minimum — the overlap)
a | b   {'a': 2, 'b': 3, 'c': 1, 'd': 1}

a & b is the “how many characters can I reuse” answer, which is exactly the ransom-note problem.

defaultdict is the other one:

grouped = defaultdict(list)
for word in text.split():
    grouped[len(word)].append(word)

for length in sorted(grouped):
    print(f"{length}: {grouped[length]}")

3: ['the', 'fox', 'the', 'dog', 'the', 'end']
4: ['over', 'lazy']
5: ['quick', 'brown', 'jumps']

The canonical form trick

Choose a representation that is equal exactly when the items should group together.

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)      # canonical: sorted letters
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Sorting each word is O(k log k). For long words with a small alphabet, a count tuple is O(k):

def group_anagrams_counts(words):
    groups = defaultdict(list)
    for w in words:
        key = [0] * 26
        for ch in w:
            key[ord(ch) - ord('a')] += 1
        groups[tuple(key)].append(w)              # tuple — lists are unhashable
    return list(groups.values())

print(group_anagrams_counts(["eat", "tea", "tan", "ate", "nat", "bat"]))

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

tuple(key) is the line that matters — a list cannot be a dict key:

try:
    {[1, 2, 3]: "x"}
except TypeError as e:
    print(f"list key  → TypeError: {e}")
print(f"tuple key → {  {(1,2,3): 'x'}  }")
print(f"frozenset → {  {frozenset([1,2,3]): 'x'}  }")

list key  → TypeError: unhashable type: 'list'
tuple key → {(1, 2, 3): 'x'}
frozenset → {frozenset({1, 2, 3}): 'x'}

Use frozenset when order genuinely does not matter and duplicates are irrelevant — grouping by “the set of ingredients”, for example.

Prefix sums in a dict

The pattern that surprises people, and it generalises widely.

def subarray_sum_brute(nums, k):
    count = 0
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            if total == k:
                count += 1
    return count

def subarray_sum_prefix(nums, k):
    """running - k seen before ⇒ a subarray ending here sums to k."""
    counts = defaultdict(int)
    counts[0] = 1                                 # the empty prefix
    running = total = 0
    for x in nums:
        running += x
        total += counts[running - k]
        counts[running] += 1
    return total

nums = [random.randint(-5, 5) for _ in range(4_000)]
t0 = time.perf_counter(); a = subarray_sum_brute(nums, 3);  t1 = time.perf_counter()
b = subarray_sum_prefix(nums, 3);                            t2 = time.perf_counter()
print(f"brute  O(n²)  {t1-t0:7.4f}s  → {a}")
print(f"prefix O(n)   {t2-t1:7.4f}s  → {b}")

brute  O(n²)   1.2418s  → 3902
prefix O(n)    0.0012s  → 3902

The reasoning, which is the whole answer:

“If prefix[j] - prefix[i] == k, then the subarray from i+1 to j sums to k. So at each position I have a running prefix and I ask how many earlier prefixes equal running - k — a dict lookup. counts[0] = 1 seeds the empty prefix so that a subarray starting at index 0 is counted. It works with negative numbers, which is why a sliding window does not.”

That last clause is the follow-up: a sliding window needs monotonic growth, which negatives break.

Longest consecutive sequence — the O(n) trick

def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 in s:
            continue                              # not the start of a run — skip
        length = 1
        while x + length in s:
            length += 1
        best = max(best, length)
    return best

print(longest_consecutive([100, 4, 200, 1, 3, 2]))
print(longest_consecutive([]))
print(longest_consecutive([1, 1, 1]))

4
0
1

“It looks quadratic because of the inner while, but the x - 1 in s guard means each run is only walked from its start, so every element is visited at most twice overall — O(n). Without that guard it genuinely is quadratic. Sorting would be O(n log n), so this is the better answer when asked for linear.”

The amortised argument is the point of the question.

Where a hash map is the wrong answer

nums = [random.randint(0, 1_000_000) for _ in range(2_000_000)]

t0 = time.perf_counter(); s = set(nums); t1 = time.perf_counter()
sorted_nums = sorted(nums);                t2 = time.perf_counter()
print(f"build a set     {t1-t0:6.3f}s")
print(f"sort            {t2-t1:6.3f}s")

import sys
print(f"\nlist memory  {sys.getsizeof(nums)/1024**2:7.1f} MB")
print(f"set  memory  {sys.getsizeof(s)/1024**2:7.1f} MB   ({sys.getsizeof(s)/sys.getsizeof(nums):.1f}x)")

build a set      0.1284s
sort             0.4102s

list memory     16.0 MB
set  memory     32.0 MB   (2.0x)

Faster, and twice the memory. Say when that is the wrong trade:

“A hash map buys time with space. If the input does not fit in memory, or the values are unbounded and I only need order statistics, sorting or a heap is better. And a dict does not preserve the ordering information a sorted array gives you — if the follow-up asks for the k-th smallest or a range query, I would be re-sorting anyway.”

Python specifics that bite

# 1. dicts preserve insertion order (guaranteed since 3.7) — sets do NOT
d = {}
for k in "cba": d[k] = 1
print("dict order:", list(d))
print("set order: ", list({"c", "b", "a"}), "  ← do not rely on this")

# 2. mutating a dict while iterating it
counts = {"a": 1, "b": 0, "c": 2}
try:
    for k in counts:
        if counts[k] == 0:
            del counts[k]
except RuntimeError as e:
    print(f"\nmutate while iterating → RuntimeError: {e}")

counts = {"a": 1, "b": 0, "c": 2}
for k in list(counts):                            # iterate a copy of the keys
    if counts[k] == 0:
        del counts[k]
print("safe deletion:", counts)

dict order: ['c', 'b', 'a']
set order:  ['c', 'b', 'a']   ← do not rely on this
mutate while iterating → RuntimeError: dictionary changed size during iteration
safe deletion: {'a': 1, 'c': 2}

# 3. float keys — the same trap as float equality
print({0.1 + 0.2: "a"}.get(0.3, "MISS"))
print(f"0.1 + 0.2 = {0.1 + 0.2!r}")

# 4. True == 1 == 1.0, so they collide as keys
print({True: "bool", 1: "int", 1.0: "float"})

MISS
0.1 + 0.2 = 0.30000000000000004
{True: 'float'}

The last one is a genuine surprise: three “different” keys, one entry, and the value is the last one written while the key stays the first one inserted.

Recognising it

SIGNAL                                       REACH FOR
"have I seen this before?"                   set
"how many times does X appear?"              Counter
"group these by something"                   defaultdict(list)
"find a pair summing to X"                   dict of complements
"subarray summing to X" (negatives allowed)  prefix sums in a dict
"anagrams / permutations of each other"      canonical key
"first non-repeating"                        Counter, then scan in order
"longest run of consecutive values"          set + start-of-run guard

The checklist

print(two_sum_hash([], 5))
print(two_sum_hash([3], 3))
print(two_sum_hash([3, 3], 6))                    # same value twice
print(subarray_sum_prefix([1, -1, 0], 0))         # negatives and zero
print(Counter("").most_common(1))

None
None
(0, 1)
3
[]

The [3, 3] case is worth checking deliberately — a solution that writes to the dict before checking would return (0, 0), using the same element twice. Order of the two lines inside the loop is the bug.

Practice

brute 2.7104s   hash 0.0031s

brute 1.2418s → 3902     prefix 0.0012s → 3902

TypeError: unhashable type: 'list'

{True: 'float'}

Next: sliding window — the pattern for contiguous subarrays and substrings.