Two Sum

Pattern: Hash Map (Dictionary)

How to Identify This Pattern?

When you see these signs in a problem, think Hash Map:

• Array is not sorted (sorting would take too long)
• Need to find a pair (or element) that complements another to reach a target
• Need fast O(1) lookups for "have I seen this before?"
• O(n) time complexity is preferred over O(n²)

Pattern Intuition: Instead of scanning the whole array for a partner (which is slow), store "what I need" or "what I've seen" in a lookup table for instant access.

Optimal Approach

Why Hash Map Works Here?

• We iterate through the array once.
• For every number num, we know exactly what we need: complement = target - num.
• A Hash Map lets us check if complement exists in O(1) time.
• This avoids nested loops, bringing complexity down from quadratic to linear.

Algorithm:

1. Initialize an empty Hash Map seen = {}.
2. Iterate through the array with index i and value num.
3. Calculate complement = target - num.
4. Check if complement is already in .