Sliding Window — Variable Size

Before we start

The previous chapter used a window of fixed size K — it always slid one step at a time. This chapter makes the window elastic: it can grow and shrink based on whether a condition is being satisfied. This is the more powerful — and more commonly tested — form of the sliding window. By the end you will be able to:

• See the variable window as a rubber band that stretches and snaps back.
• Explain the two-pointer expansion-shrink loop and why it's still O(n).
• Recognise this pattern in substring and subarray problems that ask for "longest" or "shortest."

Stop at every Pause & Think box before reading on.

Picture this first (no code yet)

The rubber band is the window. The right end is the right pointer; you are the left pointer. Together they scan the array exactly once.

The actual problem

Given an array of positive integers and a target sum S, find the length of the smallest contiguous subarray whose sum is greater than or equal to S.

Example:

array  = [2, 1, 5, 2, 3, 2]
S      = 7

subarrays with sum ≥ 7:
  [2,1,5,2] sum=10  length 4
  [5,2]     sum=7   length 2   ← shortest
  [5,2,3]   sum=10  length 3
  ...
answer = 2

First, the slow way (so you feel the pain)

Check every possible subarray:

def min_subarray_slow(arr, s):
    n = len(arr)
    best = float('inf')
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += arr[end]
            if total >= s:
                best = min(best, end - start + 1)
                break       # can't get shorter with same start
    return best if best != float('inf') else 0

Even with the early break, worst case is still O(n²) — for each start, you may scan to the end. With large arrays:

n = 10,000    →  up to 50,000,000 inner iterations
n = 100,000   →  up to 5,000,000,000 inner iterations

The variable sliding window does the same job in O(n).

The turning point

Why does brute force waste work? Because when you fix start = 0 and find the minimum valid end, then move to start = 1, you rebuild the window sum from scratch — even though arr[1] through the old end is still valid.

The answer: record the window size first, then shrink. The current window satisfies the condition — that's a valid answer. Shrinking it might give a shorter valid window (better answer). Expanding it would only give a longer window (worse answer). So: record, shrink, repeat until the condition breaks. Then expand.

The one idea to remember

The window breathes: expand to find a candidate, shrink to minimise it, expand again to find the next candidate.

Watch it happen, frame by frame

Array: [2, 1, 5, 2, 3, 2], S = 7. We want the smallest window with sum ≥ 7.

left=0, right=0, window_sum=0, best=∞

Expand right=0: add arr[0]=2  →  sum=2  < 7, keep expanding
Expand right=1: add arr[1]=1  →  sum=3  < 7, keep expanding
Expand right=2: add arr[2]=5  →  sum=8  ≥ 7  ← condition met!
  Record length = right-left+1 = 3-0+1 = 3.  best=3
  Shrink: remove arr[left=0]=2 → sum=6  < 7, stop shrinking.
  left=1

Expand right=3: add arr[3]=2  →  sum=8  ≥ 7  ← condition met!
  Record length = 3-1+1 = 3.  best=3
  Shrink: remove arr[left=1]=1 → sum=7  ≥ 7  ← still valid!
    Record length = 3-2+1 = 2.  best=2
    Shrink: remove arr[left=2]=5 → sum=2  < 7, stop shrinking.
    left=3

Expand right=4: add arr[4]=3  →  sum=5  < 7, keep expanding
Expand right=5: add arr[5]=2  →  sum=7  ≥ 7  ← condition met!
  Record length = 5-3+1 = 3.  best=2
  Shrink: remove arr[left=3]=2 → sum=5  < 7, stop shrinking.
  left=4

right exhausted.  Answer = best = 2  (the window [5,2])  ✅

left=0, sum=0, best=∞
right=0: +3 → sum=3  < 8
right=1: +4 → sum=7  < 8
right=2: +1 → sum=8  ≥ 8  → record len=3, best=3
  shrink: -3 → sum=5  < 8, stop. left=1
right=3: +1 → sum=6  < 8
right=4: +6 → sum=12 ≥ 8  → record len=4, best=3
  shrink: -4 → sum=8  ≥ 8  → record len=3, best=3
    shrink: -1 → sum=7  < 8, stop. left=3
right exhausted.  Answer = 3 (window [3,4,1] or [1,1,6])

Now, the code — line by line

def min_subarray_sum(arr, s):
    n = len(arr)
    left = 0
    window_sum = 0
    best = float('inf')        # track the smallest valid window seen

    for right in range(n):
        window_sum += arr[right]           # expand: new element enters from the right

        while window_sum >= s:             # condition is satisfied — try to shrink
            best = min(best, right - left + 1)   # record this window's length
            window_sum -= arr[left]        # remove the leftmost element
            left += 1                      # shrink from the left

    return best if best != float('inf') else 0   # 0 means no valid subarray found

Mapping to the rubber-band story:

• for right in range(n): — your friend (the right end) moves one step forward every iteration, never going back.
• window_sum += arr[right] — the rubber band now covers one more tile.
• while window_sum >= s: — the band is stretched across a valid section — check if this is the shortest so far.
• best = min(best, right - left + 1) — record the window length before you shrink.
• window_sum -= arr[left]; left += 1 — you (the left end) snap the band back one step.
• The while (not if) means you keep shrinking as long as the condition holds — every smaller valid window is a candidate for best.

Why is it O(n) even though there's a while loop inside a for loop?

This is the question everyone asks. The answer is in the pointer movement:

• right only ever moves right: n steps total.
• left only ever moves right: n steps total.

Together, the two pointers collectively take at most 2n steps. The inner while loop runs the left steps — it looks like it could run n times per outer iteration, but across the entire algorithm it runs at most n times total. Every step of left is paid for exactly once.

right moves:  n total steps
left moves:   at most n total steps
Total:        ≤ 2n steps  →  O(n)

This is called amortised analysis: the total cost is O(n), even if individual iterations look expensive.

The fixed-window vs variable-window comparison

When should I reach for this? (the trigger list)

Reach for variable sliding window when:

• The problem asks for the longest or shortest subarray (or substring) satisfying some condition.
• The condition is monotone: if a window of size W satisfies it, then any larger window (for "at least" conditions) also satisfies it — or vice versa. This monotonicity is what makes expand-shrink work.
• You see words like "at most K distinct characters," "sum exactly S," "all characters of P," "no repeats."
• The brute-force is O(n²) nested loops where both bounds slide.
• Elements are non-negative integers (for sum-based problems) — negative numbers break the monotonicity of the sum condition.

The same trick in five disguises

Disguise 1 — Longest Substring Without Repeating Characters (LC #3)

Condition: no character appears twice in the window. Window is "valid" while all characters are unique.

def length_of_longest_substring(s):
    left = 0
    seen = {}           # char → most recent index
    best = 0

    for right in range(len(s)):
        ch = s[right]
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1     # jump left past the duplicate
        seen[ch] = right
        best = max(best, right - left + 1)

    return best

Here we expand and record the max (not shrink to find the min). When a duplicate enters, we snap left past it in one jump instead of one-step shrinking. Same two-pointer logic — the window never holds a duplicate.

Disguise 2 — Minimum Window Substring (LC #76)

Find the smallest substring of s that contains all characters of t. This is the boss version of the pattern.

from collections import Counter

def min_window(s, t):
    need = Counter(t)       # characters required and their counts
    have = {}               # characters currently in window
    formed = 0              # how many unique chars in 'need' are satisfied
    required = len(need)

    left = 0
    best = (float('inf'), 0, 0)   # (length, left, right)

    for right in range(len(s)):
        ch = s[right]
        have[ch] = have.get(ch, 0) + 1
        if ch in need and have[ch] == need[ch]:
            formed += 1             # one more character fully satisfied

        while formed == required:   # all characters covered → try shrinking
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            out = s[left]
            have[out] -= 1
            if out in need and have[out] < need[out]:
                formed -= 1         # losing a required character
            left += 1

    return s[best[1]:best[2]+1] if best[0] != float('inf') else ""

The expand-shrink skeleton is identical. The "condition" is now formed == required instead of sum >= S.

Disguise 3 — Longest Subarray with Sum ≤ K (positive integers)

Flip the problem: instead of finding the minimum window with sum ≥ S, find the maximum window with sum ≤ K:

def longest_subarray_sum_k(arr, k):
    left = 0
    window_sum = 0
    best = 0

    for right in range(len(arr)):
        window_sum += arr[right]
        while window_sum > k:           # condition violated → shrink
            window_sum -= arr[left]
            left += 1
        best = max(best, right - left + 1)   # record AFTER shrinking (window is valid here)

    return best

For "longest" problems: record after shrinking (the window is in a valid state). For "shortest" problems: record before shrinking (you just found a valid window; now try to make it smaller).

Disguise 4 — Longest Substring with At Most K Distinct Characters (LC #340)

def length_of_longest_substring_k_distinct(s, k):
    left = 0
    freq = {}
    best = 0

    for right in range(len(s)):
        ch = s[right]
        freq[ch] = freq.get(ch, 0) + 1

        while len(freq) > k:            # too many distinct chars → shrink
            out = s[left]
            freq[out] -= 1
            if freq[out] == 0:
                del freq[out]
            left += 1

        best = max(best, right - left + 1)

    return best

The pattern remains: expand right, shrink left when condition breaks, record the valid window.

def character_replacement(s, k):
    left = 0
    freq = {}
    max_freq = 0          # max frequency of any single char in current window
    best = 0

    for right in range(len(s)):
        freq[s[right]] = freq.get(s[right], 0) + 1
        max_freq = max(max_freq, freq[s[right]])

        # chars to replace = window_size - max_freq
        if (right - left + 1) - max_freq > k:
            freq[s[left]] -= 1
            left += 1

        best = max(best, right - left + 1)

    return best

Traps that catch beginners

Say it like a pro (interview one-liner)

"I'll use a variable sliding window with two pointers. The right pointer always advances, expanding the window. Whenever the condition is satisfied, I shrink from the left — recording the window size each time — until the condition breaks. Both pointers only move forward, so the total work is O(n) amortised, with O(1) extra space or O(K) for any auxiliary structure like a frequency map."

Check yourself

Practice problems

When you can solve Minimum Size Subarray Sum without notes, explain the amortised O(n) argument, and name the conditions under which variable window breaks — you have fully learned this pattern.

Next up: Prefix Sum, where instead of a moving window, we precompute a lookup table that answers any range-sum query in O(1).