When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Pairs, counts, grouping, or membership
- Need to compare occurrences
When another approach fits better
- The input is already ordered and a constant-space boundary proof is central
- The key cannot be represented with stable equality or hashing
How it works#
For each item, scan the remaining or prior items to find a match, producing quadratic work in the common pair/grouping form.
Name the repeated question asked by the inner scan.
Store the smallest answer to that question while advancing once.
Choose check-before-update when the current element must not match itself.
InvariantThe table contains exactly the information from the processed prefix that a future element may need.
Example and template#
Two Sum
A direct introduction to complement lookup with a hash map.
Open the full problem brief- Prefix [2]
{2 → index 0}Only processed values are eligible.
- Read 7
need 2 → foundThe stored prefix answers the complement lookup directly.
table = empty map
for item in input:
key = required_complement_or_group(item)
if key in table:
consume(table[key], item)
update table with item- Time
- O(n) expected
- Space
- O(k)
- Assumptions
- Hash lookup/update is expected O(1); k is the number of distinct retained keys.
Pitfalls#
Common wrong approaches
It can let an element satisfy its own complement or distort a required prior count.
A raw list preserves data but not the direct lookup that removes the nested scan.
Edge cases
- Duplicate values
- Zero or negative keys
- Mutable or composite key representation
- Whether output order matters
Interview narration
- “The nested loop keeps asking whether the complement appeared earlier.”
- “My map represents only the processed prefix.”
- “I check first so this item cannot pair with itself, then record it.”
Practice#
Two Sum
A direct introduction to complement lookup with a hash map.
Practice this problemA stream of event IDs arrives; report the first ID whose third occurrence is seen.
Reveal the pattern decision
Use a frequency map because occurrence state is keyed by ID; ordering alone does not remove the lookup.
Transfer problem
Group log lines by a normalized signature while preserving first-seen group order.
Checkpoint: Define the signature and store group insertion order separately from membership/count state.
Follow-up variations
- Return all pairs without duplicating index pairs
- Handle an unbounded stream with an explicit retention policy
Error-log prompts
- What did each map value mean?
- Did my update order admit the current element?