Sliding window - DSA Learning Guide

Overview

A sliding window keeps a contiguous range [left, right] over an array or string and updates an answer as the range moves. Instead of recomputing each subarray from scratch, you add the element entering on the right and remove the element leaving on the left.

Fixed-size windows always hold k elements. Variable-size windows grow until a constraint breaks, then shrink from the left until it holds again. Both turn O(n * k) or O(n^2) brute force into O(n).

A train window

Looking out of a moving train, you always see a stretch of scenery. As the train moves, new scenery appears on one side and old scenery disappears on the other. You never need to re-see the whole route to know what is in view.

When to use it

The problem asks about contiguous subarrays or substrings.
Keywords: longest, shortest, maximum sum, at most K distinct, contains all characters.
The window's validity changes predictably when you add or remove one element.
Values are non-negative for sum constraints (so shrinking always reduces the sum).

Problem patterns it solves

Fixed-size window

Recognize it when: subarray or substring of size k, k consecutive elements, every window of length k.

643. Maximum Average Subarray I
1876. Substrings of Size Three with Distinct Characters
438. Find All Anagrams in a String
219. Contains Duplicate II

Longest valid window

Recognize it when: longest / maximum length such that a constraint holds; shrink only when the window becomes invalid.

3. Longest Substring Without Repeating Characters
424. Longest Repeating Character Replacement
904. Fruit Into Baskets
1004. Max Consecutive Ones III

Shortest valid window

Recognize it when: minimum length, smallest window that contains / reaches a target; shrink while still valid.

209. Minimum Size Subarray Sum
76. Minimum Window Substring

Count subarrays with at most K

Recognize it when: number of subarrays with exactly K of something; compute atMost(K) - atMost(K - 1).

1248. Count Number of Nice Subarrays
992. Subarrays with K Different Integers
930. Binary Subarrays With Sum

Window with a min / max (monotonic deque)

Recognize it when: maximum or minimum of every window, or max - min within a limit.

239. Sliding Window Maximum
1438. Longest Continuous Subarray With Absolute Diff <= Limit

Where it is used in real software

TCP flow control

TCP keeps a sliding window of bytes that may be in flight. Acknowledgements slide it forward, which bounds memory and adapts to the receiver's speed.

Rate limiters

Sliding-window log and sliding-window counter limiters count requests in the last N seconds as time moves forward.

Monitoring dashboards

Moving averages and rolling P99 latency over the last 5 minutes are fixed-size windows updated incrementally.

Stream processing

Kafka Streams and Apache Flink offer tumbling and sliding windows to aggregate events such as clicks per minute.

Key terms

Window: The current contiguous range between left and right, inclusive.
Expand: Move right forward and include its element in the window state.
Shrink: Move left forward and remove its element from the window state.
Window state: The running summary: a sum, a frequency map, a set, or a count of distinct items.

How it works, step by step

1
Choose the window state
Decide what you must know about the window: a running sum, character counts, or a set of seen values.
2
Expand right
For each right from 0 to n - 1, add values[right] to the state.
3
Shrink while invalid
While the window breaks the constraint, remove values[left] from the state and increment left.
4
Record the answer
Once valid, update the best answer with the window length right - left + 1 or its sum.

Fixed window: maximum sum of k = 3 consecutive values

STEP 1First window [2, 1, 5]: sum = 8. best = 8.

Longest substring without repeating characters

text = "abcabcbb"

right	char	Action	Window	Best
0	a	add	a	1
1	b	add	ab	2
2	c	add	abc	3
3	a	a repeats: drop a	bca	3
4	b	b repeats: drop b	cab	3
5	c	c repeats: drop c	abc	3
6	b	drop a, drop b	cb	3
7	b	drop c, drop b	b	3

NOWright: 0 | char: a | Action: add | Window: a | Best: 1

The answer is 3. Each character enters the window once and leaves at most once, so the total work is O(n) even though there is an inner while loop.

Implementation

1// Variable window: longest substring with no repeated characters.2function lengthOfLongestSubstring(text: string): number {3  const inWindow = new Set<string>();4  let left = 0;5  let best = 0;6 7  for (let right = 0; right < text.length; right++) {8    while (inWindow.has(text[right])) {9      inWindow.delete(text[left]);10      left++;11    }12    inWindow.add(text[right]);13    best = Math.max(best, right - left + 1);14  }15 16  return best;17}18 19// Fixed window: maximum sum of any k consecutive values.20function maxSumOfK(values: number[], k: number): number {21  let sum = 0;22  for (let i = 0; i < k; i++) sum += values[i];23  let best = sum;24 25  for (let right = k; right < values.length; right++) {26    sum += values[right] - values[right - k]; // add new, remove old27    best = Math.max(best, sum);28  }29  return best;30}

Complexity and performance

TimeO(n)

left and right each move forward at most n times; the nested loop is amortized.

SpaceO(k)

k is the number of distinct items tracked in the window (bounded by the alphabet size).

Trade-offs

Negative numbers break sum windows

Shrinking only reduces the sum when every value is non-negative. With negatives, use prefix sums with a hash map, or a monotonic deque.

Set vs last-seen map

A set shrinks one step at a time. A last-seen index map lets left jump directly, which is simpler to reason about for duplicates.

Variants and related techniques

At most K distinct

Keep a frequency map; shrink while map.size > k. Exactly K distinct equals atMost(K) - atMost(K - 1).

Minimum window substring

Track how many required characters are satisfied; shrink while all are satisfied to find the shortest valid window.

Sliding window maximum

Maintain a monotonic deque of indexes whose values decrease, giving O(n) for maximums of every window of size k.

Common mistakes

Recomputing the window sum from scratch each step.
Fix: Update incrementally: add the entering value, subtract the leaving value.
Recording the answer before the window is valid again.
Fix: Shrink first in longest-window problems; record inside the shrink loop in shortest-window problems.
Forgetting to decrement counts to zero and delete keys.
Fix: When a frequency reaches 0, delete the key so map.size reflects distinct items correctly.

Interview questions

Why is a loop with a nested while still O(n)?

The inner loop only moves left forward, and left can move at most n times across the whole run. Total pointer moves are at most 2n.

How do you know a problem is a sliding window problem?

It concerns contiguous ranges and the validity of a range changes monotonically: adding elements can only break it, removing elements can only fix it.

Practice problems

Problem	Difficulty	What it trains
Maximum Average Subarray I	Easy	Fixed window update.
Longest Substring Without Repeating Characters	Medium	Variable window with a set or map.
Minimum Size Subarray Sum	Medium	Shortest valid window.
Longest Repeating Character Replacement	Medium	Window validity using max frequency.
Permutation in String	Medium	Fixed window with frequency comparison.
Minimum Window Substring	Hard	Satisfied-count tracking.
Sliding Window Maximum	Hard	Monotonic deque.