You grow a window over a list or string and shrink it from the other side. The problem finishes in one pass, and no sum gets recomputed.

Earn the full sheet below.

When to use it

• You need the longest or shortest contiguous run.
• You update a running sum, not recompute it.
• The window is fixed, or it grows and shrinks to fit.
• 'At most k' is this pattern winking at you.

What's on the sheet

The steps hold for every problem here. Step 3 changes, and so does what the window tracks.

1. Set Up. Two pointers and a running total start here.
2. Grow the Window. The window expands until its cost is big enough.
3. Check and record. Your problem defines valid; the window just keeps the books.
4. Shrink and Return. Contract the left each pass, or it's O(n^2).

Watch out

• Expanding and contracting are separate steps; skip the contraction and you're back to an O(n^2) scan.
• Check b < len(nums) every time you grow the window, or you'll index past the end.
• The window's 'cost' isn't always a sum. Fruit into Baskets tracks distinct-element counts in a dict instead.

How to earn it

Solve half of the Sliding Window problems and the sheet is yours. A free account works fine, and everyone earns their sheets the same way.

Want to see a finished sheet first? Preview the Two Pointers sample.

Every pattern has a sheet. See the full set.