Frequency Map Window
A sliding window can only answer questions about itself if it keeps a summary. For distinct counts the summary is a frequency map: add on the way in, subtract on the way out, and a key disappears when its count hits zero. The size of the map decides whether the window shrinks.
Find the longest run holding at most 2 distinct values. The window grows to the right, a map counts what is inside, and the window shrinks from the left whenever the map has more than 2 keys.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 15, with their answers.
After 1 enters there are 1 distinct values, k is 2. What now?
Answer: Window is fine, grow right. 1 keys is within 2. The window stays and may grow further.
After 2 enters there are 2 distinct values, k is 2. What now?
Answer: Window is fine, grow right. 2 keys is within 2. The window stays and may grow further.
After 1 enters there are 2 distinct values, k is 2. What now?
Answer: Window is fine, grow right. 2 keys is within 2. The window stays and may grow further.
After 2 enters there are 2 distinct values, k is 2. What now?
Answer: Window is fine, grow right. 2 keys is within 2. The window stays and may grow further.
After 3 enters there are 3 distinct values, k is 2. What now?
Answer: Too many distinct, shrink left. The map has 3 keys and only 2 are allowed. Only dropping from the left can fix that.
After dropping 1 the map has 3 keys, k is 2. What now?
Answer: Too many distinct, shrink left. A count only reaching zero removes a key. 3 is still over 2.
After dropping 2 the map has 3 keys, k is 2. What now?
Answer: Too many distinct, shrink left. A count only reaching zero removes a key. 3 is still over 2.
After dropping 1 the map has 2 keys, k is 2. What now?
Answer: Window is fine, grow right. 2 keys fits in 2, so the window is valid again.
After 3 enters there are 2 distinct values, k is 2. What now?
Answer: Window is fine, grow right. 2 keys is within 2. The window stays and may grow further.
After 4 enters there are 3 distinct values, k is 2. What now?
Answer: Too many distinct, shrink left. The map has 3 keys and only 2 are allowed. Only dropping from the left can fix that.
After dropping 2 the map has 2 keys, k is 2. What now?
Answer: Window is fine, grow right. 2 keys fits in 2, so the window is valid again.
After 2 enters there are 3 distinct values, k is 2. What now?
Answer: Too many distinct, shrink left. The map has 3 keys and only 2 are allowed. Only dropping from the left can fix that.
After dropping 3 the map has 3 keys, k is 2. What now?
Answer: Too many distinct, shrink left. A count only reaching zero removes a key. 3 is still over 2.
After dropping 3 the map has 2 keys, k is 2. What now?
Answer: Window is fine, grow right. 2 keys fits in 2, so the window is valid again.
After 2 enters there are 2 distinct values, k is 2. What now?
Answer: Window is fine, grow right. 2 keys is within 2. The window stays and may grow further.
How it runs, step by step
Find the longest run holding at most 2 distinct values. The window grows to the right, a map counts what is inside, and the window shrinks from the left whenever the map has more than 2 keys.
Finding the longest window with at most 2 distinct values, using a frequency map.
Grow right to index 0. 1 enters, a new key, so the map now has 1 distinct. Within 2, so the window is valid.
The right end moves to index 0 and 1 enters. 1 distinct values inside. That is allowed.
Grow right to index 1. 2 enters, a new key, so the map now has 2 distinct. Within 2, so the window is valid.
The right end moves to index 1 and 2 enters. 2 distinct values inside. That is allowed.
Grow right to index 2. 1 enters, its count goes to 2. Within 2, so the window is valid.
The right end moves to index 2 and 1 enters. 2 distinct values inside. That is allowed.
Grow right to index 3. 2 enters, its count goes to 2. Within 2, so the window is valid.
The right end moves to index 3 and 2 enters. 2 distinct values inside. That is allowed.
Grow right to index 4. 3 enters, a new key, so the map now has 3 distinct. That is more than 2, so the left end must shrink.
The right end moves to index 4 and 3 enters. 3 distinct values inside. Too many, so the window shrinks.
Drop 1 from the left. Its count drops to 1, still inside, so the map keeps 3 keys. Still over 2, shrink again.
The left end moves to index 1, dropping 1. 3 distinct values remain. Still too many.
Drop 2 from the left. Its count drops to 1, still inside, so the map keeps 3 keys. Still over 2, shrink again.
The left end moves to index 2, dropping 2. 3 distinct values remain. Still too many.
Drop 1 from the left. Its count hits zero, so it leaves the map: 2 distinct now. Back within 2.
The left end moves to index 3, dropping 1. 2 distinct values remain.
Grow right to index 5. 3 enters, its count goes to 2. Within 2, so the window is valid.
The right end moves to index 5 and 3 enters. 2 distinct values inside. That is allowed.
Grow right to index 6. 4 enters, a new key, so the map now has 3 distinct. That is more than 2, so the left end must shrink.
The right end moves to index 6 and 4 enters. 3 distinct values inside. Too many, so the window shrinks.
Drop 2 from the left. Its count hits zero, so it leaves the map: 2 distinct now. Back within 2.
The left end moves to index 4, dropping 2. 2 distinct values remain.
Grow right to index 7. 2 enters, a new key, so the map now has 3 distinct. That is more than 2, so the left end must shrink.
The right end moves to index 7 and 2 enters. 3 distinct values inside. Too many, so the window shrinks.
Drop 3 from the left. Its count drops to 1, still inside, so the map keeps 3 keys. Still over 2, shrink again.
The left end moves to index 5, dropping 3. 3 distinct values remain. Still too many.
Drop 3 from the left. Its count hits zero, so it leaves the map: 2 distinct now. Back within 2.
The left end moves to index 6, dropping 3. 2 distinct values remain.
Grow right to index 8. 2 enters, its count goes to 2. Within 2, so the window is valid.
The right end moves to index 8 and 2 enters. 2 distinct values inside. That is allowed.
The longest window with at most 2 distinct values is indices 0 to 3, length 4. Each end moved forward only, 15 moves in all, so O(n), and the map answered every distinct-count question in O(1).
The longest window with at most 2 distinct values has length 4, from index 0 to 3.
Write it yourself
Define longestWithAtMostK(values, k) and return the length of the longest run holding at most k different values. It runs in your browser against this lesson's own 4 examples.
// Grow the window on the right, and while it holds more than k different values, shrink it from the left.function longestWithAtMostK(values, k) { return 0;}
Remember
- Count on entry, decrement on exit, remove the key at zero. Then map.size is the distinct count.
- Shrink from the left only while the map is over k. Both ends move forward only, so O(n).
- The same shape solves longest substring without repeats (k = 1 per key) and minimum window questions.
Topics covered
Related
Where this is used
CompressionMatch finding in gzip
DEFLATE compresses by pointing back at text it has already emitted, but only within a 32 KB window. zlib hashes each three-byte sequence to the recent positions where it occurred, inserting as bytes enter and clearing entries that fall behind the window as it slides. That eviction, together with a distance limit in the match search, is what keeps every back-reference inside the 32 KB the decompressor still holds.
NetworkingLinux connection tracking
nf_conntrack keys a hash table by connection tuple, adding a flow on its first packet and removing it when the flow times out. What the kernel caps is the number of tracked connections, not any single count: past nf_conntrack_max it drops packets and logs 'table full'. The size of the map is the signal, exactly as it is here. One connection costs two hash entries, one per direction, so a maxed-out table averages a chain length of two rather than one.
SecurityPort scan detection in Zeek
Zeek's SumStats framework collects per-source observations over a time window, and its unique reducer reports how many distinct destination ports or hosts one source touched. A scanner looks ordinary on packet volume and obvious on distinct count, so the detector fires on the size of the set rather than its total. Observations age out of the window the same way a count falls to zero and the key disappears.
AnalyticsUnique visitors in a rolling window
Counting distinct users over the last hour is this algorithm with time on the axis, and it works right up to the point where the keys stop fitting in memory. Redis answers the same question with PFADD and PFCOUNT in about 12 KB per counter at roughly 0.8% error, by hashing each key instead of storing it. The exact map is the correct tool for a window holding thousands of keys and the wrong one for a window holding billions.
Why it works this way
Why the key is deleted when its count hits zero
The code uses map.size as the distinct count, so a key left sitting at zero would still be counted and the window would keep shrinking for a value that already walked out. The alternative is to never delete and instead keep an integer you raise when a count goes from 0 to 1 and lower when it goes from 1 to 0. Both are correct. The bug is writing half of each, deleting keys and also keeping a counter that no longer agrees with them.
Why the shrink is a while and not an if
Adding one element can push the distinct count at most one over k, which tempts you into a single if. But moving left once does not always remove a key: if that leftmost value still appears further inside the window, its count only drops by one and the map is exactly as big as before. You have to keep moving left until some count actually reaches zero, which may take many steps.
At most k is easy, exactly k takes two boundaries
Pushing left forward can only lower the distinct count, so for a fixed right end the lefts that give at most k form a suffix and one pointer finds where it starts. The lefts that give exactly k form a band instead, between the at-most-k boundary and the at-most-(k - 1) boundary, which is why exactly k is usually answered by running this twice. For counting subarrays the identity is count(at most k) minus count(at most k - 1). That subtraction returns a number of subarrays, not a length, so it does not by itself give you the longest window with exactly k distinct - for that you track both boundaries and measure between them.
A hash map is not always the right map
When the values come from a small fixed alphabet - lowercase letters, bytes, DNA bases - an array of 26 or 256 counters beats a HashMap and does no hashing or resizing at all. An array has no map.size, so the separate distinct counter from the first note stops being optional. That is why the same algorithm appears as a HashMap in one solution and a 26-element array in the next.
Read more
- Count-distinct problemWikipedia
- Sliding WindowUSACO Guide
- Playlist - longest subarray of distinct valuesCSES 1141 · cses.fi
- HyperLogLogWikipedia
- nf_conntrack sysctl knobsLinux kernel documentation · kernel.org