Frequency Map
When a question is about how often things occur, or whether something has occurred before, a map from value to count answers it in one pass. Every element costs one O(1) bump, and the answer is read straight off the map: seen before is a lookup, most common is the biggest count, all unique is every count being one.
Find the first value that has appeared before. Keep a set of what has been seen. Each value is one lookup and one insert, so the pass is O(n) instead of comparing every pair.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 4, with their answers.
Set is {}. Is 3 seen before?
Answer: New. 3 has not appeared yet.
Set is {3}. Is 7 seen before?
Answer: New. 7 has not appeared yet.
Set is {3, 7}. Is 1 seen before?
Answer: New. 1 has not appeared yet.
Set is {3, 7, 1}. Is 7 seen before?
Answer: Seen before. 7 went into the set at index 1.
How it runs, step by step
Find the first value that has appeared before. Keep a set of what has been seen. Each value is one lookup and one insert, so the pass is O(n) instead of comparing every pair.
Finding the first repeated value with a set of values seen so far.
3 is not in the set. Add it and move on. 1 distinct so far.
3 is new and is added to the set.
7 is not in the set. Add it and move on. 2 distinct so far.
7 is new and is added to the set.
1 is not in the set. Add it and move on. 3 distinct so far.
1 is new and is added to the set.
7 is in the set already, from index 1. That is the first repeat, found in 4 lookups.
7 was seen before at index 1.
First repeat: 7. One pass with a set, O(n) time and O(n) space, against O(n squared) for checking every pair. That trade is the pattern.
The first repeated value is 7.
Write it yourself
Define firstRepeat(values) and return the first value that appears a second time, or -1 when none does. It runs in your browser against this lesson's own 2 examples.
// Remember what you have seen. The answer is the first value you see twice, not the first value that has a duplicate later.function firstRepeat(values) { return -1;}
Remember
- Reach for a frequency map on counting, grouping, anagram and seen-before questions.
- One pass, one O(1) bump per element: O(n) time, O(distinct values) space.
- It trades memory for the nested loop you would otherwise write.
Topics covered
Where this is used
CompressionHuffman coding in gzip, zip and PNG
A DEFLATE encoder writing a dynamic Huffman block counts how often each literal, match length and distance symbol occurs in that block, then builds a code that gives the frequent symbols the shortest bit patterns. The counting has to finish before the block's first compressed bit is emitted, because you cannot know which symbols deserve the short codes until you have seen them all, and the code lengths are written into the block header so the decoder can rebuild the same tree. DEFLATE also offers a fixed block whose table is predefined in the spec, which skips the counting pass and usually pays for it in size.
DatabasesGROUP BY as a hash aggregate
Ask PostgreSQL for SELECT country, count(*) FROM users GROUP BY country and EXPLAIN usually shows a HashAggregate node: one hash table from group key to running count, one probe and bump per row, one pass, no sort. How large that table grows is the O(distinct) cost, and work_mem is what bounds it. Before version 13 the planner refused a HashAggregate it estimated would not fit and took the sort-based GroupAggregate instead; since 13 the hash table can spill partitions to disk, so the two plans are costed against each other and an underestimated group count surfaces as an unexpected spill rather than a rejected plan.
SearchTerm frequencies in a Lucene index
Indexing a document in Lucene, and so in Elasticsearch or Solr, builds a map from term to occurrence count for that document, and those counts are written into the postings list next to the document id. BM25 scoring reads them back at query time: a word appearing eight times in a document is evidence the document is about that word. The counting happens once at index time so that ranking at query time is only a lookup.
Streaming dataCount-Min Sketch when the exact map will not fit
Counting requests per IP or views per URL across billions of distinct keys needs one map entry per key, which stops fitting in memory. Redis answers with CMS.INCRBY, from the RedisBloom module that ships in Redis Stack: a fixed grid of counters where each key hashes to one counter per row, and the estimate is the smallest of those counters. Memory is capped up front, and the price is that collisions can only ever inflate a count, never deflate it.
Why it works this way
Why a hash map and not an array of counts?
If the keys are small bounded integers, or the 26 lowercase letters, an array is strictly better: index arithmetic instead of hashing, no boxing of keys and values, contiguous memory the cache likes, and iteration in key order for free. The hash map earns its cost only when the key space is huge, sparse, or not an integer at all. An anagram check on lowercase words wants IntArray(26), not HashMap<Char, Int>.
The classic bug: bumping a key that is not there yet
The first time a value appears there is no entry to add one to. Java's map.get(v) + 1 returns null and throws NullPointerException while unboxing, Python's counts[v] += 1 raises KeyError, and Kotlin will not even compile counts[v] + 1 because the type is Int?. That is what the ?: 0 in the code is defending against; getOrDefault, merge(v, 1, Integer::sum), getOrPut, defaultdict(int) and Counter are the same defence with less typing.
Why first-repeat uses a set but most-common needs a map
first-repeat only asks have I seen this, so membership is enough and a set carries no counter per entry. More importantly it can return the moment the answer is known, often after reading only part of the array. most-common has to read every element before it can name a winner, because the last value could still tie or overtake, so there is no early exit to take.
A tie has no winner, and map order will not pick one for you
On [4, 9, 4, 9, 1] both 4 and 9 appear twice, and maxBy returns whichever the iterator reaches first. A HashMap's iteration order follows hash codes and current capacity, not insertion order, and it is not part of the contract. Small Integer keys hash to themselves, so tests often come out in neat ascending order and then break when the keys change type or the map resizes. If the tie must resolve a particular way, say so in the comparison instead of trusting the map.
Read more
- collections.CounterPython docs · docs.python.org
- Huffman codingWikipedia
- Boyer-Moore majority vote algorithmWikipedia
- Count-min sketchWikipedia
- Using EXPLAINPostgreSQL docs · postgresql.org