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 both larger than something already in the deque and arrives later, that older element can never be the maximum again — the newcomer 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.

The one-line idea: 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 almost nothing 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 dominated on both axes and 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 amortisation 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 and the expression separates:

yi + yj + (xj - xi)  =  (yi - xi)  +  (yj + xj)
                        └─ past ─┘    └ present ┘

Now the left half depends only on points already seen, and the right half only on the current point. Maximising 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.
• Version control and rsync. Content-defined chunking rolls a hash over a byte stream to find stable chunk boundaries, so an insertion does not re-chunk the whole file.
• Intrusion detection. Signature scanning over packet streams uses rolling hashes to avoid re-reading each window.
• Stock and telemetry dashboards. "Rolling 30-day high" is the deque, and re-scanning each window is the naive implementation it replaces.
• Scheduling and admission control. Maximum load over any trailing window, maintained in O(1) amortised 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) space; worst case O(nm) under adversarial collisions.

▶ Max Value of Equation

Maximise yi + yj + |xi − xj| 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 and a base larger than the alphabet.
• 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. Equal values may both be kept, but if you keep them you must handle duplicate expiry carefully; evicting on <= is simpler and still correct.
• 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 outside xj − xi ≤ k must be popped from the front, exactly like a time-based expiry.

7. Key takeaways

1. A rolling hash makes substring search linear — subtract, shift, add, and verify on a hit.
2. A maximum cannot be rolled, because removal can take the answer with it. That is the entire reason the deque exists.
3. Dominated on both axes means dead. Smaller and older can never win again — the argument that licenses eviction.
4. Split the expression until one side is past-only. For Max Value of Equation the algebra, not the data structure, is the insight.
5. Amortised O(1) per step. Each index enters and leaves once, so inner pops do not make the scan quadratic.
6. 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.