What a hash map buys you

A hash map trades memory and ordering for a lookup whose cost does not depend on how much is stored. x in a_list walks the list; x in a_set computes a hash, jumps to a bucket, and compares one or two keys. That is the cheapest change of complexity class available in an interview — O(n) per membership test becomes O(1) average, so the gap below grows with n instead of holding at a fixed multiple — and it arrives with two costs that are easy to forget under pressure.

What the average O(1) is made of

Hashing a key produces an integer, the integer picks a bucket, the bucket holds the key and its value. Nothing in that sequence grows with n, so one lookup is a hash plus one or two memory references — order 100 ns each on commodity hardware.

The difference is worth an arithmetic line. Testing 10⁵ values for membership against a list of 10⁵ elements is 10⁵ × 10⁵ = 10¹⁰ comparisons; at roughly 10⁸ simple operations per second, about 100 seconds. The same 10⁵ tests against a set are 10⁵ hashes and probes ≈ 10⁵ × 100 ns = 0.01 seconds. Four orders of magnitude, for one word's difference in how the container was built. This is the most common reason an otherwise correct solution is called too slow, and complexity by counting has the rest of that table.

One caveat on the "constant": hashing a key is O(length of the key). Hashing a 10⁵-character string is 10⁵ bytes of work, not one step. When your key is a string you build inside a loop, that construction is part of your complexity.

The two costs

No order. A Python dict iterates in insertion order — a language guarantee, and not the same thing as sorted order. Minimum, maximum, "the nearest key below t", and "how many keys lie between lo and hi" all cost a full scan, O(n) each. That is a large enough gap to be its own lesson: when you need order too.

Worst case O(n) per operation. The average assumes keys spread across buckets. Feed a table keys that all land in one bucket and every lookup degenerates to a scan of that bucket, so building the map becomes O(n²). CPython randomises string hashing per process, which removes the easy attack on string keys; integers hash to themselves, so integer keys spaced by a power of two cluster far more than random ones would. You will rarely hit this, and you should still say "O(1) average, O(n) worst case" out loud, because that qualifier is what the average actually means.

Prefix sums plus a map: O(n²) to O(n)

The single highest-value pattern in this module. The question: how many contiguous subarrays sum to exactly k? Values may be negative.

The brute force adds a running sum from every start:

def count_naive(a, k):
    total = 0
    for i in range(len(a)):
        s = 0
        for j in range(i, len(a)):
            s += a[j]
            if s == k:
                total += 1
    return total

That is O(n²) — about 5 × 10⁹ inner steps at n = 10⁵, roughly 50 seconds. Now name the waste, in the language of the solving loop: every start re-adds elements whose running total a previous start already computed.

Define the prefix sum P[j] = a[0] + … + a[j-1], with P[0] = 0. Then

sum(a[i:j]) = P[j] - P[i]

so sum(a[i:j]) == k is exactly P[i] == P[j] - k. The question stops being about subarrays and becomes: for each j, how many earlier i have that one prefix value? A counter of prefix values seen so far answers it in one step.

def count_subarrays(a, k):
    seen = {0: 1}            # the empty prefix: P = 0, counted once
    running = 0
    total = 0
    for x in a:
        running += x
        total += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return total

Counting subarrays that sum to k by looking up the earlier prefix P minus k100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

Why the seed is {0: 1}

P = 0 before you have read anything is a real prefix — the boundary at the very start of the array. A subarray that begins at index 0 and sums to k has running == k at its end, so the lookup asks for running - k == 0. If 0 is not already in the map with a count of one, every such subarray is missed.

Seeding with 0 instead of 1 is the same bug. It is the most common defect in this pattern, and it hides well: it only loses subarrays that start at the beginning, so hand-made examples often still pass.

Trace the diagram's array, a = [3, 4, 7, 2, -3, 1, 4, 2] with k = 7. The prefixes are 0, 3, 7, 14, 16, 13, 14, 18, 20. Four of them find a match: P = 7 finds the seed, P = 14 finds the earlier 7, the second P = 14 finds it again, and P = 20 finds 13. Answer: 4.

One pass, O(n) time and O(n) space. At n = 10⁵ that is 10⁵ iterations against 5 × 10⁹ inner steps. Each iteration does two dict operations, the get and the store, so at the 100 ns probe priced above: 2 × 10⁵ × 100 ns ≈ 20 milliseconds instead of about 50 seconds.

Negatives are the reason this beats a sliding window here. A window that grows and shrinks needs the sum to move monotonically with the window size, which requires non-negative values; prefix sums plus a map require nothing. The same skeleton also counts subarrays whose sum is divisible by k (key on running % k) and finds the longest subarray with sum k (store the first index of each prefix instead of a count).

Frequency counting and canonical keys

Two jobs, one structure. Frequencies are collections.Counter. Grouping is the more interesting one: pick a key that is identical for every member of a group and different for everything else.

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = tuple(sorted(w))       # 'eat' and 'tea' both become ('a', 'e', 't')
        groups[key].append(w)
    return list(groups.values())

Sorting each word costs O(L log L), so the whole pass is O(n · L log L) — at 10⁴ words of length 10 that is 10⁴ × 10 × 3.3 ≈ 3 × 10⁵ steps, nothing. If the words are long, a 26-slot count tuple is a canonical key in O(L):

counts = [0] * 26
for ch in w:
    counts[ord(ch) - 97] += 1
key = tuple(counts)

What the pattern needs is not sorting; it is canonical: equal inputs give equal keys, unequal inputs give unequal keys.

Keys that break

A list is unhashable, because its hash would change when it changed:

visited = set()
visited.add([r, c])     # TypeError: unhashable type: 'list'
visited.add((r, c))     # fine — tuples are immutable, so hashable

The exception is the kind outcome. The quiet one is a mutable key that Python does let you use: a custom object whose __hash__ reads a field you later change. The entry is still in the table, in the bucket its old hash chose, and no lookup will ever find it again. Nothing raises. Keep keys immutable — tuple for a list, frozenset for a set, a sorted tuple of items for a dict — and the failure mode disappears.

In an interview

What is being tested is whether you reach for O(1) lookup at the right moment and whether you can price it honestly. Say the complexity with its qualifier: "O(n) average, O(n²) worst case if the keys are adversarial." Candidates who say only "O(1)" sound like they have memorised the headline.

For the prefix pattern, the sentence that earns the credit is the derivation, not the code: "sum(a[i:j]) is P[j] - P[i], so I want the number of earlier prefixes equal to P[j] - k. One pass with a counter, seeded with 0 once, because the empty prefix is real."

The mistake that loses points: claiming O(n) while building the key inside the loop with a sort or a join. tuple(sorted(w)) is O(L log L) per word and belongs in the number you state.

Check yourself

Count subarrays with sum k, values may be negative, n = 10⁵. What do you use, and what goes in the map before the loop starts?

A running prefix sum and a counter of prefix values, seeded with the value 0 counted once. At each step add the count of running - k, then record running. O(n) time and space. A sliding window is not legal here because negatives break the monotonicity it needs.

You seeded the map empty instead. Which inputs still give the right answer?

Every input where no qualifying subarray starts at index 0. That covers most short hand-written examples, which is exactly why the bug survives to submission. Test a = [k] and it fails immediately.

You group 10⁵ words by anagram with key = sorted(w). What happens, and what is the fix?

sorted returns a list, which is unhashable, so the first insertion raises TypeError. Use tuple(sorted(w)) or ''.join(sorted(w)). Both are canonical; the join gives the smaller, faster-hashing key — one compact L-byte string against a tuple of L pointers, and one contiguous buffer to hash instead of L objects to dereference.