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
5	c (dup)	shrink past old c → "abc"	3	3
6	b (dup)	shrink past a, b → "cb"	5	3
7	b (dup)	shrink past c, b → "b"	7	3

Final answer: best = 3 ("abc"). Cost accounting: R advances n times and each index is removed from the set at most once as L advances → ≤ 2n set operations total, Θ(n) time; space is Θ(min(n, σ)) for the window charset (σ = alphabet size).

Edge checks (hand-run them)

• Empty string → best = 0 (loop never runs).
• Single char → best = 1.
• All unique → best = n (L never moves).
• All same, "aaaa" → best = 1 (every step shrinks exactly once).

Pitfalls

• When to shrink: shrink while invalid (a while, not an if) — 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.
• Variable windows on sums need non-negative elements: if the array can contain negatives, growing the window can decrease the sum and the shrink-while-valid logic is wrong — use prefix sums (often with a hash map) instead. Fixed-size sum windows stay valid with negatives.
• Max/min of a window: a plain running variable cannot reverse when the extremum leaves — use a monotonic deque (amortized O(1) per step).
• Arbitrary range queries: if windows are not visited in left-to-right sliding order, prefer a prefix-sum array over a sliding window. Full trade-offs: see Introduction to Sliding Window Pattern.

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.

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.

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 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.

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.