Rolling Hash and Window Max
What is this?
Both problems here break the comfortable assumption behind every simple window: that whatever you are tracking can be undone by subtraction. A sum can. A hash of a string can, with the right encoding. A maximum cannot. The element sliding out of the window might be the very thing you were reporting, and there is no arithmetic that recovers the second-best value you never stored.
So this chapter is about two states that need real design: one that rolls because it was built to, and one that survives by keeping a shortlist of everything still in the running.
Fun fact: the deque's eviction rule rests on a tiny, complete argument. If a new element is at least as large as something already in the deque and arrives later, that older element can never be the maximum again: the newcomer matches or beats it now and outlives it. Being dominated on both axes at once is what makes discarding it safe. Every monotonic-structure problem you will meet is some version of that same two-axis argument.
🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
In one line: a simple window updates its state by adding and subtracting. When that is impossible, either design a state that can be rolled (a polynomial hash) or keep a shortlist of surviving candidates (a monotonic deque), and in both cases each element is still touched a constant number of times.
1. Rolling hash
Treat a window of characters as a number in base b, modulo a large prime:
hash("abc") = a·b² + b·b¹ + c·b⁰
slide to "bcd":
subtract the leading term hash -= a·b²
shift everything up hash *= b
add the arrival hash += d
Three operations, no dependence on the window length. Two disciplines make it safe in practice: work modulo a large prime so the value cannot overflow, and treat a hash match as a candidate, not an answer: compare the actual characters before reporting. Collisions are rare, so verification costs little on average, but skipping it makes the algorithm wrong rather than merely slower.
2. Monotonic deque
Keep a deque of indices whose values are strictly decreasing.
- On arrival: pop from the back while the back's value is ≤ the newcomer's. Those are older and no larger, so they can be discarded forever.
- On expiry: if the front index has fallen out of the window, pop it from the front.
- To read the answer: the front is the maximum of the current window, always.
Every index is pushed once and popped once, so the pops inside the loop do not make it quadratic: the same amortized argument as the grow-and-shrink window.
3. The rewrite that makes Max Value of Equation a window problem
The problem asks for the maximum of yi + yj + |xi − xj| over pairs with xj − xi ≤ k. As written it is a pairwise scan. But points are sorted by x, so for i < j the absolute value resolves to xj − xi and the expression separates into (yj + xj) + (yi − xi):
Now the left half depends only on points already seen, and the right half only on the current point. Maximizing over the past inside a window is exactly what a deque does. The algebra is the insight; the deque is just the tool that becomes available once the expression is split.
4. Where you'll actually meet this
- Plagiarism and near-duplicate detection. Shingling hashes fixed-length windows of text; the rolling update is what makes it feasible over a corpus.
- rsync and backup tools. A rolling checksum over a byte stream finds blocks that match between two versions of a file, even when an insertion has shifted them.
- Stock and telemetry dashboards. A rolling 30-day high is the deque; re-scanning each window is the naive implementation it replaces.
- Scheduling and admission control. Maximum load over any trailing window, maintained in O(1) amortized per event.
5. Problems in this chapter
Implement Rabin-Karp
Substring search in linear average time. Hash the pattern once, roll a same-length window over the text, and do a full character comparison only when hashes agree.
Pattern: rolling polynomial hash. Target: O(n + m) average time, O(1) extra space; worst case O(nm) under adversarial collisions.
Max Value of Equation
Maximize yi + yj + |xi − xj| over pairs i < j subject to xj − xi ≤ k. Split the expression into a past term and a present term, then keep the best past term in a monotonic deque.
Pattern: algebraic split + monotonic deque. Target: O(n) time, O(n) space.
6. Common pitfalls
- Trusting a hash match. Always verify with a real comparison; otherwise the algorithm is probabilistic in a way the problem did not ask for.
- Overflow. Without a modulus the hash exceeds 64 bits quickly. Pick a large prime modulus and a base at least as large as the alphabet. In Java, C++ or JS, add the modulus back after a subtraction, since
%can return a negative number. - Forgetting to remove the leading term before shifting. Order matters: subtract, then multiply, then add.
- Storing values instead of indices in the deque. Expiry is positional: without indices you cannot tell when the front has left the window.
- Using
<instead of<=when evicting. Keeping equal values is also correct, but the deque then holds duplicates; evicting on<=keeps only the newer one, which stays in the window longer, and is simpler. - Checking expiry after reading the answer. Expire the front first, then read, or you may report a value that has already left.
- Forgetting the constraint window in Max Value of Equation. Points with
xj − xi > kmust be popped from the front, exactly like a time-based expiry.
7. Key takeaways
- A rolling hash makes substring search linear on average: subtract, shift, add, and verify on a hit.
- A maximum cannot be rolled, because removal can take the answer with it. That is the entire reason the deque exists.
- Dominated on both axes means dead. Older and no larger can never win again; that is the argument that licenses eviction.
- Split the expression until one side is past-only. For Max Value of Equation the algebra, not the data structure, is the insight.
- Amortised O(1) per step. Each index enters and leaves once, so inner pops do not make the scan quadratic.
- Why interviewers like it: everyone can slide a window; far fewer can say which statistics survive the slide and what to do when one does not.
Order: Implement Rabin-Karp → Max Value of Equation.
Implement Rabin-Karp
Core idea: Don't re-read a whole window of characters to test each position: summarize each window with a single number (a polynomial hash) and compare numbers instead of strings. As the window slides one step, you subtract the leaving character's contribution and add the entering one, so the hash updates in
O(1)rather thanO(m). Numbers can collide, so on a hash match you do one cheap char-by-char verification to confirm it's real.
Problem, rephrased
A plagiarism checker for an online code judge screens each incoming submission for a known fingerprint snippet. You're given two strings: text, the student's full submission, and pattern, the length-m snippet to hunt for.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson