Sliding Window Technique: Fixed vs Variable Windows and When to Shrink

By 0xmote · May 26, 2026 · 14 min read · Updated Sep 27, 2026 Intermediate Tutorial

Key takeaways

Sliding window algorithm optimizes fixed and variable-length contiguous ranges by sliding one position at a time in O(n). Learn fixed and variable window patterns, differences from two pointers, with examples.

Introduction

Recalculating sum or conditions of contiguous subarrays or substrings from scratch each time easily causes timeout. This guide teaches how to reduce complexity by sliding the window one position at a time and updating incrementally. Sliding window is a technique for efficiently processing contiguous subarrays.

Fixed-Size Window

Basic Pattern

def max_sum_subarray(arr, k):
    """
    Maximum sum of subarray of size k
    [1, 4, 2, 10, 23, 3, 1, 0, 20], k=4 → 39
    """
    if len(arr) < k:
        return None
    
    # First window sum
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide window
    for i in range(k, len(arr)):
        window_sum = window_sum - arr[i - k] + arr[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum
# Test
arr = [1, 4, 2, 10, 23, 3, 1, 0, 20]
print(max_sum_subarray(arr, 4))  # 39 (4+2+10+23)

The whole trick is on the line window_sum = window_sum - arr[i - k] + arr[i]. Two neighbouring windows share k - 1 elements, so recomputing sum(arr[i-k+1:i+1]) for each position repeats almost all of the work and costs O(n·k). Subtracting the element that leaves and adding the one that enters costs O(1) per step, which gives O(n) regardless of k. The same idea works for anything that can be updated by “remove one, add one”: a sum, a count of vowels, a frequency table. It does not directly work for the window maximum, because removing the largest element gives no cheap way to find the next largest; that variant needs a monotonic deque (LeetCode 239). Step-by-Step Trace:

arr = [1, 4, 2, 10, 23, 3, 1, 0, 20], k=4
Initial window [0:4]: 1+4+2+10 = 17
Slide 1: Remove arr[0]=1, Add arr[4]=23
  [1:5]: 4+2+10+23 = 39 ✅ max
Slide 2: Remove arr[1]=4, Add arr[5]=3
  [2:6]: 2+10+23+3 = 38
Slide 3: Remove arr[2]=2, Add arr[6]=1
  [3:7]: 10+23+3+1 = 37
...
Result: 39

Variable-Size Window

Minimum Length Subarray

def min_subarray_len(arr, target):
    """
    Minimum length subarray with sum >= target
    [2,3,1,2,4,3], target=7 → 2 ([4,3])
    """
    left = 0
    current_sum = 0
    min_len = float('inf')
    
    for right in range(len(arr)):
        current_sum += arr[right]
        
        # Shrink window when condition met
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
    
    return min_len if min_len != float('inf') else 0
# Test
arr = [2, 3, 1, 2, 4, 3]
print(min_subarray_len(arr, 7))  # 2

How It Works:

arr = [2, 3, 1, 2, 4, 3], target=7
right=0: [2], sum=2 (< 7)
right=1: [2,3], sum=5 (< 7)
right=2: [2,3,1], sum=6 (< 7)
right=3: [2,3,1,2], sum=8 (>= 7) ✅
  Shrink: [3,1,2], sum=6 (< 7)
right=4: [3,1,2,4], sum=10 (>= 7) ✅
  Shrink: [1,2,4], sum=7 (>= 7) ✅
  Shrink: [2,4], sum=6 (< 7)
right=5: [2,4,3], sum=9 (>= 7) ✅
  Shrink: [4,3], sum=7 (>= 7) ✅ min_len=2
  Shrink: [3], sum=3 (< 7)
Result: 2

Why shrinking is safe here, and when it is not

This algorithm quietly relies on every element being non-negative. Because of that, extending a window can only increase its sum and removing from the left can only decrease it. Once [left, right] reaches the target, no longer window starting at left can be shorter, so it is safe to record the length and move left forward for good. That monotonic property is what lets left never move back, and it is what makes the total work O(n).

With negative numbers the property breaks. For [1, -1, 5] and target = 5, the loop first reaches the target at right = 2 with the window [1, -1, 5], records length 3, removes the 1, sees sum 4 and stops shrinking. It returns 3, but [5] alone has length 1: removing the -1 next would have raised the sum again, and the loop has no way of knowing that. Once dropping an element can move the sum in either direction, “shrink until invalid” stops being a valid rule. The code still runs and returns a number, which is the dangerous part: I have seen this solution pass all sample tests and then fail hidden tests that contain negatives. When the input can be negative, switch to prefix sums: a hash map of prefix sums for “subarray sums to exactly k” (LeetCode 560), or a monotonic deque over prefix sums for “shortest subarray with sum at least k” (LeetCode 862). Before writing a variable window, check the constraints for “1 <= nums[i]” or similar.

Fixed vs Variable Window

Feature	Fixed Size	Variable Size
Window Length	Always same (e.g., `k`)	Expands/shrinks based on conditions
Typical Loop	`right` advances, `left` advances when `right - left + 1 == k`	Expand with `right`, shrink with `left` until condition breaks
Representative Problems	Size k subarray sum/max, fixed-length anagram	Minimum length subarray sum, longest substring without repeating, minimum window substring
vs Two Pointers	Can express as `left = right - k + 1`	Same “expand/shrink pattern” two-pointer thinking

Both are same-direction two pointers where left and right only move forward. The difference is whether length is fixed.

Practical Problems

Problem 1: Max Consecutive Ones

def longest_ones(arr, k):
    """
    Maximum consecutive 1s when flipping at most k zeros
    [1,1,1,0,0,0,1,1,1,1,0], k=2 → 6
    """
    left = 0
    zero_count = 0
    max_len = 0
    
    for right in range(len(arr)):
        if arr[right] == 0:
            zero_count += 1
        
        # Shrink window if zeros exceed k
        while zero_count > k:
            if arr[left] == 0:
                zero_count -= 1
            left += 1
        
        max_len = max(max_len, right - left + 1)
    
    return max_len
# Test
arr = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0]
print(longest_ones(arr, 2))  # 6

Trace:

arr = [1,1,1,0,0,0,1,1,1,1,0], k=2
right=0-2: [1,1,1], zeros=0, len=3
right=3: [1,1,1,0], zeros=1, len=4
right=4: [1,1,1,0,0], zeros=2, len=5
right=5: [1,1,1,0,0,0], zeros=3 (> k)
  Shrink: [1,1,0,0,0], zeros=3
  Shrink: [1,0,0,0], zeros=3
  Shrink: [0,0,0], zeros=3
  Shrink: [0,0], zeros=2
right=6: [0,0,1], zeros=2, len=3
right=7: [0,0,1,1], zeros=2, len=4
right=8: [0,0,1,1,1], zeros=2, len=5
right=9: [0,0,1,1,1,1], zeros=2, len=6 ✅
right=10: [0,0,1,1,1,1,0], zeros=3 (> k)
  Shrink: [0,1,1,1,1,0], zeros=2, len=6
Result: 6

Problem 2: Longest Substring Without Repeating Characters

def length_of_longest_substring(s):
    """
    Longest substring without repeating characters
    "abcabcbb" → 3 ("abc")
    """
    char_set = set()
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        # Remove duplicates
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    
    return max_len
# Test
print(length_of_longest_substring("abcabcbb"))  # 3
print(length_of_longest_substring("bbbbb"))     # 1
print(length_of_longest_substring("pwwkew"))    # 3

The inner while removes characters from the left one at a time until the duplicate is gone. A common optimization stores the last index of each character in a dict and jumps directly: left = max(left, last[s[right]] + 1). The max is the part people forget. Without it, a character seen before the current window (for example the first a in "abba" when right reaches the last a) would move left backwards and produce an answer that is too long. Both versions are O(n); the jump version just does fewer operations per step. Trace:

s = "abcabcbb"
right=0: 'a', set={'a'}, len=1
right=1: 'b', set={'a','b'}, len=2
right=2: 'c', set={'a','b','c'}, len=3 ✅
right=3: 'a' (duplicate!)
  Remove 'a', left=1, set={'b','c'}
  Add 'a', set={'b','c','a'}, len=3
right=4: 'b' (duplicate!)
  Remove 'b', left=2, set={'c','a'}
  Add 'b', set={'c','a','b'}, len=3
...
Result: 3

Problem 3: Find All Anagrams

from collections import Counter
def find_anagrams(s, p):
    """
    Find starting indices of p's anagrams in s
    s="cbaebabacd", p="abc" → [0, 6]
    """
    result = []
    p_count = Counter(p)
    window_count = Counter()
    
    left = 0
    
    for right in range(len(s)):
        window_count[s[right]] += 1
        
        # Maintain window size
        if right - left + 1 > len(p):
            window_count[s[left]] -= 1
            if window_count[s[left]] == 0:
                del window_count[s[left]]
            left += 1
        
        # Check anagram
        if window_count == p_count:
            result.append(left)
    
    return result
# Test
print(find_anagrams("cbaebabacd", "abc"))
# [0, 6]

The del when a count reaches zero matters on older Python. Before 3.10, Counter({'a': 1, 'b': 0}) == Counter({'a': 1}) is False, because == was plain dict equality and a key with count 0 still counts as a key. Python 3.10 changed Counter equality to treat missing keys as zero, so the del is only strictly needed on older interpreters, but it keeps the code correct everywhere. Comparing two Counters costs O(σ) per step (σ = distinct characters); for lowercase letters a fixed array of 26 counts plus a running “matches” counter makes each step O(1), which is the version to write in C++ or Java.

Representative Problems (LeetCode)

These three are almost essential when studying sliding window. (Good to read in connection with examples above.)

Problem	Type	Key
3. Longest Substring Without Repeating Characters	Variable, condition: no duplicates	Add with `right` → remove duplicates by pulling `left`
76. Minimum Window Substring	Variable, need/cover	Expand with `right` until need met → shrink with `left` for minimum
643. Maximum Average Subarray I	Fixed length k	Slide one position: `sum -= out, sum += in`, O(n)

Minimum Window Substring Sketch (Python)

from collections import Counter
def min_window(s: str, t: str) -> str:
    need = Counter(t)
    missing = len(t)
    left = 0
    best = (float("inf"), None, None)  # length, start, end
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    return "" if best[1] is None else s[best[1] : best[2] + 1]

(In actual submissions, separating need/window is common. Above is a minimal example emphasizing “condition met with missing count”.)

Time Complexity Analysis

Brute Force
Checking all contiguous ranges [left, right] with nested loops is O(n²)~O(n³).
Sliding Window
left and right each move forward at most n times, total O(n). (Even if left moves multiple times per right advance, since left never goes backward, combined is linear.)
Map/Counter
Maintaining character/frequency is O(1)~O(σ) per operation (alphabet size σ), usually expressed as O(n) or O(n·σ).
Fixed Size k
Initial sum O(k) + slide O(n−k) → O(n).

Window Expand/Shrink Condition Patterns

Expand (right++)
Always widen one position to include element in current range. Fixed window advances right sequentially, variable expands “to satisfy condition”.
Shrink (left++)
- Fixed size: If right - left + 1 > k, pull left one position to maintain length k.
- Variable — when invalid: e.g., duplicate characters, too many zeros, before finding “minimum length” after need met.
- Variable — when valid but can shrink more: In Minimum Window, after need met, pull left to update minimum length.
Invariant
Writing “condition window must satisfy” in one sentence clarifies when to pull left with while. (e.g., “move left until no duplicate characters”.)

Loop Templates

Sliding Window Patterns

# Pattern 1: Fixed size
left = 0
for right in range(len(arr)):
    add(arr[right])
    
    if right - left + 1 == k:
        process_window()
        remove(arr[left])
        left += 1
# Pattern 2: Variable size
left = 0
for right in range(len(arr)):
    add(arr[right])
    
    while not is_valid():
        remove(arr[left])
        left += 1
    
    update_result()

Common Patterns

# 1. Maximum/Minimum length
max_len = 0
for right in range(len(arr)):
    # Expand
    while not is_valid():
        # Shrink
        left += 1
    max_len = max(max_len, right - left + 1)
# 2. Count valid subarrays
count = 0
for right in range(len(arr)):
    while not is_valid():
        left += 1
    count += right - left + 1  # All subarrays ending at right
# 3. Fixed size k
for right in range(len(arr)):
    if right >= k:
        remove(arr[right - k])
    add(arr[right])
    if right >= k - 1:
        process_window()

The counting template (count += right - left + 1) deserves a note because it looks like magic. After shrinking, [left, right] is the longest valid window ending at right, and if the condition is “shrink-closed” (every sub-window of a valid window is also valid, e.g. “product less than k” or “at most k distinct”), then every start position from left to right also gives a valid window. That is right - left + 1 subarrays, added in O(1). “Exactly k distinct” is not shrink-closed, so it is solved as atMost(k) - atMost(k - 1) (LeetCode 992).

Advanced Problems

Problem: Minimum Window Substring (LeetCode 76)

from collections import Counter
def min_window(s, t):
    """
    Minimum window substring containing all characters of t
    s="ADOBECODEBANC", t="ABC" → "BANC"
    """
    if not t or not s:
        return ""
    
    need = Counter(t)
    missing = len(t)
    left = 0
    min_len = float('inf')
    min_start = 0
    
    for right in range(len(s)):
        # Expand
        if need[s[right]] > 0:
            missing -= 1
        need[s[right]] -= 1
        
        # Shrink when valid
        while missing == 0:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_start = left
            
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    
    return "" if min_len == float('inf') else s[min_start:min_start + min_len]
# Test
print(min_window("ADOBECODEBANC", "ABC"))  # "BANC"

Problem: Longest Repeating Character Replacement

def character_replacement(s, k):
    """
    Longest substring with same character after replacing k characters
    s="AABABBA", k=1 → 4 ("AABA" or "BABB")
    """
    char_count = {}
    left = 0
    max_len = 0
    max_count = 0
    
    for right in range(len(s)):
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        max_count = max(max_count, char_count[s[right]])
        
        # If replacements needed > k, shrink
        while right - left + 1 - max_count > k:
            char_count[s[left]] -= 1
            left += 1
        
        max_len = max(max_len, right - left + 1)
    
    return max_len
# Test
print(character_replacement("AABABBA", 1))  # 4

Edge Cases and Common Mistakes

Coding Interview Tips

# ✅ Initialize properly
left = 0
window_state = {}  # or set(), Counter(), etc.
# ✅ Update window state
# Add when expanding (right)
# Remove when shrinking (left)
# ✅ Check boundary conditions
# - Empty array/string
# - k > len(arr)
# - All same elements
# ✅ Understand expand/shrink conditions
# Fixed: Expand until size k, then slide
# Variable: Expand always, shrink when invalid

Common Mistakes

# ❌ Wrong: Forgot to remove when shrinking
for right in range(len(arr)):
    add(arr[right])
    while not is_valid():
        left += 1  # Forgot to remove arr[left]!
# ✅ Correct: Remove before moving left
for right in range(len(arr)):
    add(arr[right])
    while not is_valid():
        remove(arr[left])
        left += 1
# ❌ Wrong: Incorrect window size check
if right - left == k:  # Should be right - left + 1
# ✅ Correct: Window size is right - left + 1
if right - left + 1 == k:

The forgotten remove is the bug I make most often when writing these under time pressure, and it is hard to spot because the loop still terminates: left advances, but the window state (the set, the counter, the sum) still contains elements that are no longer inside the window, so the validity check keeps failing or succeeds too late. A quick way to catch it is to assert, on a small input, that the maintained state equals the state recomputed from arr[left:right + 1] after every step. The other frequent mistake is updating the answer in the wrong place: for “longest valid” the answer is updated after the shrink loop (the window is valid again), while for “shortest valid” it is updated inside the shrink loop (while the window is still valid).

Choosing a fixed or variable window

Pattern	Window Size	Movement	Example
Fixed	Constant k	Slide one position	Max sum size k
Variable (max)	Expand until invalid	Expand always, shrink when invalid	Longest substring
Variable (min)	Shrink until invalid	Expand until valid, shrink while valid	Minimum window

Use a fixed window when the problem gives the length. Use a variable window when it asks for the longest or shortest contiguous range satisfying a condition, and the condition is monotonic: if a window is valid, every smaller window inside it stays valid (for “longest”) or every larger window containing it stays valid (for “shortest”). That property is what makes it safe to move the left edge forward and never look back.

It breaks with negative numbers. “Count subarrays with sum equal to k” on an array that can contain negatives (LeetCode 560) looks like a window problem, but shrinking can increase the sum, so the window gives wrong answers. The correct approach there is a running prefix sum with a hash map of previously seen sums.

Frequently Asked Questions (FAQ)

Q. In Longest Repeating Character Replacement, why is it fine that max_count never decreases when the window shrinks?

A. The answer only gets longer when a window contains a character more often than any earlier window did, which requires max_count to grow. A stale, too-large max_count can keep a window from shrinking, but it never records a length larger than one that was actually valid. So the result stays correct and you avoid recounting the window on every shrink.

Sliding Window Technique: Fixed vs Variable Windows and When to Shrink

Key takeaways

Introduction

Fixed-Size Window

Basic Pattern

Variable-Size Window

Minimum Length Subarray

Why shrinking is safe here, and when it is not

Fixed vs Variable Window

Practical Problems

Problem 1: Max Consecutive Ones

Problem 2: Longest Substring Without Repeating Characters

Problem 3: Find All Anagrams

Representative Problems (LeetCode)

Minimum Window Substring Sketch (Python)

Time Complexity Analysis

Window Expand/Shrink Condition Patterns

Loop Templates

Sliding Window Patterns

Common Patterns

Advanced Problems

Problem: Minimum Window Substring (LeetCode 76)

Problem: Longest Repeating Character Replacement

Edge Cases and Common Mistakes

Coding Interview Tips

Common Mistakes

Choosing a fixed or variable window

Recommended Problems

Baekjoon

LeetCode

Programmers

Frequently Asked Questions (FAQ)

Q. In Longest Repeating Character Replacement, why is it fine that max_count never decreases when the window shrinks?

Key takeaways

Introduction

Fixed-Size Window

Basic Pattern

Variable-Size Window

Minimum Length Subarray

Why shrinking is safe here, and when it is not

Fixed vs Variable Window

Practical Problems

Problem 1: Max Consecutive Ones

Problem 2: Longest Substring Without Repeating Characters

Problem 3: Find All Anagrams

Representative Problems (LeetCode)

Minimum Window Substring Sketch (Python)

Time Complexity Analysis

Window Expand/Shrink Condition Patterns

Loop Templates

Sliding Window Patterns

Common Patterns

Advanced Problems

Problem: Minimum Window Substring (LeetCode 76)

Problem: Longest Repeating Character Replacement

Edge Cases and Common Mistakes

Coding Interview Tips

Common Mistakes

Choosing a fixed or variable window

Recommended Problems

Baekjoon

LeetCode

Programmers

Related Articles

Frequently Asked Questions (FAQ)

Q. In Longest Repeating Character Replacement, why is it fine that max_count never decreases when the window shrinks?