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.
Max Value of Equation
Core idea: The
xvalues are sorted, so for any pairi < jwe havexj >= xiand the absolute value collapses:|xi - xj| = xj - xi. The equation becomes(yj + xj) + (yi - xi). As you sweepjleft to right,(yj + xj)is fixed, so you want the largest(yi - xi)among earlier points still inside the windowxj - xi <= k. That is a sliding-window maximum, and a monotonic deque does it: drop stale points off the front, drop dominated points off the back, and the best(y - x)is always at the front.
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