Sliding Window — Explained with Examples

Sliding window maintains a subarray subset of data using two pointers, optimizing problems involving contiguous sequences from O(n²) to O(n).

Sliding window defines a window (range) that slides across the data. Fixed window maintains a constant size (e.g., max sum of k consecutive elements). Variable window expands and contracts based on conditions (e.g., smallest subarray with sum ≥ target). The window is tracked by left and right pointers, and the window state is updated incrementally as pointers move.

Think of sliding window like looking through a moving car window at a landscape. You see a fixed-width section of scenery that changes as the car moves. To calculate the total number of trees visible, you add new trees entering the view and subtract trees leaving — no need to recount everything from scratch.

The technique transforms many O(n²) subarray problems into O(n) solutions by avoiding recomputation.

# Fixed window: max sum of k consecutive elements
def max_sum_fixed(arr, k):
    if len(arr) < k:
        return -1
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

# Variable window: smallest subarray with sum ≥ target
def min_subarray_length(nums, target):
    left = 0
    current_sum = 0
    min_length = float('inf')
    for right in range(len(nums)):
        current_sum += nums[right]
        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1
    return min_length if min_length != float('inf') else 0

print(max_sum_fixed([2, 1, 5, 1, 3, 2], 3))  # 9 (5+1+3)
print(min_subarray_length([2, 3, 1, 2, 4, 3], 7))  # 2 ([4, 3])

Sliding window applies to subarray/substring problems: longest substring without repeating characters, maximum average subarray, and string permutations.

Two Pointers, Array, Hash Table, Queue

Two Pointers