Hashing and Frequency Counting
Use hash maps and sets to answer "have I seen this?" and "how many times?" in constant time, and turn pair-counting into a single pass.
The problem
Three questions come up constantly:
- Have I seen this value before?
- How many times has it appeared?
- How many earlier elements have some property that matches the current one?
All three are lookups by value. An array only helps when values are small whole numbers. When the value is 10^9, a string, or a pair, you need a different tool.
1 of 10