Part 1 moved two pointers toward each other. Here they both move right, and what matters is the gap between them. That gap is the window, and the whole family comes down to two questions: when do I grow it, and when do I shrink it.
Every program below is complete, was run on .NET 10, and its output is pasted from the run.
Why it is worth the trouble
Take the largest sum of any k consecutive values. The obvious version adds up each window from scratch. Count the additions:
// How many additions each approach needs. No timing — just the work done.
Console.WriteLine($"{"n",8} {"k",6} {"recompute",14} {"slide",10}");
foreach ((int n, int k) in new[] { (8, 3), (1_000, 100), (100_000, 1_000) })
{
long recompute = (long)(n - k + 1) * k;
long slide = k + (long)(n - k) * 2;
Console.WriteLine($"{n,8} {k,6} {recompute,14:N0} {slide,10:N0}");
}It prints:
n k recompute slide
8 3 18 13
1000 100 90,100 1,900
100000 1000 99,001,000 199,000At eight elements, 18 against 13 is nothing. At a hundred thousand, it is ninety-nine million against two hundred thousand, and one of those finishes inside the time limit.
The reason is that neighbouring windows overlap almost entirely. Recomputing throws that overlap away every single time.
Pattern 6 — The fixed window
The window is always exactly k wide. Slide it one step: one value leaves on the left, one arrives on the right, and the running total is corrected with a subtraction and an addition. The other k-2 values are never touched.
The window never gets re-added. One value leaves on the left (red), one arrives on the right, and the running sum is corrected by two operations instead of k.
int[] a = [3, 1, 4, 1, 5, 9, 2, 6];
int k = 3;
int win = 0;
for (int i = 0; i < k; i++) win += a[i];
int best = win, bestAt = 0;
Console.WriteLine($"window [0..{k - 1}] sum = {win}");
for (int r = k; r < a.Length; r++)
{
int leaving = a[r - k], entering = a[r];
win += entering - leaving;
if (win > best) { best = win; bestAt = r - k + 1; }
Console.WriteLine($"window [{r - k + 1}..{r}] -{leaving} +{entering} sum = {win}");
}
Console.WriteLine($"\nbest = {best}, starting at index {bestAt}: [{string.Join(", ", a[bestAt..(bestAt + k)])}]");It prints:
window [0..2] sum = 8
window [1..3] -3 +1 sum = 6
window [2..4] -1 +5 sum = 10
window [3..5] -4 +9 sum = 15
window [4..6] -1 +2 sum = 16
window [5..7] -5 +6 sum = 17
best = 17, starting at index 5: [9, 2, 6]Cost: O(n) time, O(1) space.
Reach for it when the problem fixes the window size for you — every substring of length k, any k consecutive days. If you can maintain the answer for a window in O(1) as it slides, this is the pattern.
Pattern 7 — Grow until it breaks, keep the longest
Now the window size is not given; it is what you are solving for. Find the longest stretch with no repeated character.
The rule flips: grow on the right always, and shrink from the left only when the window has become invalid. The answer is the largest valid window ever seen.
The interesting part is what “shrink” means here. Seeing a repeat, you do not step the left edge one at a time — you jump it straight past the previous occurrence. And that jump has a trap in it.
The trap is the last row. ‘a’ was seen at index 0, but index 0 is no longer in the window, so the left edge must not move back to it. Without the `prev >= lo` guard, lo goes backwards and the window grows out of control.
string s = "abba";
Dictionary<char, int> lastSeen = [];
int lo = 0, best = 0, bestAt = 0;
for (int r = 0; r < s.Length; r++)
{
char c = s[r];
if (lastSeen.TryGetValue(c, out int prev) && prev >= lo)
{
Console.WriteLine($"r={r} '{c}' seen at {prev}, and {prev} >= lo({lo}) -> lo jumps to {prev + 1}");
lo = prev + 1;
}
else if (lastSeen.TryGetValue(c, out int old))
{
Console.WriteLine($"r={r} '{c}' seen at {old}, but {old} < lo({lo}) -> it is OUTSIDE the window, lo stays");
}
else
{
Console.WriteLine($"r={r} '{c}' never seen -> lo stays {lo}");
}
lastSeen[c] = r;
int len = r - lo + 1;
if (len > best) { best = len; bestAt = lo; }
Console.WriteLine($" window [{lo}..{r}] = \"{s[lo..(r + 1)]}\" length {len}");
}
Console.WriteLine($"\nlongest = {best}, \"{s.Substring(bestAt, best)}\"");It prints:
r=0 'a' never seen -> lo stays 0
window [0..0] = "a" length 1
r=1 'b' never seen -> lo stays 0
window [0..1] = "ab" length 2
r=2 'b' seen at 1, and 1 >= lo(0) -> lo jumps to 2
window [2..2] = "b" length 1
r=3 'a' seen at 0, but 0 < lo(2) -> it is OUTSIDE the window, lo stays
window [2..3] = "ba" length 2
longest = 2, "ab"Read the r=3 line. 'a' was last seen at index 0, but the window starts at 2, so that 'a' is behind us and no longer in the window. Jumping lo to 0 + 1 would move the left edge backwards, and the window would silently start counting characters it had already discarded.
lomust never decrease. Any window pattern that jumps the left edge needs a guard saying so.
Drop the prev >= lo test and "abba" reports 3. It is a one-word bug and small inputs like "abcabc" do not catch it.
Cost: O(n) time — each pointer only ever moves right. O(k) space for the map, where k is the alphabet size.
Reach for it when the problem asks for the longest window satisfying a condition, and the condition is one that breaking can be repaired by removing elements from the left.
Pattern 8 — Shrink while it still holds, keep the shortest
The mirror image. Find the shortest window whose sum is at least a target.
Growing makes the sum bigger, so growing fixes an invalid window. That means the while loop moves to the other side: once the window is valid, shrink it as far as it stays valid, recording the length each time.
Grow on the right until the window is valid, then shrink from the left while it stays valid. The shortest answer is found at the moment shrinking would break it.
int[] a = [2, 3, 1, 2, 4, 3];
int target = 7;
int lo = 0, sum = 0, best = int.MaxValue, bestAt = -1;
for (int r = 0; r < a.Length; r++)
{
sum += a[r];
Console.WriteLine($"r={r} +{a[r]} window [{lo}..{r}] sum={sum}");
while (sum >= target)
{
int len = r - lo + 1;
if (len < best) { best = len; bestAt = lo; }
Console.WriteLine($" sum {sum} >= {target}, length {len} -> shrink: drop a[{lo}]={a[lo]}");
sum -= a[lo];
lo++;
}
}
Console.WriteLine(best == int.MaxValue
? "\nno window reaches the target"
: $"\nshortest = {best}, starting at {bestAt}: [{string.Join(", ", a[bestAt..(bestAt + best)])}]");It prints:
r=0 +2 window [0..0] sum=2
r=1 +3 window [0..1] sum=5
r=2 +1 window [0..2] sum=6
r=3 +2 window [0..3] sum=8
sum 8 >= 7, length 4 -> shrink: drop a[0]=2
r=4 +4 window [1..4] sum=10
sum 10 >= 7, length 4 -> shrink: drop a[1]=3
sum 7 >= 7, length 3 -> shrink: drop a[2]=1
r=5 +3 window [3..5] sum=9
sum 9 >= 7, length 3 -> shrink: drop a[3]=2
sum 7 >= 7, length 2 -> shrink: drop a[4]=4
shortest = 2, starting at 4: [4, 3]The while is doing the real work, and it must be a while, not an if. At r=4 the window shrinks twice in a row. An if would shrink once, leave a valid-but-not-minimal window, and quietly return 3 instead of 2.
Longest wants while (invalid) shrink; and records after. Shortest wants while (valid) { record; shrink; }. Those two lines are the difference between the two patterns, and everything else is the same code.
Cost: O(n) — lo and r each traverse the array once, so the nested loop is still linear.
Reach for it when the problem says shortest, smallest or minimum length, and all values push the quantity the same way. That last condition matters: with negative numbers in the array, growing no longer guarantees a bigger sum, the shrink rule stops being valid, and you need prefix sums instead — which is part 3.
Pattern 9 — Count “at most”, subtract to get “exactly”
Count the subarrays containing exactly K distinct values.
Try to slide that directly and you get stuck. If a window has too few distinct values, there is no move that repairs it: shrinking from the left cannot add variety. The condition is not one-sided, so the window has nothing to hold on to.
“At most K” is one-sided. Too many distinct values is always fixed by shrinking. So count that instead, twice:
exactly K = (at most K) − (at most K−1)“At most K” slides cleanly because too many distinct values is fixable by shrinking from the left. “Exactly K” does not — there is no move that repairs too few. So count the easy thing twice and subtract.
The other half of this pattern is the counting itself. For a window [lo..r] that is valid, every window ending at r and starting anywhere in lo..r is also valid — because dropping elements from the left can only reduce the distinct count. That is r - lo + 1 windows, added in one step rather than enumerated.
int[] a = [1, 2, 1, 2, 3];
int k = 2;
// Windows with AT MOST k distinct values. This one is easy to slide, because
// "too many distinct" is fixable by shrinking from the left.
static long AtMost(int[] a, int k, string label)
{
Dictionary<int, int> count = [];
long total = 0;
int lo = 0;
for (int r = 0; r < a.Length; r++)
{
count[a[r]] = count.GetValueOrDefault(a[r]) + 1;
while (count.Count > k)
{
if (--count[a[lo]] == 0) count.Remove(a[lo]);
lo++;
}
// Every window ending at r and starting at lo..r is valid: that is r-lo+1 of them.
total += r - lo + 1;
}
Console.WriteLine($"{label}: {total}");
return total;
}
long atMostK = AtMost(a, k, $"at most {k} distinct");
long atMostK1 = AtMost(a, k - 1, $"at most {k - 1} distinct");
Console.WriteLine($"\nexactly {k} distinct = {atMostK} - {atMostK1} = {atMostK - atMostK1}");It prints:
at most 2 distinct: 12
at most 1 distinct: 5
exactly 2 distinct = 12 - 5 = 7Cost: O(n), twice, so still O(n).
Reach for it when the word is exactly. It shows up for exactly K distinct, exactly K odd numbers, sums in a range. The move is always the same: find the one-sided version of the question, count it twice, subtract.
Pattern 10 — The window maximum, without rescanning
Report the maximum of every window of size k. Rescanning each window is O(nk), and a heap gets you O(n log k) but needs lazy deletion to handle values falling out of the window.
There is an O(n) answer, and it comes from one observation. If a[i] is smaller than some a[j] where j > i, then a[i] is finished. Any future window holding i also holds j, and j is both bigger and younger. a[i] can never be a maximum again, so it need never be stored.
Keep only the values that are still candidates. They come out decreasing, front to back.
The deque holds indices, and their values always decrease from front to back. Each index is pushed once and popped once, which is why the whole scan is O(n) despite the inner while loops.
int[] a = [1, 3, -1, -3, 5, 3, 6, 7];
int k = 3;
LinkedList<int> dq = []; // holds INDICES, values decreasing front to back
List<int> answer = [];
for (int r = 0; r < a.Length; r++)
{
while (dq.Count > 0 && dq.First!.Value <= r - k)
{
Console.WriteLine($"r={r} index {dq.First.Value} fell out of the window drop from front");
dq.RemoveFirst();
}
while (dq.Count > 0 && a[dq.Last!.Value] <= a[r])
{
Console.WriteLine($"r={r} a[{dq.Last.Value}]={a[dq.Last.Value]} <= a[{r}]={a[r]} it can never win again, drop from back");
dq.RemoveLast();
}
dq.AddLast(r);
if (r >= k - 1)
{
answer.Add(a[dq.First!.Value]);
Console.WriteLine($"r={r} window [{r - k + 1}..{r}] deque=[{string.Join(",", dq)}] max = a[{dq.First.Value}] = {a[dq.First.Value]}");
}
}
Console.WriteLine($"\nmaxima: [{string.Join(", ", answer)}]");It prints:
r=1 a[0]=1 <= a[1]=3 it can never win again, drop from back
r=2 window [0..2] deque=[1,2] max = a[1] = 3
r=3 window [1..3] deque=[1,2,3] max = a[1] = 3
r=4 index 1 fell out of the window drop from front
r=4 a[3]=-3 <= a[4]=5 it can never win again, drop from back
r=4 a[2]=-1 <= a[4]=5 it can never win again, drop from back
r=4 window [2..4] deque=[4] max = a[4] = 5
r=5 window [3..5] deque=[4,5] max = a[4] = 5
r=6 a[5]=3 <= a[6]=6 it can never win again, drop from back
r=6 a[4]=5 <= a[6]=6 it can never win again, drop from back
r=6 window [4..6] deque=[6] max = a[6] = 6
r=7 a[6]=6 <= a[7]=7 it can never win again, drop from back
r=7 window [5..7] deque=[7] max = a[7] = 7
maxima: [3, 3, 5, 5, 6, 7]Two details worth naming. The deque stores indices, not values, because the front has to be checked for having fallen out of the window and that is a question about position. And the front is always the answer: it is the largest surviving candidate, and everything that used to sit in front of it was discarded for being smaller.
The nested while loops look quadratic and are not. Every index is added exactly once and removed at most once, so the total work across the whole scan is bounded by 2n.
Cost: O(n) time, O(k) space.
Reach for it when you need a running min or max over a fixed window. The same structure, with the comparison flipped, gives the running minimum.
What to remember
-
Recomputing each window throws away the overlap. Correct the running value with what leaves and what arrives instead — two operations rather than
k. -
Longest and shortest are the same code with the
whileon opposite sides. Longest: shrink while invalid, then record. Shortest: while valid, record then shrink. -
lomust never move backwards. Any pattern that jumps the left edge past a previous occurrence needs theprev >= loguard, and"abba"is the smallest input that proves it. -
“Exactly K” cannot be slid. Too few is unfixable from the left. Count “at most K” twice and subtract.
-
A valid window
[lo..r]contributesr - lo + 1subarrays, not one. Counting windows one at a time is the other way people turn a linear solution quadratic. -
The monotonic deque discards anything smaller and older. It stores indices, the front is the answer, and each index enters and leaves once — which is the whole O(n) argument.
Part 3 covers what to do when the window trick stops working: negative numbers, arbitrary ranges, and updates applied to whole stretches at once. Prefix sums and difference arrays.