Sliding Window Technique

The sliding window technique maintains a "window" — a contiguous range of elements defined by two pointers — that expands or slides across an array or string, avoiding redundant recomputation and turning many O(n²) or O(n³) brute-force solutions into O(n).

When to Use Sliding Window

Reach for this pattern whenever a problem asks about a contiguous subarray or substring that satisfies some condition — maximum/minimum sum, longest/shortest length, or a count of distinct characters. If your brute force involves checking every subarray with nested loops, a sliding window can usually collapse it into a single pass.

Fixed-Size vs Variable-Size Windows

• Fixed-Size Window — the window length k is given upfront. Slide it one step at a time: add the new element entering the window, remove the one leaving it. Used for problems like "maximum sum of any subarray of size k."
• Variable-Size Window — the window grows by moving the right pointer, and shrinks by moving the left pointer whenever a constraint is violated. Used for "longest substring without repeating characters" or "smallest subarray with sum ≥ target."
• Window + Hash Map — many variable-size problems pair the window with a hash map/frequency count to track character counts or element occurrences in O(1) per step.

Time & Space Complexity

Illustration: Window Sliding Across an Array

C++ Example: Maximum Sum Subarray of Size K

#include <iostream>
#include <vector>
using namespace std;

int maxSumSubarray(vector<int>& arr, int k) {
    int windowSum = 0, maxSum = 0;

    // build the first window
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    // slide the window across the rest of the array
    for (int i = k; i < arr.size(); i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = max(maxSum, windowSum);
    }
    return maxSum;
}

Python Example: Variable-Size Windows

# 1. Longest substring without repeating characters
def length_of_longest_substring(s):
    seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

# 2. Minimum size subarray with sum >= target
def min_subarray_len(target, nums):
    left = 0
    total = 0
    best = float('inf')
    for right, num in enumerate(nums):
        total += num
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return best if best != float('inf') else 0

# 3. Minimum window substring containing all characters of t
def min_window(s, t):
    from collections import Counter
    need = Counter(t)
    missing = len(t)
    left = start = end = 0

    for right, ch in enumerate(s, 1):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1

        if missing == 0:
            while left < right and need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if end == 0 or right - left < end - start:
                start, end = left, right
            need[s[left]] += 1
            missing += 1
            left += 1

    return s[start:end]

Practice on LeetCode

Once you're comfortable with the concepts above, try solving these problems to reinforce your understanding:

• Easy 643. Maximum Average Subarray I — classic fixed-size window.
• Easy 219. Contains Duplicate II — fixed-size window with a hash set.
• Medium 3. Longest Substring Without Repeating Characters — variable-size window with a hash map.
• Medium 209. Minimum Size Subarray Sum — shrinking window once a sum threshold is met.
• Medium 424. Longest Repeating Character Replacement — variable-size window with frequency counting.