Basic Sliding Window Questions

Six warm-ups to lock the two templates into muscle memory. Three are fixed-size, three are variable-size — by the end you should be able to spot which flavor a new problem wants in five seconds.

For each problem, force yourself through the pattern-spotting checklist before peeking:

Is the answer over a contiguous range?
Is the property monotone in window growth?
What running state do I need?
What signals shrink (variable) or slide (fixed)?
When do I record the answer?

1. Maximum sum of a size-k subarray

Find the maximum sum of any contiguous subarray of length k.

Flavor: fixed-size. State: running sum. Record: every shift after the first window.

Time: O(n). Space: O(1).

2. Moving Average from a Data Stream

Implement a MovingAverage(k) class that supports next(val) returning the average of the last k values.

Flavor: fixed-size (streaming). State: queue + running sum.

The queue keeps the window contents so we know what to evict. The sum is a precomputed projection for O(1) averaging.

3. Contains Nearby Duplicate

Return true if there are two distinct indices i and j with nums[i] == nums[j] and |i − j| <= k.

Flavor: fixed-size. State: set of values in the last k + 1 positions.

Time: O(n). Space: O(k).

4. Longest Substring Without Repeating Characters

Find the length of the longest substring of s without repeating characters.

Flavor: variable-size, longest-valid. State: set of chars in window. Shrink while: s[r] already in set.

Time: O(n). Space: O(min(n, charset)).

5. Minimum Size Subarray Sum

Given a positive-integer array nums and target, find the minimal length of a contiguous subarray with sum >= target.

Flavor: variable-size, shortest-valid. State: running sum. Record: inside the shrink loop.

Time: O(n). Space: O(1).

The “shrink while valid, recording each step” structure is the signature of shortest-valid-window problems.

6. Fruit Into Baskets (longest with at most 2 distinct)

A classic in disguise. You walk through a row of fruit trees and can carry only two types of fruit. Starting at any tree, how many fruits can you collect?

It’s “longest contiguous subarray with at most 2 distinct values” — variable-window with at-most-K.

Time: O(n). Space: O(1) — the map has at most 3 entries before shrinking.

Mini-quiz

In Longest Substring Without Repeating Characters, where do you put the answer update?

In Minimum Size Subarray Sum, where do you put the answer update?

Why does Contains Nearby Duplicate use a hash SET instead of a deque or queue?

Next: the eight practice problems — every shape covered, with full state-design walkthroughs.

Advanced Patterns Overview