Sliding Window Pattern
What Is a Sliding Window?
A sliding window is a contiguous range [left, right] of an array or string that moves from left to right. Instead of recomputing every range from scratch, you update the window's summary (sum, counts, distinct items) as elements enter on the right and leave on the left.
values: [4, 2, 7, 1, 8, 3, 5] window of size 3 sliding right: [4, 2, 7] 1 8 3 5 sum 13 4 [2, 7, 1] 8 3 5 sum 13 - 4 + 1 = 10 4 2 [7, 1, 8] 3 5 sum 10 - 2 + 8 = 16 4 2 7 [1, 8, 3] 5 sum 16 - 7 + 3 = 12 4 2 7 1 [8, 3, 5] sum 12 - 1 + 5 = 16 Brute force: re-sum each window → O(n · k) Sliding: one add + one subtract per step → O(n)
It is the same-direction form of Two Pointers, specialised for contiguous ranges.
Two Kinds of Window
FIXED SIZE VARIABLE SIZE
───────────────────────────── ──────────────────────────────────
Size k is given Size depends on a condition
"any k consecutive ..." "longest / shortest range such that ..."
Both ends move together right always grows the window;
left shrinks it when needed
The Variable-Window Template
left = 0
for right in 0 .. n-1:
ADD values[right] to the window state
while WINDOW IS INVALID: ← for "longest valid" problems
REMOVE values[left]; left += 1
UPDATE answer with (right - left + 1)
For "shortest valid" problems, flip the inner loop:
while WINDOW IS VALID:
UPDATE answer with (right - left + 1)
REMOVE values[left]; left += 1
Every variable-window problem is this loop plus a choice of window state (a sum, a count map, a last-seen map) and a validity rule.
Worked Examples
1. Best Total Over k Consecutive Days (Fixed)
rainfall = [4, 2, 7, 1, 8, 3, 5], k = 3 → best = 16, first reached at day 2 (7+1+8)
2. Longest Run With No Repeat (Variable, "Longest Valid")
A playlist is a string of song IDs. Find the longest stretch of consecutive songs with no song repeated.
playlist = A B C A D B E
index 0 1 2 3 4 5 6
right=0 A window [A] len 1
right=1 B window [A B] len 2
right=2 C window [A B C] len 3
right=3 A A last seen at 0 → left = 1 window [B C A] len 3
right=4 D window [B C A D] len 4
right=5 B B last seen at 1 → left = 2 window [C A D B] len 4
right=6 E window [C A D B E] len 5 ← best
State: last_seen[item] — lets left JUMP past the earlier copy.
Guard: only jump if last_seen[item] ≥ left (an older copy outside
the window must not drag left backwards).
3. Longest Run With At Most k Kinds (Variable, Count Map)
items = X Y X Z Z Z Y X, k = 2 State: count of each kind in the window. Invalid when > k kinds. Best window: X Z Z Z (or Z Z Z Y) → length 4
4. Shortest Batch Reaching a Goal (Variable, "Shortest Valid")
orders = [2, 1, 5, 2, 3, 2], goal = 7 grow until total ≥ 7, then shrink while it stays ≥ 7: [2 1 5] = 8 ≥ 7 → len 3; drop 2 → [1 5] = 6 [1 5 2] = 8 ≥ 7 → len 3; drop 1 → [5 2] = 7 ≥ 7 → len 2 ✓; drop 5 → [2] = 2 ... Shortest: 2 ([5, 2])
Code: Fixed and Variable Windows
import java.util.HashMap;
import java.util.Map;
public class SlidingWindow {
// Fixed-size window — best total over any k consecutive values
static int[] bestFixedWindow(int[] values, int k) {
int window = 0;
for (int i = 0; i < k; i++) window += values[i];
int best = window, bestStart = 0;
for (int right = k; right < values.length; right++) {
window += values[right] - values[right - k]; // slide: add new, drop old
if (window > best) { best = window; bestStart = right - k + 1; }
}
return new int[]{best, bestStart};
}
// Variable window — longest stretch with no repeated item
static int longestWithoutRepeat(String items) {
Map<Character, Integer> lastSeen = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < items.length(); right++) {
char item = items.charAt(right);
Integer prev = lastSeen.get(item);
if (prev != null && prev >= left) left = prev + 1; // jump past the earlier copy
lastSeen.put(item, right);
best = Math.max(best, right - left + 1);
}
return best;
}
// Variable window — longest stretch with at most k distinct items
static int longestAtMostKDistinct(String items, int k) {
Map<Character, Integer> count = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < items.length(); right++) {
count.merge(items.charAt(right), 1, Integer::sum);
while (count.size() > k) { // too many kinds → shrink
char out = items.charAt(left++);
if (count.merge(out, -1, Integer::sum) == 0) count.remove(out);
}
best = Math.max(best, right - left + 1);
}
return best;
}
// Variable window — shortest stretch whose total reaches a goal (positive values)
static int shortestReaching(int[] values, int goal) {
int left = 0, total = 0, best = values.length + 1;
for (int right = 0; right < values.length; right++) {
total += values[right];
while (total >= goal) { // valid → try to shrink
best = Math.min(best, right - left + 1);
total -= values[left++];
}
}
return best == values.length + 1 ? 0 : best;
}
public static void main(String[] args) {
int[] r = bestFixedWindow(new int[]{4, 2, 7, 1, 8, 3, 5}, 3);
System.out.println("best 3-day rainfall: " + r[0] + " starting at day " + r[1]);
for (String p : new String[]{"ABCADBE", "AAAA", "ABCDEF"})
System.out.println("longest no-repeat run in " + p + ": " + longestWithoutRepeat(p));
System.out.println("longest run with <= 2 kinds in XYXZZZYX: " + longestAtMostKDistinct("XYXZZZYX", 2));
int[] orders = {2, 1, 5, 2, 3, 2};
for (int goal : new int[]{7, 11, 100})
System.out.println("shortest batch reaching " + goal + ": " + shortestReaching(orders, goal));
}
}Output:
best 3-day rainfall: 16 starting at day 2
longest no-repeat run in ABCADBE: 5
longest no-repeat run in AAAA: 1
longest no-repeat run in ABCDEF: 6
longest run with <= 2 kinds in XYXZZZYX: 4
shortest batch reaching 7: 2
shortest batch reaching 11: 4
shortest batch reaching 100: 0
Why It's O(n)
for right in 0..n-1: ← right moves n times total
while invalid:
left += 1 ← left moves at most n times TOTAL,
because it never moves backwards
and never passes right
Total pointer moves ≤ 2n → O(n) time.
Window state (a sum, or a map with at most "alphabet size" entries)
→ O(1) or O(k) extra space.
When Sliding Window Breaks
The variable window relies on monotonicity: growing the window can only push it one way (e.g. more distinct items, bigger sum), and shrinking can only push it back.
WORKS BREAKS ─────────────────────────────────── ───────────────────────────────────── Sum ≥ goal with NON-NEGATIVE values Sum = goal with NEGATIVE values At most k distinct items "Exactly k" directly (use a trick ↓) No repeated items Non-contiguous selections Longest run of 1s with ≤ k flips Max product (sign flips break order) FIXES: Negative values, "sum exactly goal" → Prefix Sum + hash map "Exactly k distinct" → atMost(k) − atMost(k−1) Non-contiguous → DP, two pointers on sorted data, hashing
The "exactly k = at most k − at most (k − 1)" trick is worth remembering: counting windows with exactly k of something is not monotone, but counting at most k is.
How to Spot It
✓ "subarray" / "substring" / "consecutive" / "contiguous" / "run" / "stretch" ✓ "longest" / "shortest" / "maximum total" / "count of ranges" ✓ A condition that gets monotonically harder (or easier) as the range grows ✓ Input size up to 10^5 or more → O(n²) over all ranges is too slow
Common Mistakes
Moving left backwards. In the last-seen version, an old occurrence outside the window must be ignored — hence the last_seen[item] >= left guard.
Updating the answer in the wrong place. For "longest valid", update after the shrink loop (the window is valid again). For "shortest valid", update inside the shrink loop (while it is still valid).
Using if instead of while for shrinking. One step of shrinking may not restore validity.
Forgetting to delete zero-count keys. If the map keeps keys with count 0, len(count) overstates the number of distinct items.
Applying it to negative numbers. The shrink rule assumes removing an element moves the sum one way; with negatives it can move either way.
Interview Questions
Q: How would you count the subarrays with exactly k distinct values?
Counting "at most k" is monotone: for each right, the number of valid windows ending at right is right − left + 1. Sum that over all right to get atMost(k). Then exactly(k) = atMost(k) − atMost(k − 1). Both passes are O(n).
Q: Why does "shortest subarray with sum ≥ goal" fail with negative numbers, and what replaces it?
With negatives, shrinking from the left can increase the sum, so a window that is invalid now might become valid after removing an element — the window can't decide which way to move. The replacement uses prefix sums: for each right, find the latest left with prefix[left] ≤ prefix[right] − goal, using a monotonic deque of prefix indices, still O(n).
Q: Fixed window maximum — how do you get the maximum value (not sum) of every window of size k in O(n)?
A running sum can't track a maximum because removing the max requires knowing the next max. Use a monotonic deque of indices whose values decrease from front to back: the front is always the window's max, and indices that fall out of the window are popped from the front. See Monotonic Stack & Queue.
Summary
- ›A sliding window updates a summary as elements enter right and leave left — no recomputation.
- ›Fixed size: add one, drop one → O(n).
- ›Variable size: expand with
right, shrink withleftwhile invalid (longest) or while valid (shortest). - ›O(n) because both pointers only move forward.
- ›Needs monotonicity; for negatives or "exactly k", switch to prefix sums or the at-most trick.
Next, Fast & Slow Pointers uses two pointers moving at different speeds to find cycles and middles — in linked lists and in number sequences.
A fixed window of size k moves one step right. How is the new window sum computed in O(1)?