Explore fixed and variable sliding windows with interactive substring and subarray examples. Follow pointer moves, compare brute force and study Python solutions.
The pattern
Sliding Window: a range that moves instead of restarting
Many questions ask about substrings or subarrays: runs of consecutive items. There are about n²/2 of them, so checking each one is slow. A sliding window keeps one range [L, R] and moves its ends, updating what it knows about the range (a sum, letter counts, a set) as items enter on the right and leave on the left. Each item enters once and leaves at most once, so the whole scan is O(n).
1Slide, don't recount
Moving a window of 3 one step changes just two things: one number leaves on the left, one arrives on the right. Update the sum or counts for those two instead of starting again.
2Grow until it breaks, then shrink
For “longest” or “shortest” windows, R adds one item at a time. When the window breaks the rule, L drops items from the left until it's fine again. Both only move right, so it's O(n).
3Keep only what can still win
For the max of every window, a number is useless once a bigger number arrives after it. Throw those away and the survivors are in decreasing order, so the max is always at the front.
How to spot it
- The question says “substring”, “subarray” or “consecutive”, not “subsequence” (those can skip items).
- “Longest / shortest … such that …”: a window that grows and shrinks.
- “Every window of size k”, “a permutation of p inside s”: a fixed-size window.
- “At most k changes / distinct / zeros”: count inside the window and shrink when the budget is broken.
The template (Python)
l = 0
for r in range(len(s)):
add(s[r]) # grow on the right
while window_is_broken():
remove(s[l]) # shrink on the left
l += 1
best = max(best, r - l + 1)For “shortest”, flip it: shrink while the window is still valid, recording as you go. Another variable-size example on this site: Longest Subarray with Sum K.
NeetCode 150 · Sliding Window
All 6 problems
Pick a problem to see it solved step by step. They're in NeetCode's order, roughly easiest first.
Best Time to Buy and Sell Stock
EasyBlind 75prices[i] is a stock's price on day i. Buy on one day and sell on a later day. Return the largest profit you can make, or 0 if no trade makes money.
prices = [7, 1, 5, 3, 6, 4]
variables
- buy price p[L]
- 7
- sell price p[R]
- 1
- profit
- -6
- best
- 0
Press Play or Step to watch the solution run.
Brute force vs the pattern
On this input:
- Pattern: O(n)
- 5 ops
- Brute force
- 15 ops
On a bigger input (200 days):
- Pattern
- 199 ops
- Brute force
- 19,900 ops
Try every buy day with every later sell day: about n²/2 pairs.
“ops” counts basic steps: lookups, inserts, comparisons, array reads. On tiny inputs brute force can even win, because it may stumble on the answer early; as n grows, the gap opens up.
How it works: Best Time to Buy and Sell Stock
Step by step
- Buy day L
- Sell day R
- Best trade so far
- Best trade
Press Start or Step: the step the animation is on lights up below.
- 1
Buy on day 0
L = 0 is the buy day; R will try every later day.
l, best = 0, 0 - 2
Price higher → check the profit
Profit if we sell today = p[R] − p[L]; keep the best.
best = max(best, p[r] - p[l]) - 3
Price lower → buy here instead
A cheaper buy day beats the old one for every later sale.
if p[r] < p[l]: l = r - 4
Every sell day tried → best profit
Each day was the sell day once.
return best
The window runs from the buy day L to the sell day R. R moves forward one day at a time; for each R, the best buy day is simply the cheapest day so far.
So whenever R finds a price lower than the buy price, the window restarts there: L jumps to R. Otherwise, check the profit and keep the best. One pass, O(n).
Spot it in an interview
- “Best pair where one comes before the other”: keep the best left end seen so far while the right end moves.
- The window here only restarts, never shrinks one by one. Later problems shrink it step by step.
R visits each day once, and each visit is one comparison.
Credits
Learn more from NeetCode
The problem list and order come from the NeetCode 150 by NeetCode (neetcode.io). The solutions here follow the approaches NeetCode teaches in the linked videos; the animations, explanations and code were written for CodeQuest. If these help, NeetCode's videos and site are well worth your time.
Problem statements are summarised in our own words; the full versions are on LeetCode.