Knowledge Guide
Home › DSA

Sliding Window

Step 4 in the DSA path · 1 concepts · 6 problems

0 / 7 complete

📘 Learn Sliding Window from zero

The Sliding Window pattern maintains a contiguous range [L, R] over an array or string and slides it instead of re-scanning every subrange, turning an O(n²) brute force into O(n). You expand the right edge to include new elements and contract the left edge when the window breaks a constraint, all while tracking the best window seen. Reach for it whenever a problem asks for the longest / shortest / best contiguous subarray or substring satisfying some condition (a target sum, a character count, or "no duplicates"). Canonical example: Longest Substring Without Repeating Characters on s = "abcabcbb" (answer = 3).

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 0 — Setup
s =  a  b  c  a  b  c  b  b
idx  0  1  2  3  4  5  6  7
     ^
     LR        (L=0, R=0)

seen = {}        best = 0

We keep a window [L, R] plus a seen map of each character's last index. L is the left edge, R scans rightward. Invariant: s[L..R] always holds only distinct characters, and best records the longest valid window so far.

Step 1 — R=0, add 'a'
s = [a] b  c  a  b  c  b  b
idx  0  1  2  3  4  5  6  7
     ^
     LR

window = "a"   len = 1
seen = {a:0}   best = 1

'a' is not in the window, so we extend R and record seen[a]=0, giving best=1. Safe because a single character can never duplicate itself.

Step 2 — R=1..2, add 'b','c'
s = [a  b  c] a  b  c  b  b
idx  0  1  2  3  4  5  6  7
     ^     ^
     L     R

R=1 'b' new: window "ab"  len=2  best=2
R=2 'c' new: window "abc" len=3  best=3
seen = {a:0, b:1, c:2}  best = 3

'b' (R=1) then 'c' (R=2) are both new, so R keeps expanding while L stays pinned at 0. The window grows "ab" (best=2) then "abc" (best=3). No duplicate appeared, so no shrink is required and the invariant still holds.

Step 3 — R=3, 'a' repeats → jump L
s =  a [b  c  a] b  c  b  b
idx  0  1  2  3  4  5  6  7
        ^     ^
        L     R

seen[a]=0 and 0 >= L(=0), so L = 0+1 = 1
window = "bca"  len = 3   best = 3

'a' is already in seen at index 0, which is inside the current window. To restore "no duplicates" we jump L = seen[a]+1 = 1, skipping the stale 'a' in one move, then set seen[a]=3. Window "bca" has len 3, so best stays 3.

Step 4 — R=4, 'b' repeats → jump L
s =  a  b [c  a  b] c  b  b
idx  0  1  2  3  4  5  6  7
           ^     ^
           L     R

seen[b]=1 and 1 >= L(=1), so L = 1+1 = 2
window = "cab"  len = 3   best = 3

'b' was last seen at index 1, still >= L, so it is a true in-window duplicate. We jump L=2 and set seen[b]=4. We never move L backward — that is exactly why the jump check uses seen[ch] >= L rather than just "ch in seen".

Step 5 — R=5, 'c' repeats → jump L
s =  a  b  c [a  b  c] b  b
idx  0  1  2  3  4  5  6  7
              ^     ^
              L     R

seen[c]=2 and 2 >= L(=2), so L = 2+1 = 3
window = "abc"  len = 3   best = 3

Same move for 'c' (last seen at 2): jump L=3, set seen[c]=5. The window slides to "abc" with len 3. Each character is added by R once and skipped by L at most once, which is why the whole scan stays O(n).

Step 6 — R=6,7 add 'b','b' → final
s =  a  b  c  a  b  c  b [b]
idx  0  1  2  3  4  5  6  7
                          ^
                          LR
R=6 'b': seen[b]=4 >= L(3) -> L=5 ; "cb" len2
R=7 'b': seen[b]=6 >= L(5) -> L=7 ; "b"  len1

best = 3   ANSWER = 3

At R=6 the duplicate 'b' (last seen at 4) jumps L=5, window "cb"; we set seen[b]=6. At R=7 another 'b' (now last seen at 6) jumps L=7, window "b". Neither beats best. R has reached the end, so we return best = 3 — the length of "abc". This same expand-then-shrink-on-violation template also powers Minimum Size Subarray Sum, Max Vowels in a Substring, and Max Consecutive Ones III.

🎯 Guided practice

  1. Easy — Maximum Average Subarray I (fixed window). Given nums and k, return the maximum average of any contiguous subarray of length k.

    Reasoning: Average is maximized exactly when the sum is maximized (k is constant), so optimize the sum and divide once at the end. (1) Build the first window: windowSum = sum(nums[0..k-1]); set best = windowSum. (2) Slide i from k to n-1: windowSum += nums[i] - nums[i-k] — add the entrant, subtract the element that fell off the left. (3) After each slide, best = max(best, windowSum). (4) Return best / k as a double — in C++/Java best and k are ints, so cast ((double)best / k) or integer division will silently truncate 12.75 to 12.

    Trace on nums = [1,12,-5,-6,50,3], k = 4: first window sum = 1+12-5-6 = 2. Slide (add 50, drop 1): 2 + 50 - 1 = 51. Slide (add 3, drop 12): 51 + 3 - 12 = 42. best = 51 → answer 51/4 = 12.75. Linear time, O(1) space. Lesson: a fixed window is just a running aggregate you patch as you slide. (Sibling: Maximum Number of Vowels in a Substring of Given Length is the identical fixed-window template, but the aggregate is a vowel count — on each slide do cnt += isVowel(s[i]) - isVowel(s[i-k]).)

  2. Medium — Max Consecutive Ones III (variable window, "longest"). Given a binary array nums and integer k, return the length of the longest contiguous subarray of all 1's after flipping at most k zeros.

    Reframe (the key move): "flip at most k zeros to make all 1's" = "find the longest window containing at most k zeros". That constraint is monotonic, so the variable-window template applies. (1) left = 0, zeros = 0, best = 0. (2) Expand: for each right, if nums[right] == 0 increment zeros. (3) Restore the invariant: while zeros > k, if nums[left] == 0 decrement zeros, then left += 1. (4) The window [left, right] is now valid; record best = max(best, right - left + 1) — after shrinking, because this is a "longest" problem.

    Trace on nums = [1,1,0,0,1,1,1,0,1], k = 2: both zeros are admitted by index 3 (window [0..3], zeros = 2, valid, len 4). Indices 4–6 add 1's freely (window [0..6], len 7, best = 7). At index 7 a third zero appears → zeros = 3 > k; shrink, advancing left from 0 past the zero at index 2, dropping zeros back to 2 → window [3..7], len 5. Index 8 → window [3..8], len 6. Final best = 7. O(n) time, O(1) space.

    Sibling trap — Longest Subarray of 1's After Deleting One Element (LC 1493). This looks like the k = 1 case but the off-by-one is genuinely different, and the difference is load-bearing. You must delete exactly one element, so the answer is right - left unconditionally (never + 1), even when the window holds zero zeros. Why: the "at most one zero" window represents the subarray before deletion; removing one element shortens the resulting all-ones run by one, giving windowSize - 1 = right - left. Concrete check: input [1,1,1] must return 2, not 3 — there is no zero to flip, you are still forced to delete one element. (Contrast: Max Consecutive Ones III with k = 1 on [1,1,1] returns 3, because flipping keeps the length.)

  3. Medium — Minimum Size Subarray Sum (variable window, "shortest"). Given a positive-valued array nums and a target, return the minimal length of a contiguous subarray with sum ≥ target (or 0 if none).

    The fork from the previous problem: here we want the shortest valid window, so the answer is recorded inside the shrink loop, not after it. (1) left = 0, sum = 0, best = ∞. (2) Expand: sum += nums[right]. (3) while sum >= target (window is valid): record best = min(best, right - left + 1), then sum -= nums[left]; left += 1 to try a shorter window. (4) Return best == ∞ ? 0 : best. Trace on target = 7, nums = [2,3,1,2,4,3]: the window [4,3] at indices 4–5 sums to 7 with length 2, and no length-1 element reaches 7, so best = 2. The reason recording happens inside the loop: every state while sum >= target is a valid candidate, and the smallest occurs at the tightest left edge. This is the canonical demonstration of Recognition Pitfall 3 — the all-positive guarantee is what makes the shrink monotonic; drop it and you must switch to prefix-sum + binary search. The Longest Substring Without Repeating Characters problem is the same variable-window machinery with a hash map: extend right, and while the entering character is already in the window, shrink from the left (removing characters) until it is unique again, then record the "longest" length right - left + 1 after the window is valid — giving O(n) time and O(min(n, |charset|)) space.

✨ Added by the guide — work these before the full problem set.

Lessons in this topic