Pick the right key.
Pay O(1).
Win.

Derived from brute force, not memorized

The canonical entry point is Two Sum (unsorted): given an array and a target, return indices of two elements that sum to the target. Don't jump to the solution — find the waste in the brute force first.

The O(n²) brute force

For every pair (i, j) with i < j, check if arr[i] + arr[j] == target. This is correct but wasteful: on each outer iteration at index i, you're linearly scanning the rest of the array to find the complement target - arr[i].

for i from 0 to n - 1:
    for j from i + 1 to n - 1:
        if arr[i] + arr[j] == target:
            return [i, j]           # found the pair

# what are we doing on every outer iteration i?
# scanning all j > i to ask: "is (target - arr[i]) anywhere in the rest?"
# that linear scan is the waste. if we already knew the answer in O(1), we'd save it.

Ask: what are we recomputing?

At each step i, we want to know: "Have I already seen the value target - arr[i]?" The inner loop answers this with a linear scan — O(n) work. If instead we had a structure that answers "have I seen X" in O(1), we'd reduce the total work to O(n). That structure is a hashmap: trade memory for the ability to answer membership queries in constant time.

The key-design question

Every hashmap solution requires answering exactly two questions: (1) what is the key? and (2) what is the value? The value is usually obvious (a count, an index, a list of indices). The key requires a design decision — and getting it wrong is the single most common source of wrong first attempts.

Where the naive key choice fails: Group Anagrams

Given a list of strings, group them so that all anagrams appear together. The naive approach: use each string itself as the hashmap key.

The fix is structural: instead of asking "what is this string?", ask "what does this string reduce to when we remove all ordering information?" That reduced form is the key. Two strings are anagrams if and only if they reduce to the same form.

The two-question decision matrix

Four canonical patterns

These four patterns cover virtually all hashmap interview problems. A given problem may layer two of them together (e.g., prefix sums + frequency counting in Subarray Sum Equals K), but the individual patterns are the building blocks.

Pattern 1 — Frequency counting

Build a map from element → count, then reason over the count structure. The canonical problem is Valid Anagram: two strings are anagrams iff their character-frequency maps are equal. Frequency counting is often a sub-step inside a larger algorithm rather than the final answer by itself.

# pass 1: build frequency map
freq = {}
for x in arr:
    freq[x] = freq.get(x, 0) + 1      # increment or initialize to 1

# pass 2: reason over the count map
for key, count in freq.items():
    # e.g., check if count > n//2 (majority element)
    # or compare against another freq map (anagram)
    # or find elements with count == 1 (first unique)

Pattern 2 — Complement / lookup (one-pass)

Process each element and ask: "have I already seen the thing I need to pair with this?" The map is built incrementally — store an element at step i, then check it at some later step j. This is one-pass because the map is populated and queried in the same scan.

Pattern 3 — Grouping by derived key

Compute a signature for each element and bucket elements sharing the same signature. The signature must be: (1) identical for all elements in the same group, and (2) different for elements in different groups. The design work is entirely in choosing the right signature function.

Common signature choices: sorted characters of a string (anagram grouping), a tuple of (char, count) pairs in canonical order (more collision-resistant than sorted string for Unicode), a prefix/suffix normalization, a hash of the element itself (content-addressing), or a composite tuple of multiple fields.

Pattern 4 — HashSet for existence / dedup

When you only need to ask "have I seen X" and never "how many times have I seen X", a HashSet is cleaner than a HashMap with dummy values. Two important sub-cases: (1) dedup while preserving order — iterate and add to an output list only if the element isn't in the set yet; (2) cycle detection — if a value recurs, a cycle exists (e.g., Happy Number problem). The set tracks visited states, not counts.

One-pass vs two-pass

Many candidates default to two-pass out of habit — build the full map, then query it. Two-pass is sometimes necessary (when you need global frequency information before you can answer any query), but one-pass is possible — and slightly more elegant — in a surprising number of cases.

When one-pass is valid

One-pass is valid when the question at each step is: "does the thing I need already exist among the elements I've processed before this point?" In Two Sum, at index i, you check if target - arr[i] is already in the map. If yes, the answer pair uses the element at i and some earlier element. The map at step i contains exactly arr[0..i-1]. This is correct because the pair consists of two distinct positions and we process them in order.

When two-pass is necessary

Two-pass is necessary when the query requires global information. Example: "find the first element whose frequency in the entire array is exactly 1." You can't answer this without knowing the final frequency of every element, which requires processing the entire array first. Similarly, "group anagrams" requires seeing all strings before you can assemble groups — though you can accumulate into buckets in one pass if you process one string at a time.

In practice: try one-pass first. If you find yourself needing to know about future elements to answer the current query, switch to two-pass.

Why O(1) holds (and when it doesn't)

Hash tables provide amortized O(1) average-case insertion and lookup. The word "amortized" and the qualifier "average-case" both carry real weight — interviewers at research-lab-tier companies occasionally probe this, and being caught flat-footed is avoidable.

How it works

A hash function maps a key to a bucket index: bucket = hash(key) % num_buckets. A perfect hash function spreads keys uniformly across all buckets — each lookup goes directly to the right bucket, O(1). Real hash functions are not perfect: two distinct keys can hash to the same bucket. This is a collision.

What to say in an interview

If an interviewer asks "what if the hash function is bad?", the complete answer is: average case O(1) holds under a uniform hash function and reasonable load factor. Worst case is O(n) per operation if all keys collide (adversarial input, birthday-paradox clustering). Real implementations defend with randomized hash seeds, so adversarial worst-case requires the attacker to know the seed. Java additionally converts degenerate buckets (8+ entries) to balanced BSTs, giving O(log n) worst case instead of O(n).

Widget A — "What's the key?" interactive trainer

Five problems. For each, choose what the correct key and value should be in the hashmap solution. The wrong choices are plausible — they'll compile and run, just give the wrong answer or wrong complexity. On selection, you'll see exactly why the wrong choice fails and why the right one succeeds.

Widget B — live hashmap build animator

Step through an array element by element. The hashmap panel updates live — watch insertions, hit-vs-miss lookups, and how the map's state changes at each step. Toggle between Two Sum (one-pass: build and check simultaneously) and frequency count (two-pass: populate first, then query) to see the structural difference in scanning order.

Widget C — hash table & collision visualizer

An 8-bucket hash table displayed as physical slots. Insert keys and watch them hash into buckets. Collisions are shown as chained entries in the same bucket — making the O(n) worst case visually obvious. Toggle between a good hash function (uniform distribution) and a deliberately bad one (everything lands in bucket 0) to see how quickly performance degrades.

Pattern recognition: the pre-code checklist

At Tier-1 interviews, the problem statement won't say "use a hashmap." The pattern has to be recognized from structural cues in the problem description. Internalize these triggers:

Hashmap patterns in real systems

The four interview patterns are not toy abstractions — each has a direct, non-trivial application in production systems. Recognizing them bridges the gap between interview performance and engineering judgment.

GROUP BY as bucketing by derived key. A tabular query tool's GROUP BY implementation is a direct, undisguised application of the grouping pattern: each row is hashed by its group-key column value, and rows sharing a key accumulate into the same bucket for aggregation — identical in structure to grouping anagrams by sorted characters, except the key is an existing column value rather than a computed signature. The aggregation function (SUM, COUNT, AVG) is then applied per bucket, exactly as frequency counting reduces a bucket's entries to a scalar.

UTXO set as O(1) existence check with a composite key. A ledger-style system that must answer "does this referenced output exist and is it still unspent?" on every incoming transaction is using a hashmap purely for O(1) existence and membership checking — structurally identical to a "have I seen this value before?" interview pattern, except the key is a composite of two fields (a transaction identifier and an output position index) rather than a single primitive value. This is itself a good illustration of the "key can be any deterministic derived value, including a tuple" principle from the grouping pattern.

Database hash indexes and hash joins. A hash index stores hash(column_value) → row_pointer, enabling O(1) equality lookups on that column — the database equivalent of a complement-lookup map. Hash join algorithms (used in query planning when two large tables need to be joined on a key) build a hash map from the smaller table's join key to its rows, then probe it for each row of the larger table — a textbook one-pass build-and-query pattern.

Content-addressed storage. Systems like Git, IPFS, and content delivery networks use the data's own hash as its key — the "key is a derived signature, not the raw value" principle applied at the storage level. Two files with identical content produce identical hashes, and identical hashes guarantee identical content (with cryptographic certainty). This is the grouping-by-derived-key pattern elevated to a storage model: the signature is the address.

Problem set — 10

Ordered easy to hard. All four sub-patterns are covered. Four problems explicitly reuse Widget A or Widget B (same visual vocabulary, different parameters). Problem 10 is a design/explain problem — the kind that appears at research-lab tier as a follow-up to a coding problem, not as the primary coding task.

Pseudocode templates

Four templates. Every annotation names a decision point you will encounter, not a formality. The fourth template (hash table insertion with chaining) makes Widget C's behavior legible as executable pseudocode.

function one_pass_complement(arr, target):
    seen = {}                           # maps: value → index it was seen at

    for i from 0 to len(arr) - 1:
        complement = target - arr[i]

        if complement in seen:           # O(1) lookup: have I seen what I need?
            return [seen[complement], i]  # yes — pair found

        seen[arr[i]] = i                # no — record this element for future queries
                                        # note: insert AFTER the lookup check
                                        # prevents pairing arr[i] with itself

    return None                         # no valid pair exists

# key: target - arr[i] (or arr[i] stored for complement lookup)
# value: index i
# one-pass valid because: we only need "seen before this position"

function freq_count_two_pass(arr):
    # pass 1: build frequency map over the ENTIRE input
    freq = {}
    for x in arr:
        freq[x] = freq.get(x, 0) + 1

    # pass 2: query the complete map
    result = []
    for x in arr:                       # or iterate over freq.items() if you want pairs
        if freq[x] == 1:               # example: find elements with frequency == 1
            result.append(x)
        # other queries: freq[x] > n // 2 (majority), max(freq.values()) (top K), etc.

    return result

# two-pass necessary when: the query requires knowing the FINAL count of every element
# (e.g., "first element with frequency 1" can only be answered after seeing all elements)

function group_by_signature(items):
    groups = {}                              # maps: signature → [list of items]

    for item in items:
        sig = compute_signature(item)        # THE design decision: what is the key?
                                             # anagrams: sorted(item)
                                             # numeric: item % k, item // k, abs(item)
                                             # strings: tuple(freq_map(item))
                                             # general: any deterministic fn of item

        if sig not in groups:
            groups[sig] = []
        groups[sig].append(item)             # bucket this item by its signature

    return list(groups.values())

# compute_signature must be:
#   (1) deterministic — same input always gives same signature
#   (2) same for all items in the same group
#   (3) different for items in different groups (no false groupings)

class HashTable:
    buckets = [[] for _ in range(num_buckets)]   # each bucket is a chain (list)
    size = 0
    LOAD_THRESHOLD = 0.75

    function insert(key, value):
        idx = hash(key) % len(buckets)              # map key to bucket index
        chain = buckets[idx]

        for entry in chain:                         # check for existing key (update)
            if entry.key == key:
                entry.value = value
                return

        chain.append({key: key, value: value})      # collision: append to chain
        size += 1

        if size / len(buckets) > LOAD_THRESHOLD:    # O(n) rehash amortized to O(1)
            rehash()

    function lookup(key):
        idx = hash(key) % len(buckets)
        for entry in buckets[idx]:                  # scan chain at this bucket
            if entry.key == key: return entry.value
        return None                                 # key not found

    # lookup cost: O(1) average (chain length ~1), O(n) worst case (all keys collide)
    # amortized O(1) insert: most inserts are O(1); rehash is O(n) but rare

Further reading