Arrays & Hashing

How it works

Think of a hash map as a memory you can query in constant time. Almost every brute-force array solution repeats one expensive question inside a loop: is there an earlier element that completes this one? Storing what you have already seen turns that inner scan into a single lookup.

It works because the question can be phrased as an exact key. Pair sums become 'have I seen target minus x', duplicates become 'is x already in the set', and grouping becomes 'which bucket does this key belong to'. Once the question is a key, the hash structure answers it without caring how many items came before.

The pattern hides behind words like count, group, frequency, first unique, or 'in one pass'. It also hides in prefix sums: a subarray summing to k is just two prefix sums that differ by k, which is the pair-sum lookup again.

The real skill is choosing the key. A sorted string, a tuple of character counts, a running sum, a remainder modulo k: the right signature collapses many different-looking inputs into one bucket.

How to attack it

1. 1Write the brute force and name the question the inner loop keeps asking.
2. 2Rephrase that question as a lookup on an exact key.
3. 3Decide what the map stores per key: a boolean, a count, an index, or a list.
4. 4Decide the order: look up before inserting the current element, or after.
5. 5Handle the empty input and repeated values, then confirm one pass is enough.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

def one_pass_lookup(nums, target):
    # Maps a value (or a derived key) to what we need later: here, its index.
    seen = {}
    for i, x in enumerate(nums):
        need = target - x  # the key that would complete the current element
        if need in seen:
            return [seen[need], i]
        # Insert AFTER the lookup so an element never pairs with itself.
        seen[x] = i
    return []


def group_by_signature(items):
    groups = {}
    for item in items:
        key = "".join(sorted(item))  # choose a signature shared by the group
        groups.setdefault(key, []).append(item)
    return list(groups.values())

What it costs