Hashing Problems

Hashing is often the first tool to reach for when you need to improve an algorithm's performance from O(n²) to O(n) by trading space for time.

1. Frequency Counting

Use a hash map to keep track of how many times each element appears.

2. Two-Sum (The Classic)

Given an array of integers and a target, find the indices of the two numbers that add up to the target.

3. Finding Duplicates

A set can check if we've seen an element before in O(1).

Key Performance Tip

Always check the Load Factor ($\alpha = n/m$) where $n$ is number of elements and $m$ is number of buckets. If $\alpha$ becomes too high (e.g., > 0.7), the performance degrades as collisions increase, requiring a Rehash.

Quiz