Sliding window

Two hundred thousand OTPs for one phone

Payment OTPs (the one-time codes sent by text message) are taking nine seconds to arrive, and the cause is found within ten minutes. A merchant's test script is stuck in a retry loop, asking for OTPs for one phone number about 300 times a second. The rate limiter allows at most 5 OTPs per phone in any 60 seconds, so it is correctly refusing them. The trouble is how it decides. It keeps every request the phone has made today, and on each new request it reads the whole list to count how many fall in the last 60 seconds.

Work out the cost. That phone's list is 200,000 requests long. 300 requests a second, each reading 200,000 timestamps, is 60 million checks a second, and every other customer's OTP waits behind them.

The oldest entry on the list is six hours old. It stopped mattering a minute after it arrived, and the limiter has read it 200,000 times since.

Pause and predict A request made at 16:00:05 is more than 60 seconds before a request made at 16:01:07, so it does not count towards that request's limit. Could it count towards the limit of any request made after 16:01:07?

Once a start is ruled out, it stays ruled out

A string of length n has about n²/2 substrings. The brute-force method checks each one, so even if each check costs O(1), the total is quadratic.

A window is one substring, written [l, r]: it starts at index l and ends at index r. The sliding window checks far fewer windows than that. It is allowed to skip the rest because of one property of the rule the window must meet.

Take the rule "no character appears twice". If [l, r] already has a repeated character, then any larger window that contains [l, r] has that repeat too. So once a window breaks the rule, every larger window around it also breaks it. A rule with this property is called monotone.

The same argument gives the cost. r moves right n times. l moves right at most n times in total over the whole run, because it never moves back. The inner while loop looks as if it makes the code quadratic, but its cost is amortised over the run: each index enters the window once and leaves at most once, so the loops take at most 2n steps together.

Two shapes, one argument

For "longest" problems, breaking the rule carries over to larger windows. For "shortest" problems, such as finding the smallest window that contains certain letters, it is the other way round: if [l, r] meets the rule, every larger window meets it too. The argument is the same. What changes is when you shrink and where you record the answer.

Pause and predict You want the shortest window of s that contains every letter of t. The loop grows the window until it contains them all, then shrinks it from the left. Where should the code record the answer?

A fixed window is the simplest case. The size k is given, so there is nothing to decide: each step adds one element on the right and removes one on the left. Whatever the loop keeps about the window, such as a sum or some counts, is updated in O(1) per step instead of being recomputed from all k elements.

Where it breaks

Pause and predict You run the sliding window to find the longest subarray of [6, 7, -9, 5] whose sum is at most 10. What length does it report?

The negative value made a larger window valid again, so the rule is not monotone, and the 6 was dropped even though a valid window starts there. When values can be negative, use prefix sums instead. The same test shows that "exactly K different values" is not monotone either; the last problem of this unit shows how to handle it.

Real rate limiters count requests this way, with timestamps in place of indices: System design: rate limiter.

How to recognise it

Before you use a sliding window, ask one question: if a window breaks the rule, does every larger window that contains it break the rule too?

Pause and predict The rule is that the window's sum is at most 10, and the values may be negative. Is that rule monotone, so that a window that breaks it stays broken as it grows?

Three that only look like it

• If the answer is a pair of positions and the values between them do not matter, that is two pointers.
• If the rule is about sums and the values can be negative, or the sum must be exactly k, the rule is not monotone. That is prefix sums.
• If you need the maximum or minimum of each window, the window slides as usual, but you cannot update a maximum by removing the value that leaves, the way you subtract it from a sum. The loop keeps a monotonic deque instead, which is covered in stack.

Where it bites

Pause and predict In Java, after int best = 11, k = 3; double avg = best / k; runs, what value does avg hold?

• Sliding when the rule is not monotone. Sums with negative values and "exactly k" rules are not monotone. Check the rule before you write the loop.
• Using if instead of while in the shrink step. One drop may not make the window valid again; on abba this mistake reports 3 instead of 2.
• Recording in the wrong place. The longest shape records after the shrink loop, and the shortest shape records inside it. If you swap them, you measure a window that does not meet the rule.
• Moving l backwards. If you keep a map from each character to the index where it was last seen, set l = max(l, last[c] + 1), so that l never moves left.
• Starting best at 0 when looking for a maximum average or sum. If every value is negative, the code then reports 0, which is not the sum of any window. Start from the first window's value.