Sliding Window — Fixed vs Variable, Traced
From O(n²) nested loops to one O(n) pass
Many "longest/shortest/contains substring or subarray" problems look like "check every range" = O(n²). The
sliding window keeps a range [L, R] and moves both pointers only right: grow
R to include more, shrink L when a constraint breaks. Each index enters and leaves the
window once → O(n).
The two shapes
// VARIABLE window — longest substring without repeating chars
int L=0, best=0; Set<Character> win = new HashSet<>();
for (int R=0; R < s.length(); R++) {
while (win.contains(s.charAt(R))) win.remove(s.charAt(L++)); // shrink until valid
win.add(s.charAt(R));
best = Math.max(best, R - L + 1); // window is valid here
}
return best;
// FIXED window of size k — slide both together
long sum=0, best=Long.MIN_VALUE;
for (int R=0; R < n; R++) {
sum += a[R];
if (R >= k) sum -= a[R - k]; // drop the element leaving the window
if (R >= k-1) best = Math.max(best, sum);
}The trace ("abcabcbb")
| R | char | window | L | best |
|---|---|---|---|---|
| 0–2 | a b c | "abc" | 0 | 3 |
| 3 | a (dup) | shrink past old a → "bca" | 1 | 3 |
| 4 | b (dup) | "cab" | 2 | 3 |
Pitfalls
- When to shrink: shrink while invalid (a
while, not anif) — multiple elements may need to leave. - Window size is
R - L + 1— off-by-one here is the classic bug. - Only for contiguous subarrays/substrings; non-contiguous needs a different tool.
Takeaways
- Two pointers moving only right → O(n); each element enters/leaves once.
- Fixed window: slide both together. Variable: grow R, shrink L while invalid.
- Track the valid-window state (a set/map/sum) incrementally, not by re-scanning.
Re-authored for this guide; window-slide diagram hand-authored as SVG. See also: Two Pointers, Hashing, Arrays.
🤖 Don't fully get this? Learn it with Claude
Stuck on Sliding Window — Fixed vs Variable, Traced? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
🎨 Explain it visually
Build the mental picture, not memorization.
I just read a lesson on **Sliding Window — Fixed vs Variable, Traced** (DSA) and want to truly understand it. Explain Sliding Window — Fixed vs Variable, Traced from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)
Socratic — adapts to where you're stuck.
Teach me **Sliding Window — Fixed vs Variable, Traced** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps
Active recall exposes what you missed.
Quiz me on **Sliding Window — Fixed vs Variable, Traced** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick
Intuition + hook + flashcards for long-term memory.
Help me remember **Sliding Window — Fixed vs Variable, Traced** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.