Hashing

Use hash-based lookup structures to trade space for fast membership, counting, or complement queries.

The seen structure always contains every element encountered before the current index while scanning forward.

By remembering values already seen, each element only needs to be examined once.

The cost of the lookup is constant per step, making the total cost linear regardless of input size.