Hash Map Lookups

Store what you need to find later

A hash map (Python dict) gives average O(1) insert and lookup. The pattern: iterate once, and for each element check whether something you saw earlier completes the answer (Two Sum checks for target - x), then record the current element. Sets answer "have I seen this?" for duplicates and membership. Note the worst case can degrade, and keys must be hashable (use tuples, not lists).

Remember what you have seen

Hash maps and prefix sums turn many quadratic array problems into single passes.

The Two Sum pattern

From the complexity example above.

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i

Check before inserting

Looking up before storing the current element avoids pairing an element with itself.

त्वरित जाँच: What is the average lookup time in a hash map?

• O(n)
• O(1)
• O(log n)
• O(n²)